Todo algoritmo auto-modificador pode ser modelado por um algoritmo não-auto-modificador?

Se temos algum programa de computador arbitrário que pode modificar suas instruções, é possível simular esse programa com um programa que não pode modificar suas instruções?

Editar:

Eu sou novo no stackexchange, então não tenho certeza se posso fazer uma nova pergunta aqui, mas aqui vai: Ok, então a prova de que isso é possível é realmente muito simples, como vocês demonstraram. Agora, eu estou me perguntando: existem problemas para os quais é mais eficiente (e em que medida) usar o algoritmo de auto-modificação mais eficiente para resolver o problema, versus o algoritmo não-auto-modificado mais eficiente de entrada-saída-equivalente?

computability computation-models turing-completeness church-turing-thesis user56834
fonte

Respostas:

Sim é possivel. Você pode simular o programa usando um intérprete para o idioma em que está escrito. Agora, o programa (o intérprete) está corrigido e o que costumava ser um programa de autod modificação é agora os dados do intérprete.

Em particular, você poderia perfeitamente ter uma máquina de Turing universal que permitisse à TM que está simulando modificar sua própria descrição. (A descrição da máquina simulada, quero dizer; não a UTM.)

David Richerby
fonte

Você nem precisa do intérprete hipotético. A CPU executar seu algoritmo de auto-modificação é em si uma máquina que executa um algoritmo fixo (que dita como ele executa instruções)

Alexander - Reintegrar Monica

@AlexanderMomchliov existem CPUs que podem modificar partes do conjunto de instruções em tempo real (mas sim, a idéia é a mesma - a parte programável são os dados, o microcontrolador que o executa é o intérprete - embora aponte para um microcontrolador dentro de uma célula FPGA pode ser complicado)

John Dvorak

para responder a: "você poderia perfeitamente ter uma máquina de Turing universal que permitisse à TM que está simulando modificar sua própria descrição". Estou pensando: isso não implora a pergunta? porque agora você ainda precisa provar que a MT que está sendo simulada pode realmente modelar o algoritmo auto-modificador, certo? Ainda é possível que exista um programa auto-modificador que NÃO seja ele próprio uma máquina de Turing, portanto, não podemos usar a integridade de Turing para mostrar que ela pode ser simulada, pois a integridade de Turing está relacionada à simulação de TMs e à modificação automática. algo não é uma TM.

User56834

@ Programmer2134 Não implora a pergunta. Seja qual for a CPU em que você pensa que está executando seu programa de modificação própria, eu posso simular essa CPU em uma máquina de Turing. Para explicá-lo de uma maneira diferente, o programa inicial é uma sequência finita de instruções, algumas das quais acontecem modificam o próprio programa. Cada uma das instruções pode ser simulada pelo UTM, cada uma das modificações pode ser simulada e cada uma das instruções modificadas pode ser simulada. Não há nada, em qualquer estágio deste processo, que ultrapasse o poder das máquinas de Turing.

precisa saber é o seguinte

Qualquer modelo computacional completo de Turing que não possua código modificador (ou "código") serve como prova dessa afirmação. Eu não sei que qualquer um dos modelos padrão (TM, RAM, ...) não tem modificar o código, de modo que não tem que olhar muito longe.

Para obter um programa em qualquer idioma que você tenha em mente, compile a partir desse modelo (e certifique-se de que o compilador não introduza modificação de código).

Este é, naturalmente, um argumento existencial: lá é um programa equivalente. Mas também sabemos que existem compiladores recursivos (isto é, computáveis) entre duas linguagens completas de Turing, e é assim que você obtém um programa do formulário (leia-se: na linguagem) que deseja.

Rafael
fonte

Para adicionar à resposta de David Richerby :

Se fosse verdade que nenhum algoritmo auto-modificável não pode ser modelado por algoritmos não auto-modificáveis, esses algoritmos teriam que ser executados em algo que também fosse auto-modificável. Teria que ser tartarugas até o fim.

Como mencionei no meu comentário, um algoritmo auto-modificador pode ser executado em um processador que obedece às regras de um algoritmo estático (codificado em seu design) que "informa" como executar as instruções da máquina.

Alexander - Restabelecer Monica
fonte

Eu acho que isso pode ser uma linha divisória interessante. Eu acho que alguém poderia argumentar que "a vida" é um algoritmo auto-modificável que não pode ser modelado por algoritmos não-modificáveis, mas, novamente, "a vida" normalmente não é pensada como um algoritmo.

Cort Ammon

@ CortAmmon: Se vemos a "vida" como um algoritmo, então qual é a sua entrada e a sua saída? Como se poderia provar que qualquer algoritmo equivalente (ou seja, qualquer algoritmo que produz a mesma saída quando recebe a mesma entrada) deve ser auto-modificado?

ruach

@ruakh Se eu argumentasse que a vida era um algoritmo auto-modificável, as entradas seriam em si e suas saídas seriam em si. Provar que não pode ser reduzido a um algoritmo não modificável seria mais complicado, mas acho que é uma hipótese popular. Afinal, quantas pessoas querem acreditar que podem ser reduzidas a um algoritmo que pode ser executado em um computador?

Cort Ammon

@ CortAmmon: não posso ser reduzido a um algoritmo que roda em um computador porque esse algoritmo não é mais "eu"; Eu sou mais do que minhas entradas e saídas. Mas se partimos do pressuposto de que eu sou apenas um algoritmo, adotar "o que pode ser executado em um computador" não muda nada. Re: "Se eu argumentasse que a vida era um algoritmo auto-modificável, as entradas seriam em si e suas saídas seriam em si": Nesse caso, acho que você estaria se saindo bem fora do CS, e perigosamente próximo ao crackpottery.

ruakh 4/08/16

@CortAmmon Um programa que se apresenta como entrada é justo cat. (Sem trocadilhos, mesmo que os gatos estejam vivendo coisas)

user253751