Skip to Main Content

Mathematics of Computation

Published by the American Mathematical Society, the Mathematics of Computation (MCOM) is devoted to research articles of the highest quality in all areas of pure and applied mathematics.

ISSN 1088-6842 (online) ISSN 0025-5718 (print)

The 2020 MCQ for Mathematics of Computation is 1.98.

What is MCQ? The Mathematical Citation Quotient (MCQ) measures journal impact by looking at citations over a five-year period. Subscribers to MathSciNet may click through for more detailed information.

 

The determination of the value of Rado’s noncomputable function $\Sigma (k)$ for four-state Turing machines
HTML articles powered by AMS MathViewer

by Allen H. Brady PDF
Math. Comp. 40 (1983), 647-665 Request permission

Abstract:

The well-defined but noncomputable functions $\Sigma (k)$ and $S(k)$ given by T. Rado as the "score" and "shift number" for the k-state Turing machine "Busy Beaver Game" were previously known only for $k \leqslant 3$. The largest known lower bounds yielding the relations $\Sigma (4) \geqslant 13$ and $S(4) \geqslant 107$, reported by this author, supported the conjecture that these lower bounds are the actual particular values of the functions for $k = 4$. The four-state 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 $k = 4$ 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: $\Sigma (4) = 13$ and $S(4) = 107$.
References
    A. H. Brady, Solutions to Restricted Cases of the Halting Problem, Ph.D. thesis, Oregon State Univ., Corvallis, December 1964. A. H. Brady, "The conjectured highest scoring machines for Rado’s $\Sigma (k)$ for the value $k = 4$", IEEE Trans. Comput., v. EC-15, 1966, pp. 802-803. M. W. Green, A Lower Bound on Rado’s Sigma Function for Binary Turing Machines, 5th IEEE Symposium on Switching Theory, November 1964, pp. 91-94. R. W. House & T. Rado, An Approach to Artificial Intelligence, IEEE Special Publication S-142, January 1963. S. Lin, Computer Studies of Turing Machine Problems, Ph.D. thesis. The Ohio State University, Columbus, 1963.
  • Shen Lin and Tibor Rado, Computer studies of Turing machine problems, J. Assoc. Comput. Mach. 12 (1965), 196–212. MR 195649, DOI 10.1145/321264.321270
  • D. S. Lynn, "New results for Rado’s sigma function for binary Turing machines," IEEE Trans. Comput., v. C-21, 1972, pp. 894-896.
  • T. Radó, On non-computable functions, Bell System Tech. J. 41 (1962), 877–884. MR 133229, DOI 10.1002/j.1538-7305.1962.tb00480.x
  • Tibor Radó, On a simple source for non-computable 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
Similar Articles
Additional Information
  • © Copyright 1983 American Mathematical Society
  • Journal: Math. Comp. 40 (1983), 647-665
  • MSC: Primary 03D10; Secondary 03B35, 03D15, 68C30, 68D20
  • DOI: https://doi.org/10.1090/S0025-5718-1983-0689479-6
  • MathSciNet review: 689479