Les définitions de la machine de Turing indiquent qu'il est interdit à quiconque de lire/modifier sa table d'instructions (programme). Exactement, Turing Machine n'a pas accès à son propre programme.Tableau d'instructions de la machine de Turing
Quels avantages peut-on obtenir si l'on pouvait affaiblir cette restriction? Si une machine peut analyser et/ou modifier son programme. Cela étendrait-il la classe des tâches turing-calculables?
La machine de Turing peut déjà implémenter une autre machine de Turing et modifier ses règles, par exemple, pour prendre en entrée un programme modifiable. En particulier, la machine de Turing peut calculer n'importe quelle fonction calculable. Il pourrait en théorie implémenter un interpréteur Lisp, qui aurait des macros, un code «auto-modifing», etc.
Donc, la réponse est NO. Rappelez-vous, personne, et je veux dire absolument aucune personne nulle part, jamais, a effectivement besoin d'une machine de Turing, bien que sans doute des zillions de simulateurs ont été écrits. (Je ne vais pas l'admettre, mais en tant qu'étudiant de premier cycle j'ai peut-être fait quelque chose comme ça ...) C'est juste quelque chose sur lequel diverses preuves importantes sont basées.
Plus complètement: Il y a une différence entre une "Machine de Turing Universelle" et une "Machine de Turing" .Une machine de Turing ordinaire a un jeu de règles câblé, donc ne peut pas être auto-modifiable. Universal Turing Machine, qui lit son jeu de règles sur la même bande que celle qu'il utilise pour les E/S, et qui a la capacité de modifier cet ensemble de règles.Si l'UTM a la capacité de recharger (reboot) cet ensemble de règles modifié à partir d'une bande, En fait, déjà auto-modifiable
Est-ce que quelqu'un sait pourquoi cela aurait été downvoted? Je suis intéressé à entendre ce que j'ai dit qui pourrait être considéré comme erroné, mais la rétrogradation sans commentaire ne fournit pas beaucoup d'informations à moi-même ou à quelqu'un d'autre qui pourrait lire. – stevegt
Ah, je vois, merci – Bubba88
C'est une bonne question, sans vraiment se rappeler le point de la MT, vous avez réussi à poser la question centrale derrière toute son existence: que peut-elle calculer. – DigitalRoss
J'étais presque sûr qu'il n'y a aucun avantage de calcul dans ce mo dification, mais votre réponse a été très claire. – Bubba88