Embed Size (px)
Citation preview
I.A. Session 2009/2010
E.P.S.I. Bordeaux – C.S.I.I – 2ème Année – Cours n°2
Définition• Définition de Minsky :
« Construction de programmes informatiques qui s’adonnent à des tâches qui sont, pour l’instant, accomplies de façon plus satisfaisantes par des êtres humains, car elles demandent des processus mentaux de haut niveau tels que : l’apprentissage perceptuel, l’organisation de la mémoire et le raisonnement critique. »
Alan Turing• Article fondateur de la discipline :
« Computing Machinery and Intelligence » (Mind, Octobre 1950)
• Principaux champs de recherche : – Calculabilité– Décryptage– Travaux sur les premiers ordinateurs– Morphogénèse (biomathématiques)
Machine de Turing• Modèle abstrait de fonctionnement des
appareils mécaniques de calcul (ordinateurs).• But : donner une définition précise au concept
d’algorithme.• Ce modèle est toujours utilisé pour résoudre
les problèmes de complexité algorithmique et de calculabilité.
Machine de Turing• Une machine de Turing est constituée des éléments suivants :
– une bande infinie, décomposée en cellules au sein desquelles peuvent être stockés des caractères
– une tête de lecture/écriture, pouvant : • lire et modifier le caractère stocké dans la cellule correspondant à la position
courante de la tête (le caractère courant)• se déplacer d’une cellule vers la gauche ou vers la droite (modifier la position
courante)– un ensemble fini d’états internes permettant de conditionner le
fonctionnement de la machine – une table de transitions indiquant, pour chaque couple (état interne,
caractère courant) les nouvelles valeurs pour ce couple, ainsi que le déplacement de la tête de lecture/écriture.
• Dans la table de transitions, chaque couple est donc associé à un triplet: (état interne[nouveau], caractère[nouveau], déplacement)
Machine de Turing• Une machine de Turing fonctionne sur le principe suivant :
– la bande est initialisée avec la séquence de caractères correspondant aux données d’entrées.
– la tête de lecture/écriture est positionnées sur la première cellule de la bande, et l’état interne est positionné à sa valeur initiale (par exemple 1).
– tant que le couple courant (état interne, caractère courant) est présent dans la table de transitions, le triplet (état interne[nouveau], caractère[nouveau], déplacement) est utilisé pour mettre à jour l’état interne, le caractère courant, puis le déplacement de la tête de lecture/écriture est effectué.
– lorsqu’est rencontré un couple (état interne, caractère courant) non recensé dans la table de transitions, la machine s’arrête et la séquence de caractères stockée à ce moment-là sur la bande est considérée comme le résultat du traitement.
Exemple
Machine de Turing universelle• Une machine de Turing est caractérisée par :
– Sa logique de fonctionnement,– Le codage de ses entrées / sorties,– La table de transitions décrivant son fonctionnement
• La machine de Turing est une abstraction d’un automate modifiable
• Une machine de Turing universelle est une machine de Turing dont le programme fait partie des entrées de la machine.
• i.e. : La table de transition est fixe, les conditions de fonctionnement sont entièrement imposées par les données d’entrées.
Intérêt• Elle donnent une base théorique aux notions
de décidabilité et de complexité.• Elle permettent de donner un cadre précis à la
notion jusque là informelle d’algorithme.
Test de Turing• Répondre à la question : les machines
peuvent-elles penser ?• Création d’un test appelé « jeu de
l’imitation »• Principe :
– Mettre en confrontation verbale un humain avec un ordinateur et un autre humain à l’aveugle.
– Si l’homme qui engage les conversation ne peut pas déterminer qui est l’homme et qui est l’ordinateur, alors le test est réussi.
Applications• Bots de conversation (ex : ELIZA)
• Autre modalité du test : Captcha (acronyme de : « Completely Automated Public Turing test to Tell Computers and Humans Apart »)
“We are continually faced with a series of great opportunities brilliantly disguised as insoluble problems.”
John W. Gardner
Authors:Ophir Paz ([email protected] )Geoffroy Vincens ([email protected])
