Machines de Turing

La machine de Turing est un dispositif abstrait doté d'un contrôle fini et d'un ruban illimité qui saisit la notion intuitive d'un algorithme, et elle sert de modèle de référence standard pour ce qui est calculable.

Definition

Une machine de Turing se compose d'un ensemble fini d'états et d'un ruban de cellules infini dans les deux sens ; à chaque étape, elle lit le symbole sous sa tête, écrit un symbole, se déplace à gauche ou à droite, et change d'état selon une fonction de transition, s'arrêtant lorsqu'elle entre dans un état d'acceptation ou de rejet.

Scope

Ce sujet couvre la définition et le fonctionnement des machines de Turing, les configurations et les calculs, la robustesse du modèle face à des variantes telles que les rubans multiples et le non-déterminisme, la machine de Turing universelle capable de simuler n'importe quelle autre, et l'encodage des machines en tant que données, ce qui rend possibles les arguments d'autoréférence et d'indécidabilité.

Core questions

• Comment un simple dispositif de lecture-écriture-déplacement capture-t-il la notion complète d'algorithme ?
• Pourquoi de nombreuses variantes du modèle calculent-elles exactement les mêmes fonctions ?
• Qu'est-ce qu'une machine universelle, et pourquoi son existence est-elle significative ?
• Comment l'encodage des machines sous forme de chaînes de caractères permet-il des preuves sur leur propre comportement ?

Key theories

Universalité

Il existe une unique machine de Turing universelle qui, étant donné un encodage de n'importe quelle machine et de son entrée, simule le calcul de cette machine, préfigurant l'ordinateur à programme enregistré dans lequel les programmes sont eux-mêmes des données.

Robustesse du modèle

L'ajout de rubans, de têtes multiples, de rubans bidimensionnels ou de non-déterminisme ne modifie pas la classe des fonctions calculables, de sorte que la machine de Turing capture une notion de calcul qui est insensible à de tels détails.

Clinical relevance

La machine de Turing est l'étalon à l'aune duquel la puissance des langages de programmation et des architectures informatiques est mesurée, et la machine universelle est l'ancêtre conceptuel de l'ordinateur à programme enregistré à usage général sur lequel repose toute l'informatique moderne.

History

Turing a introduit ses machines en 1936 pour préciser ce que signifie pour un nombre d'être calculable et pour résoudre le problème de la décision de Hilbert. L'idée d'une machine universelle, dans laquelle une description stockée contrôle un dispositif général, a influencé la conception par von Neumann de l'ordinateur à programme enregistré une décennie plus tard.

Key figures

• Alan Turing
• Emil Post
• John von Neumann

Seminal works

• turing1937
• sipser2013

Frequently asked questions

Une machine de Turing est-elle un véritable ordinateur ?

Non, c'est une abstraction mathématique dotée d'un ruban illimité et sans souci de vitesse ou de coût de mémoire. Sa valeur est conceptuelle : elle détermine précisément ce qui peut être calculé en principe, et toute tâche qu'un ordinateur réel peut effectuer, une machine de Turing peut également l'accomplir avec suffisamment de ruban et de temps.

Pourquoi la machine de Turing universelle est-elle importante ?

Elle montre qu'une machine fixe peut exécuter le comportement de n'importe quelle autre lorsqu'on lui fournit la description de cette machine en entrée. C'est le fondement théorique de l'ordinateur programmable à usage général, où le logiciel est une donnée fournie à un unique dispositif d'interprétation plutôt qu'un recâblage pour chaque tâche.