La machine de Turing.

Bonjour,

Je voudrais, pour ceux éventuellement intéressés, présenter l'ancêtre théorique des ordinateurs.

Cette machine a été conçue par le logicien britannique Alan Turing.

Vous trouverez son principe dans le graphique ci-dessous que j'ai créé pour l'occasion.

Il est remarquable qu'avec si peu de types de commandes on puisse faire executer n'importe quel traitement à une information donnée.

Il est encore plus étonnant que le langage des ordinateurs modernes ne soit pas LOGIQUEMENT plus puissant que celui de cette machine !

Bien sûr, pour faire executer un simple calcul par cette machine il pourrait se faire qu'on attende pendant des années le résultat qu'un ordinateur moderne obtient en une fraction de seconde.

Mais l'intérêt de la machine de Turing se situe au niveau de la logique. Ainsi l'indécidabilité de certains problèmes logiques a été démontrée au moyen de ces machines, tel, par exemple, que le problème de l'équivalence des mots dans la théorie des calculs associatifs (Indécidabilité du problème des mots dans les semi-groupes de Thue).

Mais Alan Turing est allé beaucoup plus loin et est vraiment considéré comme le père des ordinateurs. En effet il a démontré qu'il est possible de coder le "programme" de sa machine sur le ruban lui-même. C'est bien ce qui existe sur les ordinateurs dont la mémoire contient aussi bien le programme que les données.

Quand vous aurez sous les yeux le graphique joint, pourriez vous me dire ce qui se passerait si on remplace sur la ligne q1 le S (Stop) par la commande q0 ?

Précision : On voit 6 bâtonnets qui représentent le nombre 5 car le premier bâtonnet à gauche désigne le 0 qu'il faut bien distinguer d'un "blanc".

Le programme montré ajoute donc 1 à 5 ce qui done donc 6 représenté par 7 bâtonnets.

Cordialement.

P.S. J'ai corrigé des fautes de frappe dans le graphique aussi j'ajoute ce graphique corrigé.