2012/08/31 by Dominic J. D. Hughes, Hughes, Dominic J. D.
Computer Science · Biochemistry, Genetics and Molecular Biology · #Cellular Automata and Applications #Computability, Logic, AI Algorithms #DNA and Biological Computing
paper · pdf · doi:10.48550/arxiv.1208.6342
Wolfram [2, p. 707] and Cook [1, p. 3] claim to prove that a (2,5) Turing machine (2 states, 5 symbols) is universal, via a universal cellular automaton known as Rule 110. The first part of this paper points out a critical gap in their argument. The second part bridges the gap, thereby giving what appears to be the first proof of universality.