bonjours les amis, je n'y connais pas grand chose en math, et malheureusement je constate que les matheux sont en général pas très doués pour expliquer en français ce qu'ils expriment généralement par des symboles, or j'aurait besoin d'aide pour comprendre le principe d'une machine de Turing car je ne saisi pas le concept n'étant pas familier des formules mathématiques..
salut,
on peut voir une machine de turing comme un automate fini déterministe (AFD) à mémoire et qui peut modifer sa fonction de transition
as tu lu cette page ?
http://fr.wikipedia.org/wiki/Automate_fini
j'ai lu wikipedia mais je ne comprend pas certains truc
Automate c'est une machine qui fontionne toute seule, ça je comprend
Finit, je suppose que ça fait référence au fait que le nombre de caractères possibles à écrire est limité
Deterministe, je penses que ça fait référence à la programmation, le fait qu'ils soit programmé pour executer une tâche..
à memoire je suppose que cela parle de la bande de papier.
Mais ce que je ne comprend pas c'est la fonction de transition, et l'utilité intellectuelle de l'appareil.
On en parle dans certains cours d'informatique mais j'ai du mal avec les histoires de machines théoriques.. Je n'arrive pas à visualiser dans ma tête le fonctionnement de la machine de turing.. ni son but. Qu'est-ce qu'elle est censée démontrer?
En gros, ça donne ça :
Tu as un ruban (une bande de papier si tu préfères) que tu imagines infini des deux côtés (càd que tu peut écrire aussi loin que tu veux vers la droite, et aussi vers la gauche). Ton ruban est séparé en cases, et dans chaque case tu peux écrire un caractère (on peut fixer l'alphabet à {0,1}, càd que tu n'écris que des 0 et des 1 sur ton ruban). Ça te fait la partie "mémoire".
Ensuite, tu as un ensemble de règles pour faire marcher ta machine. Pour les définir, il faut d'abord définir des états (imaginons que tu aies par exemple sur ton ruban, au début, deux nombres écrits en binaires, et que tu veux faire leur somme : les états pourront être par exemple l'état "je suis en train de lire le premier nombre", "je suis en train de lire le second nombre", "je suis en train de les ajouter", "j'ai fini". Mais c'est qu'un exemple, et tout ce qu'on veut c'est un nombre fini d'états qu'on numérote). Maintenant tes règles sont de la forme suivante : si je suis dans l'état E et que je lis la lettre L sur le ruban, alors je remplace L par L', puis je décale mon ruban vers la gauche/droite.
Voilà, c'est tout ce que peut faire une machine de Turing. Techniquement parlant, l'ensemble des règles forme un AFD mais ce n'est pas très important si ce que tu veux est visualiser le fonctionnement.
Ensuite le but : la Machine de Turing, qui est un modèle mathématique, modélise le fonctionnement d'un ordinateur réel. Le fait que cette modélisation soit exacte n'est pas prouvable, et est l'hypothèse sur laquelle se fonde l'informatique théorique ("Thèse de Church-Turing"). Ensuite, le but de l'informatique théorique est d'étudier, via le modèle de Machine de Turing, ce qu'un ordinateur est capable de faire (en imaginant des algorithmes par exemple) et ce qu'il n'est pas capable de faire (démonstrations d'indécidabilité, bornes inférieures de complexité, etc...).
NB: Mon message contient beaucoup d'imprécisions volontaires pour espérer être clair, j'ai caché un certain nombre de détail (ceci s'adresse à toi comme à un spécialiste en train de s'arracher les cheveux au vu des raccourcis employés...).
d'accord je comprend le fonctionnement, mais j'ai du mal a saisir l'utilité. Peutêtre est-ce une question de génération, mais il me paraît beaucoup plus simple pour comprendre le fonctionnement d'un ordinateur, d'imaginer un ordinateur plutôt qu'une machine qui écrit sur du papier..
Un ordinateur est effectivement un outil qui utilise un programme pour écrire sur une mémoire, mais à quoi cela peut-il bien servir de comparer une machine qui existe (l'ordinateur) et donc on peut connaître les limites par l'expérience, avec une machine qui n'existe pas (machine de turing) dont on ne peut imaginer les limites ou no-limit qu'a condition d'utiliser un ordinateur pour la simuler?
En fait c'est comme si on comparait un ordinateur reel avec une mémoire finie, avec un ordinateur théorique avec une mémoire infinie.. Ca sert à quoi?
A voir jusqu'où peut fonctionner un programme tout seul si on ne lui impose aucune contrainte physique? A quoi cela sert-il d'imaginer une machine capable de calculer une opperation dont le résultat n'existe pas ou est infinit?
C'est juste un petit problème d'histoire de l'informatique:Envoyé par nidhalg
"Alan Mathison Turing (23 juin 1912 - 7 juin 1954) est un mathématicien britannique, auteur de l'article fondateur de la science informatique[1] qui allait donner le coup d'envoi à la création des calculateurs universels programmables (ordinateurs). Il y présente sa machine de Turing, le premier calculateur universel programmable, et invente les concepts de programmation et de programme."
merci du rappel , je confond souvent Turing et Von Neumann.
Non tu fais une erreur ici. Et la réponse suivante est également fausse :
Si effectivement la Machine de Turing a un intérêt historique indéniable, elle a également un intérêt actuellement ! Quand tu dis qu'on "peut connaître les limites [de l'ordinateur] par l'expérience", c'est tout simplement faux. On ne peut pas, par exemple, dire qu'un ordinateur est incapable de résoudre un problème donné efficacement juste parce que tous les programmes qu'on a écrits mettent énormément de temps. Ce qu'il faut pour établir un tel résultat, c'est le prouver mathématiquement. Et c'est justement l'utilité de la machine de Turing : on peut faire des preuves mathématiques, parfaitement rigoureuses, qu'un ordinateur ne pourra jamais résoudre tel ou tel problème efficacement. Et donc pour avoir des résultats sur la Machine de Turing, on ne la simule pas sur un ordinateur ! On fait des preuves.
Un bon exemple, simple, de telles preuves est le résultat fondateur de Turing dans son papier de 1936 intitulé "On Computable Numbers, with an Application to the Entscheidungsproblem" ("Sur les nombres calculables, avec une application au problème de la décision"). Turing y prouve son célèbre résultat : le problème de l'arrêt est indécidable. Qu'est-ce que ça signifie ? Cela veut dire qu'il est impossible de créer un programme qui nous dirait si tel ou tel programme va boucler ou non. Pour reprendre les mots de Gérard Berry lors de sa leçon inaugurale au Collège de France, "il n'existe pas de débuggueur universel". Et qu'est-ce qu'une preuve d'un tel résultat ? On ne peut pas se contenter de dire "on n'a jamais réussi à écrire un tel programme". On montre que si un tel programme existe, cela aboutit à une contradiction. Je donne une idée de la preuve ci-dessous.
Pour conclure, cet exemple montre l'utilité du modèle mathématique de l'ordinateur qu'on appelle Machine de Turing. Cela nous évite de chercher en vain à programmer un utilitaire pour trouver les programmes qui bouclent. Et il y a une pléiade de tels résultats d'impossibilité qui ont été prouvés depuis ce premier résultat de Turing.
----
Idée de la preuve du théorème de l'arrêt :
On va supposer que nos programmes et nos entrées sont écrit à l'aide de trois caractères, "0", "1" et ",". SI on veut n'avoir que des "0" et des "1", il suffit de remplacer "0" par "00", "1" par "11" et "," par "01" par exemple. Si on a une chaine de caractères c1 et une autre c2, on note c1,c2 la chaine consistant en c1, puis le caractère ",", puis c2. Un programme est représenté par une chaine de caractères (son "code" écrit dans notre langage de programmation préféré), et on peut supposer qu'il ne contient aucun caractère ",".
Supposons qu'il existe un programme P tel que P(f,x)=1 si le programme f lancé sur l'entrée x s'arrête, et P(f,x)=0 si le programme boucle à l'infini. On construit le programme Q suivant : si Q est lancé avec l'entrée x, Q commence par tester si x possède une virgule. Si c'est le cas, il s'arrête et renvoie 0. Sinon, il appelle P sur l'entrée "x,x". Si P(x,x)=1, alors Q lance une boucle infinie (par ex., "while true do print(je boucle) done"). Sinon, Q s'arrête et renvoie 0.
En pseudo code, voilà Q :
Entrée : x
SI (x contient une virgule) ALORS RENVOYER 0;
SINON
__SI P(x,x)=1 ALORS
____TANT QUE 0=0 FAIRE
______PRINT("Je boucle\n")
____FIN TANT QUE
__SINON RENVOYER 0
Maintenant examinons ce que donne Q appliqué à lui-même : Q(Q). Q ne contient pas de virgule, donc on teste P(Q,Q). Si P(Q,Q)=1, càd si Q(Q) s'arrête, alors on boucle à l'infini. Et si Q(Q) ne s'arrête pas, alors on s'arrête et on renvoie 0.
En conclusion, Q(Q) s'arrête si et seulement si Q(Q) boucle à l'infini. Il y a donc une contradiction !
P.S.: Preuve librement inspirée de Wikipédia...
