¿Es posible tener una máquina de Turing que sea capaz de construir otra máquina de Turing (diferente) a partir de bits puramente aleatorios?

Déjame darte un ejemplo no completo de Turing que es uno de mis favoritos, el MetaArtbot de Mark. Es una aplicación web simple basada en Tracery. Tracery es un lenguaje para generar texto al azar, y se usa para alimentar muchos bots de Twitter, incluidos algunos bots SVG (Gráficos vectoriales escalables) como Tiny Spires \ U0001f3f0 (@tinyspires).

El giro aquí es que MetaArtbot usa Tracery para generar artbots de Tracery. Toma bits aleatorios y genera un “programa” bien formado a partir de ellos. Luego, el programa se puede ejecutar varias veces para generar SVG aleatorios.

Entonces, ¿podríamos hacer lo mismo para un lenguaje completo de Turing? Absolutamente. Puedo escribir un programa en C que, dada una entrada aleatoria, genera un programa en C bien formado basado en esa entrada, y asegurarme de que sea un programa diferente cada vez. (O incluso podríamos escribir una gramática de Tracery que genere una C bien formada). Todo eso podría, en teoría, reducirse a máquinas Turing, no es que yo sepa de un compilador de máquinas C-a-Turing en la parte superior de mi cabeza. O podríamos simplemente hacer que Tracery genere descripciones de la máquina de Turing, utilizando la entrada aleatoria como fuente de aleatoriedad.

Sin embargo, eso no significa que podamos generar todos los programas posibles a partir de ese ejemplo. Generar programas es fácil. Cubrir todo el espacio de los programas legales es algo más difícil …

… pero no imposible. Considere generar lenguaje ensamblador, para un conjunto de instrucciones donde cada combinación posible de 32 bits es una instrucción legal. Entonces, cualquier entrada aleatoria también es una salida válida, posiblemente rellenada a 32 bits. La mayoría de ellos no son productos muy interesantes, eso se detendría rápidamente.

Físicamente no. Una máquina de Turing es un dispositivo hipotético que ejecuta un programa de computadora de complejidad no especificada, escribiendo 1 y ceros en una cinta de papel potencialmente infinita. Es un concepto profundamente defectuoso, muy alejado de la computadora que está utilizando para acceder a Quora, pero útil como dispositivo teórico para explorar los límites teóricos de la informática, así como los conceptos matemáticos pueden dar forma al mundo de la física y la ingeniería. No puedo ver ni comprender la raíz cuadrada de menos uno, pero tiene aplicaciones prácticas, por ejemplo.

Pero, deje caer la palabra Turing, ¿podría una máquina construir otra máquina? Bueno, sí, y eso parece más probable con el progreso realizado con las impresoras 3D.

yo

Una “máquina universal de Turing” puede simular el funcionamiento de cualquier otra máquina de Turing (incluida ella misma) al analizar una descripción de la máquina desde su entrada.