 |
Forum |
|
|
Réagissez
dans les forums
de JDN Développeurs
|
Les plus curieux en informatique, et plus précisément en
langages de programmation, seront déjà tombés sur le terme
"Turing complet" pour désigner un problème ou un langage.
L'explication habituelle est qu'un langage est considéré comme
Turing complet s'il peut émuler une machine de Turing, et
si une machine de Turing peut émuler le langage. Partant de
là, il faut pour comprendre l'ensemble remonter à l'origine
: la machine de Turing.
Une
machine de Turing est une machine abstraite, ou théorique,
inventée par Alan Turing (1912 - 1954) en 1936, pour servir
de modèle idéal lors d'un calcul mathématique. Par extension,
tous les ordinateurs modernes sont conçus selon le principe
de fonctionnement qu'elle présente.
En pratique,
il s'agit d'un simple système de bande divisé en cases,
d'une tête de lecture/écriture (un trombone pourra être utilisé
pour la représenter), un registre d'état qui mémorise l'état
en court de la machine, et une table d'actions qui précise
les interventions à réaliser pour la tête. Chaque case contient
un symbole issu d'un alphabet connu (et contenant un symbole
"vide", ou "0"). Cet alphabet se limite généralement à 0 et
1 - pour rester simple - et réalise des traitements binaires.
La plupart des composants de cette machine sont finis : l'alphabet
dispose d'un nombre donné de symboles ; les déplacements de
la tête se font case par case, et vers la gauche ou vers la
droite ; le registre peut contenir un nombre fixe d'états
; et la table d'actions finit également par être vide (auquel
cas la machine s'arrête, n'ayant plus d'actions à traiter).
En revanche, la bande est supposée être infinie - une
machine abstraite idéale, donc.
Si l'on exclut l'infinité de la bande, il est possible de
très simplement réaliser une telle machine - mais l'on obtient
alors une machine Turing équivalente, et non Turing complète.
Étant donné que l'infinité de la bande, donc par extension
de l'espace de stockage/espace mémoire, est impossible à atteindre,
on considère la plupart du temps que Turing équivalent
est synonyme de Turing complet.
Basiquement, donc, une machine de Turing peut additionner
et soustraire des entiers (0 et 1), et ce, sans limite de
stockage. Décrire un langage ou un problème comme Turing
complet n'est donc pas une mesure de l'utilité ou de nombre
de fonctionnalités de celui-ci, mais un moyen de faire abstraction
des détails d'implémentation du langage, pour n'en garder
que les fonctionnalités essentielles.
En définitive, tout langage moderne peut se targuer d'être
Turing équivalent, donc Turing complet si l'on assouplit
la règle du stockage infini. Un langage Turing incomplet,
selon cette acception, ne traiterait pas les données qu'on
lui fournit, aurait une liste infinie d'actions, ou aurait
un seul symbole dans son alphabet... Ainsi, SQL n'est pas
considéré comme Turing complet, mais des extensions, comme
PL/SQL, le sont.
|
Forum |
|
|
Réagissez
dans les forums
de JDN Développeurs
|
La machine de Turing servit, lors de sa création, à montrer
la faisabilité d'un automate programmable capable de calculer
toute fonction calculable. Les machines modernes sont toutes
des machines de Turing, selon cette acception. Cette dénomination
n'est pas négligeable pour autant, car elle forme la base
de toute machine : même les plus compliquées peuvent être
émulées par la machine de Turing - si l'on exclue le temps
requis pour la préparer et la programmer.
|
