¿Puede cada algoritmo de auto-modificación ser modelado por un algoritmo que no se auto-modifica?

Si tenemos algún programa de computadora arbitrario que pueda modificar sus instrucciones, ¿es posible simular ese programa con un programa que no pueda modificar sus instrucciones?

Editar:

Soy nuevo en stackexchange, así que no estoy seguro si se me permite hacer una NUEVA pregunta aquí, pero aquí va: Ok, entonces la prueba de que es posible es realmente muy simple, como ustedes han demostrado. Ahora, me pregunto: ¿Existen problemas para los cuales es más eficiente (y en qué medida) usar el algoritmo de auto-modificación más eficiente para resolver el problema, en comparación con el algoritmo de no auto-modificación más eficiente equivalente a la entrada-salida?

computability computation-models turing-completeness church-turing-thesis usuario56834
fuente

Respuestas:

Si es posible. Puede simular el programa utilizando un intérprete para el idioma en el que está escrito. Ahora, el programa (el intérprete) está arreglado y lo que solía ser un programa auto modificable ahora son los datos del intérprete.

En particular, podría perfectamente tener una máquina universal de Turing que permitiera al TM que simula modificar su propia descripción. (La descripción de la máquina simulada, quiero decir; no la UTM).

David Richerby
fuente

Ni siquiera necesita el intérprete hipotético. Una CPU de la ejecución de su algoritmo de auto-modificación es en sí misma una máquina que ejecuta un algoritmo fijo (que dicta la forma en que ejecuta instrucciones)

Alexander - Restablecer Mónica

@AlexanderMomchliov existen CPU que pueden modificar partes de su conjunto de instrucciones sobre la marcha (pero sí, la idea es la misma: la parte programable son los datos, el microcontrolador que lo ejecuta es el intérprete), aunque apunta a un microcontrolador dentro de una celda FPGA podría ser complicado)

John Dvorak

para responder: "podría perfectamente tener una máquina universal de Turing que permitiera al TM que simula modificar su propia descripción". Estoy pensando: ¿esto no plantea la pregunta? porque ahora todavía necesitas demostrar que la TM que se está simulando realmente puede modelar el algoritmo de auto-modificación, ¿verdad? Todavía podría ser el caso de que haya un programa de auto-modificación que NO sea en sí mismo una máquina de Turing, por lo que no podemos usar la integridad de Turing para mostrar que se puede simular, ya que la integridad de Turing se relaciona con la simulación de TM y la auto-modificación Algo no es un TM.

user56834

@ Programmer2134 No plantea la pregunta en absoluto. Independientemente de la CPU en la que creas que estás ejecutando tu programa de auto modificación, puedo simular esa CPU en una máquina Turing. Para explicarlo de una manera diferente, el programa inicial es una secuencia finita de instrucciones, algunas de las cuales modifican el programa en sí. El UTM puede simular cada una de las instrucciones, cada una de las modificaciones puede simularse y cada una de las instrucciones modificadas puede simularse. No hay nada, en ninguna etapa de este proceso, que vaya más allá del poder de las máquinas Turing.

David Richerby

Cualquier modelo computacional completo de Turing que no tenga código de modificación (o "código") sirve como prueba de esa declaración. No sé que ninguno de los modelos estándar (TM, memoria RAM, ...) Qué tienen modificar el código, por lo que no tiene que ir muy lejos.

Para obtener un programa en cualquier idioma que tenga en mente, compile a partir de dicho modelo (y asegúrese de que el compilador no introduzca modificación de código).

Esto es, por supuesto, un argumento existencial: no es un programa equivalente. Pero también sabemos que hay compiladores recursivos (es decir, computables) entre cualquiera de los dos idiomas completos de Turing, de modo que así es como se obtiene un programa de la forma (lectura: en el idioma) que desea.

Rafael
fuente

Para agregar a la respuesta de David Richerby :

Si fuera cierto que ningún algoritmo de auto-modificación no puede ser modelado por algoritmos que no se auto-modifiquen, entonces esos algoritmos tendrían que ejecutarse en algo que también se auto-modifica. Tendrían que ser tortugas hasta el fondo.

Como mencioné en mi comentario, un algoritmo de auto-modificación se puede ejecutar en un procesador que se atiene a las reglas de un algoritmo estático (codificado en su diseño) que "le dice" cómo ejecutar las instrucciones de la máquina.

Alexander - Restablece a Monica
fuente

Creo que podría ser una línea divisoria interesante. Creo que se podría argumentar que la "vida" es un algoritmo de auto-modificación que no puede ser modelado por algoritmos que no se auto-modifican, pero, de nuevo, la "vida" generalmente no se considera como un algoritmo.

Cort Ammon el

@CortAmmon: Si vemos la "vida" como un algoritmo, ¿cuál es su entrada y su salida? ¿Cómo podría uno probar que cualquier algoritmo equivalente (es decir, cualquier algoritmo que produce la misma salida cuando se le da la misma entrada) debe auto modificarse?

ruakh

@ruakh Si tuviera que argumentar que la vida era un algoritmo de auto modificación, las entradas serían en sí mismas y sus salidas serían en sí mismas. Demostrar que no se puede reducir a un algoritmo no auto modificable sería más complicado, pero creo que es una hipótesis popular. Después de todo, ¿cuántas personas quieren creer que pueden reducirse a un algoritmo que puede ejecutarse en una computadora?

Cort Ammon el

@CortAmmon: No puedo reducirme a un algoritmo que se ejecuta en una computadora porque ese algoritmo ya no es "yo"; Soy más que mis entradas y salidas. Pero si partimos de la suposición de que solo soy un algoritmo, entonces agregar "eso puede ejecutarse en una computadora" en realidad no cambia nada. Re: "Si tuviera que argumentar que la vida era un algoritmo de auto-modificación, las entradas serían en sí mismas y sus salidas serían en sí mismas": En ese caso, creo que se desviaría mucho fuera de CS, y peligrosamente cerca de crackpottery.

ruakh

@CortAmmon Un programa que se genera a sí mismo dado que la entrada es justa cat. (Sin juego de palabras, a pesar de que los gatos son seres vivos)

user253751