The determination of the value of Rado's noncomputable function for fourstate Turing machines
Author:
Allen H. Brady
Journal:
Math. Comp. 40 (1983), 647665
MSC:
Primary 03D10; Secondary 03B35, 03D15, 68C30, 68D20
MathSciNet review:
689479
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The welldefined but noncomputable functions and given by T. Rado as the "score" and "shift number" for the kstate Turing machine "Busy Beaver Game" were previously known only for . The largest known lower bounds yielding the relations and , reported by this author, supported the conjecture that these lower bounds are the actual particular values of the functions for . The fourstate case has previously been reduced to solving the blank input tape halting problem of only 5,820 individual machines. In this final stage of the case, one appears to move into a heuristic level of higher order where it is necessary to treat each machine as representing a distinct theorem. The remaining set consists of two primary classes in which a machine and its tape are viewed as the representation of a growing string of cellular automata. The proof techniques, embodied in programs, are entirely heuristic, while the inductive proofs, once established by the computer, are completely rigorous and become the key to the proof of the new and original mathematical results: and .
 [1]
A. H. Brady, Solutions to Restricted Cases of the Halting Problem, Ph.D. thesis, Oregon State Univ., Corvallis, December 1964.
 [2]
A. H. Brady, "The conjectured highest scoring machines for Rado's for the value ", IEEE Trans. Comput., v. EC15, 1966, pp. 802803.
 [3]
M. W. Green, A Lower Bound on Rado's Sigma Function for Binary Turing Machines, 5th IEEE Symposium on Switching Theory, November 1964, pp. 9194.
 [4]
R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S142, January 1963.
 [5]
S. Lin, Computer Studies of Turing Machine Problems, Ph.D. thesis. The Ohio State University, Columbus, 1963.
 [6]
Shen
Lin and Tibor
Rado, Computer studies of Turing machine problems, J. Assoc.
Comput. Mach. 12 (1965), 196–212. MR 0195649
(33 #3847)
 [7]
D. S. Lynn, "New results for Rado's sigma function for binary Turing machines," IEEE Trans. Comput., v. C21, 1972, pp. 894896.
 [8]
T.
Radó, On noncomputable functions, Bell System Tech. J.
41 (1962), 877–884. MR 0133229
(24 #A3063)
 [9]
Tibor
Radó, On a simple source for noncomputable functions,
Proc. Sympos. Math. Theory of Automata (New York, 1962) Polytechnic Press
of Polytechnic Inst. of Brooklyn, Brooklyn, N.Y., 1963,
pp. 75–81. MR 0170808
(30 #1043)
 [1]
 A. H. Brady, Solutions to Restricted Cases of the Halting Problem, Ph.D. thesis, Oregon State Univ., Corvallis, December 1964.
 [2]
 A. H. Brady, "The conjectured highest scoring machines for Rado's for the value ", IEEE Trans. Comput., v. EC15, 1966, pp. 802803.
 [3]
 M. W. Green, A Lower Bound on Rado's Sigma Function for Binary Turing Machines, 5th IEEE Symposium on Switching Theory, November 1964, pp. 9194.
 [4]
 R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S142, January 1963.
 [5]
 S. Lin, Computer Studies of Turing Machine Problems, Ph.D. thesis. The Ohio State University, Columbus, 1963.
 [6]
 S. Lin & T. Rado, "Computer studies of Turing machine problems," J. Assoc. Comput. Mach., v. 12, 1965, pp. 196212. MR 0195649 (33:3847)
 [7]
 D. S. Lynn, "New results for Rado's sigma function for binary Turing machines," IEEE Trans. Comput., v. C21, 1972, pp. 894896.
 [8]
 T. Rado, "On noncomputable functions", Bell System Tech. J., v. 41, 1962, pp. 877884. MR 0133229 (24:A3063)
 [9]
 T. Rado, "On a simple source for noncomputable functions," Proceedings of the Symposium on Mathematical Theory of Automata, Polytechnic Institute of Brooklyn, April 1963, pp. 7581. MR 0170808 (30:1043)
Similar Articles
Retrieve articles in Mathematics of Computation
with MSC:
03D10,
03B35,
03D15,
68C30,
68D20
Retrieve articles in all journals
with MSC:
03D10,
03B35,
03D15,
68C30,
68D20
Additional Information
DOI:
http://dx.doi.org/10.1090/S00255718198306894796
PII:
S 00255718(1983)06894796
Keywords:
Busy Beaver Game,
cellular automata,
computability,
mechanical proofs,
Turing machines
Article copyright:
© Copyright 1983
American Mathematical Society
