Máquina de Turing universal

Davis hace un caso indicando que el computador de Turing, el Automatic Computing Engine (ACE), "anticipó" las nociones de microprogramación (microcódigo) y procesadores RISC (Davis 2000:188).Donald Knuth cita el trabajo de Turing en el computador ACE como designando "hardware para facilitar la vinculación a subrutinas";[2]​ Davis también hace referencia a este trabajo como el uso por Turing de un hardware de "stack" (Davis 2000:237 Nota 18).El "primer programa serio de von Neumann... [fue] para simplemente ordenar datos eficientemente" (Davis 2000:184).Knuth observa que el retorno de subrutina incrustado en el propio programa en lugar de registros especiales es atribuible a von Neumann y Goldstine.[3]​ Knuth además afirma que Davis menciona brevemente a los sistemas operativos y a los compiladores como resultados de la noción de programa como datos (Davis 2000:185).Otros dos nombres de importancia son los investigadores canadienses Melzak (1961) y Lambek (1961).El teorema utm demuestra la existencia de dicha función.En consecuencia, toda máquina de Turing puede codificarse como una cadena sobre el alfabeto {0, 1}.Similarmente, nuestra construcción asocia a cada cadena binaria α, una máquina de Turing Mα.[4]​ Cuando Alan Turing vino con la idea de una máquina universal tenía en mente el más simple modelo de computación lo suficientemente poderoso como para calcular todas las posibles funciones que pueden ser calculadas.Él mostró que dos símbolos eran suficientes, siempre y cuando fueran usados suficiente estados (o viceversa), y que siempre era posible intercambiar estados por símbolos.Máquinas universales Turing pequeñamente débiles que simulan el autómata celular regla 110 ha sido dado por los pares de estado símbolo (6, 2), (3, 3) y (2, 4).