¿Quién fue el primero en demostrar que existe una máquina de Turing universal que utiliza un alfabeto binario?

Question

El título lo dice todo, creo.

Sabemos que hay máquinas de Turing universales que sólo utilizan un alfabeto binario. ¿Pero quién lo demostró primero?

El propio Turing demostró la existencia de una máquina de Turing universal... ¿pero también demostró que dicha máquina puede existir utilizando sólo un alfabeto binario? ¿O fue otra persona?

¿O simplemente era "obvio" para él y para otros que esto sería así, y por eso no existe una "primera" prueba o publicación explícita de este resultado?

Pero si hay una publicación que pueda considerarse la "primera" prueba de este resultado, me interesaría mucho saber cuál es.

Merci !

Answer 1

Una máquina de Turing en la que una celda de cinta tiene sólo dos símbolos posibles se llama a veces Máquina de postproducción . En realidad, el modelo de Post se desarrolló de forma independiente al de Turing y se publicó más tarde, el mismo año, en 1936; pero creo que para ambos, y para los que vieron ambos trabajos, debió quedar claro que los dos son equivalentes.