
doi: 10.1007/bf01625831
The well known Rado function B(n,m) is defined as the maximal number of printing symbols which can be left on the type by a deterministic Turing machine with n states and m symbols when it eventually stops. The value of the Rado function depends on how Turing machines are defined. The authors used the definition of turing machines by means of quadruples instead of traditional quintuples. In this case in one step a machine should only move or print a symbol. Using a not difficult simulation of any Turing machines by machines having only 3 internal states the authors obtained the following main results: B(n,m) is nonrecursive for \(n\geq 3\); there is a universal quadruple Turing machine with 3 internal states; B(2,m) is recursive.
Rado function, Turing machines and related notions, busy beaver problem, Models of computation (Turing machines, etc.), deterministic Turing machine, Recursive functions and relations, subrecursive hierarchies, universal quadruple Turing machine
Rado function, Turing machines and related notions, busy beaver problem, Models of computation (Turing machines, etc.), deterministic Turing machine, Recursive functions and relations, subrecursive hierarchies, universal quadruple Turing machine
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
