BUSY BEAVER COMPETITION AND COLLATZ-LIKE PROBLEMS

被引:19
作者
MICHEL, P
机构
[1] Paris, F-75005
关键词
D O I
10.1007/BF01409968
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
The Busy Beaver Competition is held by Turing machines. The better ones halt taking much time or leaving many marks, when starting from a blank tape. In order to understand the behavior of some Turing machines that were once record holders in the five-state Busy Beaver Competition, we analyze their halting problem on all inputs. We prove that the halting problem for these machines amounts to a well-known problem of number theory, that of the behavior of the repeated iteration of Collatz-like functions, that is functions defined by cases according to congruence classes.
引用
收藏
页码:351 / 367
页数:17
相关论文
共 20 条
[1]  
Brady A. H, 1988, UNIVERSAL TURING MAC, P259
[3]  
CONWAY JH, 1972, 1972 P NUMB THEOR, P49
[4]  
Dewdney A. K., 1984, SCI AM, V251, P10
[5]  
DEWDNEY AK, 1984, SCI AM, V251, P27
[6]  
DEWDNEY AK, 1985, SCI A, V252, P16
[7]  
GREEN MW, 1964, 5TH P IEEE S SWITCH, P91
[8]  
Hopcroft J. E., 1979, INTRO AUTOMATA THEOR
[9]   THE 3X+1 PROBLEM AND ITS GENERALIZATIONS [J].
LAGARIAS, JC .
AMERICAN MATHEMATICAL MONTHLY, 1985, 92 (01) :3-23
[10]   COMPUTER STUDIES OF TURING MACHINE PROBLEMS [J].
LIN, S ;
RADO, T .
JOURNAL OF THE ACM, 1965, 12 (02) :196-&