L'approche par le bas de la machine consiste à explorer les opérations élémentaires que peut faire une machine. On commence en situation prélogique où il n'y a pas de négation et donc où il n'y a pas d'état rejetant, ni de réponse négative.
Il y a deux modes de fonctionnement, le mode énumératif et le mode prédicatif. Les énumérateurs énumèrent tous les mots du langage. Les prédicats prennent comme argument un mot et lance un calcul. Si le calcul s'arrête alors le mots fait partie du langage. Et si le calcul ne s'arrète jamais alors le mot ne fait pas partie du langage.
Historiquement, c'est la machine de Turing qui fait référence pour définir la calculabilité.
C'est un modèle abstrait de machine, un ordinateur, conçu par Alan Turing, mathématicien et cryptologue anglais, en 1936. On en présente une version en mode prédicatif prélogique.
La machine utilise un alphabet `A` comprenant au moins 2 caractères dont le caractère blanc.
La machine possède un ruban indéfini comprenant des cases numérotées en partant de `0` qui contiennent chacune un caractère.
La machine possède un pointeur pointant initialement sur la case n°`0` du ruban, pouvant lire ou écrire un caractère sur la case pointés et pouvant se déplacer de case en case.
La machine possède `n` états, `E={1,2,3,...,n}`
La machine possède un programme déclaratif qui la définit complètement. C'est une liste d'instructions qui prédéfinit le comportement de la machine. Le langage de programmation de la machine de Turing comprend un seul type d'instruction sous forme de quintuplet :
`(e_1, x_1,x_2,s,e_2)`
Où les paramètres sont définit comme suit :
`e_1` : Numéro d'état de départ de la transition, `e_1 in E`
`x_1` : Caractère lu, `x_1 in A`
`x_2` : Caractère écrit, `x_2 in A`
`s` : Déplacement, `s in {"gauche", "droite"}`
`e_1` : Numéro d'état de fin de la transition, `e_1 in E`
Cette instruction décrit un comportement possible de la machine lorsque celle-ci est dans l'état `e_1` : Si le caractère sous le pointeur est `x_1`, alors le remplacer par le caractère `y_2` et déplacer le pointeur d'une case dans la direction `s` si possible (car si on le pointeur pointe sur la case n°0 le déplacement à gauche n'aura pas d'effet et la position du pointeur restera inchangé pointant sur la case n°0), puis mettre la machine dans l'état `e_2`. Cette opération s'appelle une transition.
A l'état initial la machine se trouve à l'état `1` et le mot à tester se trouve sur le ruban à partir de la case n°0, toutes les autres cases du ruban contiennent le caractère blanc.
On démarre la machine. La machine s'arrête lorsqu'il n'y a pas de transition possible. Si la machine s'arrête, alors le mot fait partie du langage. Si la machine ne s'arrête jamais, alors le mot ne fait pas partie du langage.
La machine est dite déterministe si les instructions ne proposent à chaque fois qu'au plus une transition possible. Elle est dites non-déterministe si dans certaines situations elle propose plusieurs transitions possibles. Cette qualité d'être non-déterministe n'apporte pas de pouvoir de calculabilité supplémentaire. Car une machine de Turing non-déterministe est rendu déterministe simplement en dupliquant la machine à chaque alternative rencontrée.
---- 22 janvier 2023 ----