Chaque algorithme auto-modifiable peut-il être modélisé par un algorithme non auto-modifiable?

Si nous avons un programme informatique arbitraire qui peut modifier ses instructions, est-il possible de simuler ce programme avec un programme qui ne peut pas modifier ses instructions?

Éditer:

Je suis nouveau sur stackexchange, donc je ne sais pas si je suis autorisé à poser une NOUVELLE question ici, mais voici: Ok donc la preuve que c'est possible est en fait très simple comme vous l'avez montré. Maintenant, je me demande: y a-t-il des problèmes pour lesquels il est plus efficace (et dans quelle mesure) d'utiliser l'algorithme d'auto-modification le plus efficace pour résoudre le problème, par rapport à l'algorithme de non-auto-modification le plus efficace équivalent en entrée-sortie?

computability computation-models turing-completeness church-turing-thesis user56834
la source

Réponses:

Oui c'est possible. Vous pouvez simuler le programme en utilisant un interpréteur pour la langue dans laquelle il est écrit. Maintenant, le programme (l'interpréteur) est fixe et ce qui était un programme auto-modifiable est maintenant les données de l'interpréteur.

En particulier, vous pourriez parfaitement avoir une machine Turing universelle qui a permis au TM qu'il simule de modifier sa propre description. (La description de la machine simulée, je veux dire; pas l'UTM.)

David Richerby
la source

Vous n'avez même pas besoin de l'interprète hypothétique. Un CPU exécutant votre algorithme d'auto-modification est lui-même une machine qui exécute un algorithme fixe (qui dicte comment il exécute les instructions)

Alexander - Reinstate Monica

@AlexanderMomchliov il existe des processeurs qui peuvent modifier des parties de leur jeu d'instructions à la volée (mais oui, l'idée est la même - la partie programmable est des données, le microcontrôleur qui l'exécute est l'interprète - bien qu'elle pointe vers un microcontrôleur à l'intérieur d'une cellule FPGA pourrait être délicat)

John Dvorak

pour répondre: "vous pourriez parfaitement avoir une machine de Turing universelle qui a permis au TM qu'il simule de modifier sa propre description." Je pense: cela ne pose-t-il pas la question? parce que maintenant vous devez encore prouver que la MT qui est simulée peut réellement modéliser l'algorithme d'auto-modification, non? Il pourrait toujours être le cas qu'il existe un programme d'auto-modification qui n'est PAS lui-même une machine de Turing, nous ne pouvons donc pas utiliser l'intégralité de Turing pour montrer qu'il peut être simulé, car l'intégralité de Turing concerne la simulation des MT et l'auto-modification algo n'est pas une MT.

user56834

@ Programmer2134 Cela ne pose pas du tout la question. Quel que soit le processeur sur lequel vous pensez exécuter votre programme d'auto-modification, je peux simuler ce processeur sur une machine Turing. Pour l'expliquer d'une manière différente, le programme initial est une séquence finie d'instructions, dont certaines modifient le programme lui-même. Chacune des instructions peut être simulée par l'UTM, chacune des modifications peut être simulée et chacune des instructions modifiées peut être simulée. Il n'y a rien, à n'importe quelle étape de ce processus, qui dépasse la puissance des machines Turing.

David Richerby

Tout modèle de calcul complet de Turing qui n'a pas de code de modification (ou "code") sert de preuve de cette déclaration. Je ne sais pas que des modèles standard (TM, RAM, ...) n'ont modifier le code, donc nous ne pas regarder trop loin.

Pour obtenir un programme dans le langage que vous avez en tête, compilez à partir d'un tel modèle (et assurez-vous que le compilateur n'introduit pas de modification de code).

C'est, bien sûr, un argument existentiel: il existe un programme équivalent. Mais nous savons également qu'il existe des compilateurs récursifs (c'est-à-dire calculables) entre deux langages Turing-complete, c'est ainsi que vous obtenez un programme de la forme (lisez: dans la langue) que vous voulez.

Raphael
la source

Pour compléter la réponse de David Richerby :

S'il était vrai qu'aucun algorithme auto-modifiable ne peut être modélisé par des algorithmes non auto-modifiables, alors ces algorithmes devraient être exécutés sur quelque chose qui est également auto-modifiable. Il faudrait que ce soit des tortues tout le long.

Comme je l'ai mentionné dans mon commentaire, un algorithme auto-modifiable peut être exécuté sur un processeur qui respecte lui-même les règles d'un algorithme statique (codé dans sa conception) qui lui "indique" comment exécuter les instructions de la machine.

Alexander - Rétablir Monica
la source

Je pense que cela pourrait être une ligne de démarcation intéressante. Je pense que l'on pourrait soutenir que la "vie" est un algortihm auto-modifiable qui ne peut pas être modélisé par des algorithmes non auto-modifiables, mais là encore, la "vie" n'est généralement pas considérée comme un algorithme.

Cort Ammon

@CortAmmon: Si nous considérons la "vie" comme un algorithme, alors quelle est son entrée et sa sortie? Comment pourrait-on prouver que tout algorithme équivalent (c'est-à-dire tout algorithme qui produit la même sortie quand on lui donne la même entrée) doit s'auto-modifier?

ruakh

@ruakh Si je soutenais que la vie était un algorithme auto-modifiant, les entrées seraient elles-mêmes et leurs sorties seraient elles-mêmes. Prouver qu'il ne peut pas être réduit à un algorithme non auto-modifiant serait plus délicat, mais je pense que c'est une hypothèse populaire. Après tout, combien de personnes veulent croire qu'elles peuvent être réduites à un algorithme pouvant s'exécuter sur un ordinateur?

Cort Ammon

@CortAmmon: Je ne peux pas être réduit à un algorithme qui s'exécute sur un ordinateur car cet algorithme n'est plus "moi"; Je suis plus que mes entrées et sorties. Mais si nous partons de l'hypothèse que je ne suis qu'un algorithme, le fait de "claquer sur un ordinateur" ne change rien. Re: "Si je soutenais que la vie était un algorithme auto-modifiant, les entrées seraient elles-mêmes et leurs sorties seraient elles-mêmes": dans ce cas, je pense que vous seriez bien en dehors de CS, et dangereusement proche de la poterie.

ruakh

@CortAmmon Un programme qui sort lui-même donné en entrée est juste cat. (Pas de jeu de mots, même si les chats sont des êtres vivants)

user253751