Machine de Turing universelle

jma · April 2019

Bonjour

Je pense avoir compris ce qu'est une machine de Turing mais je ne comprends lorsque cette machine est universelle. Pourriez-vous m'expliquer de manière vulgarisatrice mais aussi formellement ce concept ?

Merci d'avance.
Cordialement.

Poirot · April 2019

Une machine de Turing universelle $M$ est une machine de Turing capable de "faire tourner" n'importe quelle autre machine de Turing quand on lui donne en entrée. Une fois fixé le langage utilisé, on encode sous la forme $\#N$ une machine de Turing $N$ dans ce langage (typiquement en binaire). Plus précisément, on encode toute la table d'action de $N$. Alors si on donne à $M$ l'entrée $(\#N, e)$, celle-ci va ressortir la valeur $N(e)$.

jma · April 2019

Bonjour,

D'abord merci pour ta réponse.

Pour la partie intuitive, la machine universelle est capable de lire n'importe quelle machine bien définie ? Pour la machine universelle, tout ce qui fait une machine de Turing est une sorte de "variable" et peut reproduire son comportement ?

Pour la partiie formelle, je dois réfléchir à ce que tu viens d'écrire et, je pense que j'aurais des questions.

Cordialement.

jma · April 2019

Je voulais dire la machine M a une "variable" qui prend la definition de n'importe quelle machiine de Turing et reproduit son comportement ?
Cordialement.

Poirot · April 2019

Dans l'idée c'est ça, mais on ne parle pas de "variable" ici. C'est juste qu'une machine de Turing universelle qui lit l'encodage d'une machine de Turing en entrée, suivi d'une "entrée usuelle" simulera effectivement la lecture de cette "entrée usuelle" par la machine encodée. On peut faire ça plus formellement, mais ça devient vite lourd. Si tu veux les détails techniques ce n'est pas moi qui vais pouvoir t'aider :-D Tu ferais mieux de consulter des ouvrages de référence.

jma · April 2019

Ok merci.
Cordialement.

jma · May 2019

Bonjour,
Après avoir essayé de comprendre le premier chapitre du livre de Perifel ayant pour titre "Complexité algorithmique" (en accès libre sur internet) j'ai compris qu'une machine de Turing est dédiée à un calcul et un seul défini par sa fonction/table de transition. Une machine de Turing universelle est capable d'encoder n'importe quelle fonction de transition et d'entrée d'une machine de Turing et de la simuler.
Le formalisme et l'aspect pédagogique du livre, que j'ai cité, ne me convient pas pour l'instant d'où une éternelle question : connaissez-vous une ressources plus simple pour aborder ce sujet ?
Merci d'avance pour vos réponses.
Cordialement.

Math Coss · May 2019

Je dirai même plus : le livre de Sylvain Perifel intitulé Complexité algorithmique (Ellipses, 2014) et (pourtant) en accès libre sur internet.

jma · May 2019

@Math Coss : merci pour ces précisions. Chacun pourra voir la difficulté du texte et pourra d'autant plus me conseiller.
Cordialement.

jma · June 2019

Bonjour,

En combinant les livres de Sylvain Perifel dont le lien hypertexte est dans le post de Math Coss et du document de travail http://theory.cs.princeton.edu/complexity/book.pdf du livre de S. Arora, B. Barak (2009) "Computational Complexity : A Modern Approach", Cambridge University Press, j'arrive à m'en tirer. Maintenant, il faut faire quelques exercices de plus pour confirmer.

Cordialement.

Machine de Turing universelle

Réponses

Bonjour!

Catégories

In this Discussion

Qui est en ligne 34