∑
MathTCG
#002 / 100•Space, Chance & Computation•MathTCG #402 / 500•★★★★★Légendaire•∀Logique•Concept

Machine de Turing

Période historique : 1936

Le modèle abstrait de ruban et tête de lecture incarnant mathématiquement tout calcul mécanique.

Contenu & Formulation mathématique

Définition rigoureuse
Modèle formel de calcul universel constitué d'un ruban infini subdivisé en cases, d'une tête de lecture/écriture et d'états internes gouvernés par une table de transition.
M=⟨Q,Σ,Γ,δ,q0,qaccept,qreject⟩,δ:Q×Γ→Q×Γ×{L,R}M = \langle Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject} \rangle, \quad \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}

Genèse & Portée historique

Conçue par Alan Turing en 1936 pour répondre au problème de la décision (Entscheidungsproblem) de Hilbert, la machine de Turing manipule des symboles sur un ruban infini selon une table de transitions finie. La thèse de Church-Turing stipule que toute fonction effectivement calculable par un algorithme quelconque peut être exécutée par une telle machine.

En 1936, à seulement 24 ans, Turing formalise le concept d'algorithme et de calcul mécanique universel, démontrant l'existence de problèmes indécidables tels que l'indécidabilité du problème de l'arrêt.

« Un ruban infini, une tête de lecture et des états discrets : l'essence mécanique de toute pensée algorithmique. »

Filiations & Relations conceptuelles (3)

Prérequis indispensable pour#401

Problème P contre NP

Les classes P et NP sont définies formellement sur une machine de Turing.

Établi / Formulé par#005

Alan Turing

Modèle formel abstrait de calculabilité universelle imaginé par Alan Turing en 1936.

Repose sur le concept#125

Algorithme

Formalisation mathématique universelle de la notion d'algorithme et de calcul mécanique.

Objet de collection MathTCG

#402
★★★★★Légendaire
∀

Machine de Turing

Logique•CONCEPT

Modèle formel de calcul universel constitué d'un ruban infini subdivisé en cases, d'une tête de lecture/écriture et d'états internes gouvernés par une table de transition.

M=⟨Q,Σ,Γ,δ,q0,qaccept,qreject⟩,δ:Q×Γ→Q×Γ×{L,R}M = \langle Q, \Sigma, \Gamma, \delta, q_0, q_{accept}, q_{reject} \rangle, \quad \delta : Q \times \Gamma \to Q \times \Gamma \times \{L, R\}
1936

Dans l'édition physique et numérique de MathTCG, cette carte appartient à l'extension Space, Chance & Computation.

Extension : Space, Chance & Computation (#002 / 100)
Numéro global MathTCG : MathTCG #402 / 500
Rareté officielle : Légendaire (★★★★★)
Domaine théorique : Logique
Identifiant pérenne : machine-de-turing
Consulter mon classeurExplorer tout le recueil
AccueilClasseurCodexBoostersÉchangesProfil