Modèle abstrait de calcul composé d'une bande infinie (ou non bornée) divisée en cellules, d'une tête de lecture/écriture se déplaçant à gauche ou à droite, d'un ensemble fini d'états et d'une fonction de transition qui associe (état courant, symbole courant) à (état suivant, symbole à écrire, déplacement de la tête).

Principe

Le calcul est modélisé comme des transitions d'états discrets opérant sur une bande symbolique à espace de travail non borné ; la complexité et la décidabilité s'étudient en comptant pas et usages de bande en fonction de la taille de l'entrée.

Démonstration

Une machine de Turing déterministe simple décidant la parité sur une entrée unaire : lire les symboles, basculer un état interne de parité à chaque '1' et s'arrêter dans un état d'acceptation/rejet selon la parité après avoir parcouru l'entrée et les blancs.

Mauvaise application

Assimiler l'arrêt abstrait d'une machine de Turing au temps d'exécution pratique sur matériel réel, ou considérer les calculs non terminants comme des résultats valides plutôt que des exécutions indéfinies.

Conséquence

Constitue la base de la théorie de la calculabilité : elle définit problèmes décidable vs indécidables, et par raffinements de complexité fournit des classes (temps/espace) ordonnant les besoins en ressources algorithmiques.

Inversion

Un automate fini ne dispose que d'une mémoire de travail finie et ne peut simuler une bande non bornée ; il reconnaît une classe de langages strictement plus petite (réguliers) que celle des langages calculables par une machine de Turing.

Limite

Les machines de Turing déterministes à une seule bande sont un modèle fondamental ; des variantes nondéterministes, multi‑bandes ou à oracle étendent les capacités ou modifient la comptabilisation des ressources. Les modèles quantiques ou probabilistes se situent en dehors de la définition déterministe classique.

Tension sémantique

Tension avec les langages de programmation et architectures de haut niveau : la machine de Turing est un dispositif théorique minimal centré sur la calculabilité et les ressources, non sur des aspects pratiques comme les facteurs constants, le parallélisme ou les jeux d'instructions.

Synthèse

Une machine de Turing est un dispositif abstrait minimal qui formalise le calcul en transitions d'états étiquetées sur une bande symbolique non bornée, servant de modèle standard pour définir la calculabilité et le calcul à ressources limitées.