Les algorithmes et le debut de l'invention de la machine: La Machine de Turing

De nos jours, beaucoup de developpeurs dìse lancent dans le coding de tout type (mobile, web, desktop etc..) et tout le temps on parle de Algorithm et Algorithm au point ou certains meme insconsciement, font des algorithmes sans pour autant savoir comment est venu l'idée des algorithmes et comment a été pensé et inventé l'ordinateur.

Pour la petite histoire, les peripheries digitales ou mieux les ordinateurs que vous utilisez de nos jours , partent d'une idée d'abstraction, celui qui a pensé l'ordinateur comme il est aujourdhui n'a meme pas vu cet ordinateur, il est resté dans son monde imaginaire et ses abstractions, pourtant, dans toutes les facultés d'informatiques, sont oeuvre continut d'etre enseigné aux étudiants, car si on ne reconstruit pas la genèse et la base de la création des machines, les apprenants n'auront pas assez d'immagination pour savoir d'ou on est partit et ou on en est actuellement et comment l'ameliorer.

Alain Turing c'est un mathematicien (je vous ai toujours dit que tout part de la mathematique ou des mathematiques) qui dans les années 1930, eut l'idée d'une bastraction d'une machine : La machine de turing. c'est quoi la machine de turing?

Une machine de Turing est un ordinateur simple (une machine conceptuelle pas réelle) composé d'une bande infinie partitionnée en carrés et d'une tête de lecture/écriture qui se déplace le long de la bande. Une table d'états, parfois appelée table d'instructions, précise le fonctionnement de la machine. Chaque étape consiste à rechercher dans la table d'instructions une correspondance entre l'état actuel et le symbole actuellement sur la bande sous la tête. Pour chaque correspondance, le tableau spécifie une action, une direction à suivre et un nouvel état. Trois actions sont autorisées : imprimer un symbole sur la bande, effacer le symbole déjà présent sur la bande ou ne rien faire. La direction est soit déplacer vers la gauche, déplacer vers la droite ou ne pas bouger. La machine est initialisée en chargeant une bande, qui peut être vierge ou déjà marquée, et en positionnant la tête sur la position de départ, généralement le début de la bande. 

Le fonctionnement de la machine de turing suit les étapes suivantes:

1. Recherchez dans le tableau une correspondance entre l'état actuel et le symbole sous la tête de lecture.

2. Effectuez l'action indiquée pour cette combinaison : ne rien faire, imprimer un symbole ou effacer un symbole.

3. Déplacez la tête de bande vers la gauche ou vers la droite d'un carré si spécifié dans le tableau.

4. Définissez l'état actuel sur le nouvel état lu dans le tableau et répétez à partir de l'étape 1.

Aussi simple que soit cette machine, elle peut implémenter n'importe quel algorithme ; mais personne n'a parlé d'efficacité ou de facilité de mise en œuvre. La thèse de Church-Turing va encore plus loin et affirme que la définition même de l'algorithme est celle qui peut être implémentée par une machine de Turing. Autrement dit, un problème peut être résolu par un algorithme si (et seulement si) il peut être résolu par une machine de Turing. Notez que cette affirmation est une thèse et non un théorème. Une thèse est quelque chose que l'on croit, avec raison, être vraie, mais un théorème est quelque chose qui s'est avéré vrai.

Son premier exemple est une machine qui remplit la bande avec le motif « 0 1 0 1 0 … ». La machine imprime un 0, se déplace deux fois vers la droite pour laisser un espace vide, imprime un 1, puis se déplace deux fois vers la droite, répéter à l'infini.

La bande est initialement vide, ce qui signifie qu'il n'y a pas d'entrée dans cette machine. La tête commence à la première case et l'état initial est 0. Pour effectuer un mouvement, nous avons besoin de la table d'instructions qui nous indique quelle est la prochaine étape. Les instructions pour cette machine sont dans dans la table suivante (state=etat, Symbol=Simbole, Print=Ecrire, Move=Deplacer, New State = Nouveau etat)::

La machine démarre à l'état 0 avec une bande vierge. La recherche dans le tableau de cette configuration produit une correspondance avec « 0 vide ». Dans ce cas, le tableau indique d'imprimer un 0, de se déplacer vers la droite et de régler la machine sur l'état 1.

L'étape suivante recherche l'état 1 et tout ce qui se trouve sous la tête de bande, qui est un blanc. Il existe une correspondance pour cette configuration. La correspondance indique d'imprimer un blanc, de se déplacer vers la droite et de régler la machine sur l'état 2. L'état 2 correspond, imprime un 1, se déplace vers la droite et passe à l'état 3. Enfin, l'état 3 correspond, imprime un blanc, se déplace vers la droite et revient à l'état 0. À ce stade, le processus se répète indéfiniment car il n'y a pas d'état d'arrêt. Nous allons explorer d'autres exemples de machines de Turing ci-dessous.

Il n'est pas immédiatement évident ou, d'ailleurs, évident dans tous les sens du terme, qu'une machine de Turing incarne le concept d'algorithme. En fait, Turing lui-même croyait que la thèse de Church-Turing ne se prêtait pas à une preuve mathématique. 

Voila en quelque sorte comment est née l'idée derrière les algorithmes et leur application, successivement, Alain turing dans sa machine imaginaire, demontrera que cette machine peut etre universelle, en anglais on perle de "Universal Turing Machine", dans ce cas la machine est capable de resoudre n'importe quel algorithme y compris meme une autre machine de turing, en fait c'est ce concept qui fait que de nos jours, pour juger si un langage de programmation peut resoudre tous les problemes computationels, on doit absolument demontrer qu'il est est une machine de turing , on parle de "Turing Complete" en anglais, vous aurez beaucoup lu des livres ou des tutoriels quand ils abordent un langage par exemple java, javascript, c# etc.. vous disent que ces langages sont Turing complet car pour etre Turing complet, il faut etre à mesure de resoudre tous les algorithmes que peut resoudre une machnie de turing.

Voilà le debut de l'invention de la machine du moins de l'ordinateur, je parles la des machines qu'on a aujourdhui, fort de ce constat, un autre electronicien va s'appuyer sur ces recherches mathematiques de alain Turing, pour mettre sur pied la mère de ce qui constitut l'architecture d'un ordinateur de nos jours, il s'agit de l'architecture de Von Neumann du nom de son auteur

en fait, quand on parle de l'architecture d'un ordinateur, on parle des élements présent dans l'image ci haut donc la CPU(le processeur) est l'éelement fondamentale, en fait vous verrez que cette image a une similitude avec la machine imaginaire de alain turain et son fonctionnement, quand nous écrivons un logiciel, le compilateur le traduit en code machine donc les bits 10...01...01. etc.. qui sont en fait des instructions qui seront passées à la CPU pour etre executer 1 à 1, ces instructions sont d'abord chargé en mémoire RAM, puis passé à la CPU qui en utilisant ses registres c'est à dire des zone mémoires temporaires à la CPU ou il peut stocker des données, les élabore 1 à 1 avant de les envoyer aux peripheries de sorties, ici la CPU est en quelque sorte la tete de lecture de la machine de alain turing, qui doit aller pecher les instructions en mémoire qui ici remplace la table des instructions de alain turing et les elaborer en faisant exactement ce qui a été decrit ci haut par la machine de turing, voilà comment est partit l'ordinateur que nous utilisons de nos jours et la mise sur pied des algorithmes.

J'esperes que cette toute petite notion, meme si theorique vous a appris une autre facette du monde du coding

happy coding

---

---

Share

Comments (0)

Leave A Comment

Your Name:
Comment: