Autor:	Hughes, Dominic J. D.
Rok vydání:	2012
Předmět:	Computer Science - Formal Languages and Automata Theory Computer Science - Logic in Computer Science Mathematics - Logic 03D10 68Q05 F.1.1 F.4.1
Druh dokumentu:	Working Paper
Popis:	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. Comment: 13-page draft. Languished untouched since 2007. Seek co-author to dot 'i's and cross 't's. Email if interested
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/1208.6342 Zobrazit plný text záznamu View this record from Arxiv