Castor quadruplorum (Q1103615)

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.