[PDF] Machine de Turing - Informatique Théorique 2 Licence 3 informatique

View - Download Machine de Turing - Informatique Théorique 2 Licence 3 informatique

Previous PDF

Next PDF

Machine de Turing

Informatique Theorique 2

Licence 3 informatique

S ebastien Verel verel@univ-littoral.fr http://www-lisic.univ-littoral.fr/ ~verel

Universite du Littoral C^ote d'Opale

Laboratoire LISIC

Equipe OSMOSE

IntroductionLangage reconnuFonction calculableIndecidabilite

Objectifs de la seance 04

Connaitre la denition d'une machine de Turing

Savoir executer une machine de Turing

Savoir denir le langage reconnu par une machine de Turing Savoir denir la fonction calculee par une machine de Turing Savoir denir une machine de Turing pour reconna^tre un langage ou calculer une fonctionConnaitre la these de Church-Turing Savoir que le probleme de l'arr^et est non calculable

Questions principales du jour :

Qu'est-ce qu'une procedure eective?

IntroductionLangage reconnuFonction calculableIndecidabilite Plan

1Introduction

2Langage reconnu

3Fonction calculable

4Indecidabilite

IntroductionLangage reconnuFonction calculableIndecidabilite

Introduction

D'apres P. Dehornoy, universite de CaenAutomate :

modele abstrayant la notion de calcul sans ecriture L est decidable par automate si pour tout motwde L, on peut repondre a la question "wappartient-il a L?" enlisantle mot et en utilisant lamemoire nie.Machine de Turing : modele analogue avec une notion plus elaboree de calcul L est decidable par automate si pour tout motwde L, on peut repondre a la question "wappartient-il a L?" enlisantle mot et en utilisant lamemoire nie mais aussi enecrivantdes informations sur unsupport illimiteVersion formalisee du calcul mental

Version formalisee du calcul au sens general

IntroductionLangage reconnuFonction calculableIndecidabilite

Bibliographie

Turing, Jean Lassegue, Les belles lettres, 2003.

IntroductionLangage reconnuFonction calculableIndecidabilite

Alan Turing

IntroductionLangage reconnuFonction calculableIndecidabilite

1912 : naissance a Londres, parents en Inde (1912-21)

1926 : entre a la Public School Sherborne

1928 : D. Hilbert renouvelle son Programme au Congres de

Bologne1931 : entre au King's College de Cambridge pour suivre des etudes de mathematiques1931 : K. Godel : sur les propositions indecidables des Principia Mathematica1933 : Hitler arrive au pouvoir, exil des intellectuels d'Allemagne et d'Europe centrale1934 : Licence de mathematiques avec mention

1935 : devient Fellow de Kibg's College

1936 : Prouve le resultat negatif de la decidabilite propose par

Hilbert. Part travailler avec A. Church et J. Von Neumann1939 : 4 septembre debut de la guerre. Entre au service GCCS

a Bletchley Park.1943 : janv. - mars, laboratoire Bell sur des questions de cryptage de la parole; renontre Shannon Commence a concevoir son projet de construire un cerveau. National Physical Laboratory pour construire un prototype d'ordinateur

1950 Publication de "computing machinery and intelligence"

1952 : Publication "La base chimique de la morphogenese"

1954 : Suicide le 7 juin par ingestion d'une pomme au cyanure

IntroductionLangage reconnuFonction calculableIndecidabilite

1939 : 4 septembre debut de la guerre. Entre au service GCCS

a Bletchley Park.1943 : janv. - mars, laboratoire Bell sur des questions de cryptage de la parole; renontre ShannonCommence a concevoir son projet de construire un cerveau. National Physical Laboratory pour construire un prototype d'ordinateur1950 Publication de "computing machinery and intelligence"

1952 : Publication "La base chimique de la morphogenese"

1954 : Suicide le 7 juin par ingestion d'une pomme au cyanure

IntroductionLangage reconnuFonction calculableIndecidabilite

Les inter^ets scientiques de M. Turing

Mathematiques pures (calculs des probabilites et statistiques, theories des nombres, theories des groupes)Logique mathematique (decidabilite, calculabilite)

Cryptologie

Construction eective des premiers ordinateurs

Morphogenese

IntroductionLangage reconnuFonction calculableIndecidabilite

Articles majeurs

1936 (24 ans) : fonde la theorie de la calculabilite,

Machine de Turing1952 : Theorie generale sur les principes de la morphogenese

1950 : Lien entre logique et biologie. Etude des processus

cognitifs par simulation informatiqueTuring se place du point de vue del'eectivite du calcul:

condition pratique de la realisation de celui-ciA. Turin, "On computable numbers, with an application to the

Entscheidungsproblem", nov 1936.

IntroductionLangage reconnuFonction calculableIndecidabilite

Articles majeurs

1936 (24 ans) : fonde la theorie de la calculabilite,

Machine de Turing1952 : Theorie generale sur les principes de la morphogenese

1950 : Lien entre logique et biologie. Etude des processus

cognitifs par simulation informatiqueTuring se place du point de vue del'eectivite du calcul:

condition pratique de la realisation de celui-ciA. Turin, "On computable numbers, with an application to the

Entscheidungsproblem", nov 1936.

IntroductionLangage reconnuFonction calculableIndecidabilite

Calculabilite

Intuition de calculable

"resultat d'une operation conduisant a la determination exacte et achevee d'un nombre"3 etats de la calculabilite

1Trouver en un nombre ni d'etapes un resultat exact et acheve

2Trouver en un nombre ni d'etapes un resultat approche a

n'importe quel degre d'approximation decide a l'avance3"incalculable" : pas moyen de trouver une approximation en

un nombre ni d'etapeNotion de fonction calculable si sa valeur pour tout nombre calculable de l'ensemble de depart est un nombre calculable IntroductionLangage reconnuFonction calculableIndecidabilite

Introduction par les langages

LangagesGrammairesProcedure eective

3Rationnelsregulieres a droite

ouA!a,A!aB,A!Automates reguliersA;B2N a2Tnis (regulieres a gauche)

2algebriquesalgebriques, non-contextuellesAutomates

ouA!a pile non-contextuelsA2N2(N[T)1contextuelles, monotonesMachine de Turing contextuels!ouA!a l'espace ;2(N[T),Aaxiomelineairement borne jj jj0recursivementcontextuelles avec eacement enumerables!Machine de Turing

2(N[T)+2(N[T)aucune contrainte

IntroductionLangage reconnuFonction calculableIndecidabilite

Automate ni

Fonction a valeur booleenne denie sur l'ensemble des mots

A: ! f0;1g

Repond a un probleme de decision :

siA(w) = 0 alorsw62LA siA(w) = 1 alorsw2LAMachine de Turing : point de vue langage, memoire innie

MT: ! f0;1g

Repond a un probleme de decision :

siMT(w) = 0 alorsw62LMT siMT(w) = 1 alorsw2LMT

Mais :

en utilisant un support inni de memorisation en plus d'un nombre ni d'etat IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

etatsab !121 234
341
444a
1 2 4 3 b a b a b a,baaba 1 IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

etatsab !121 234
341
444a
1 2 4 3 b a b a b a,baaba 2 IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

etatsab !121 234
341
444a
1 2 4 3 b a b a b a,baaba 3 IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

etatsab !121 234
341
444a
1 2 4 3 b a b a b a,baaba 1 IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

etatsab !121 234
341
444a
1 2 4 3 b a b a b a,baaba 2 IntroductionLangage reconnuFonction calculableIndecidabilite

Caracteristiques d'une machine de Turing

Support illimite de l'information : Ruban

aaba

1Machine de Turing

Etats : memoire nie,

Lecture des symboles du ruban,

Ecrituresur le rubanProgramme :

fonction de transition d'etats et de deplacement et d'ecriture IntroductionLangage reconnuFonction calculableIndecidabilite

Transition

Ancien etatSymbole luSymbole ecritMouv.Nouvel etat !accepte 1ab!1 ba!1 aaba 1baba 1 IntroductionLangage reconnuFonction calculableIndecidabilite

Transition

Ancien etatSymbole luSymbole ecritMouv.Nouvel etat !accepte 1ab!1 ba!1 aaba 1baba 1 IntroductionLangage reconnuFonction calculableIndecidabilite

Transition : Tableau a double entree

ab !1b ,!, 1a ,!, 1accepte_ /_, a/b,b/a, qq

12aaba

1Exercice 1

Executer la machine de Turing ci-dessus.

Quel est le langage reconnu par la machine?

IntroductionLangage reconnuFonction calculableIndecidabilite

Transition : Tableau a double entree

Exercice 1

Le langage reconnu est

= (a+b), l'ensemble de tous les mots. IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : M2

ab !0,!, 1,!, 2accepte

1a ,!, 1b ,!, 1, , 32a ,!, 2b ,!, 2, , 43accepterefuseaccepte

4refuseaccepteaccepte

aaabbb baabab

Exercice 2

Executer la machine de Turing ci-dessus.

Quel est le langage reconnuLM2par la machine M2?

L M2aurait-il pu ^etre reconnu a l'aide d'un automate ni? IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : M2

Exercice 2

Le langage reconnu est l'ensemble de tous les mots qui commencent et terminent par le m^eme symbole. Il peut ^etre reconnu par un automate ni. IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : M3

ab !0,!, 1refuseaccepte

1a ,!, 1b ,!, 1, , 22refuse, , 33a , , 3b , , 3,!, 0aaabbb

aaabab

Exercice 3

Executer la machine de Turing ci-dessus.

Quel est le langage reconnuLM2par la machine M3?

L M3aurait-il pu ^etre reconnu a l'aide d'un automate ni? IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : M3

Exercice 3

Le langage reconnue estLM3=fanbnjn0g.

Il ne peut pas ^etre reconnu a l'aide d'un automate ni.

Cet automate est a connaitre quasiment par coeur.

IntroductionLangage reconnuFonction calculableIndecidabilite

Denition formelle

Machine de Turing (MT)

Une machined e Turing a un ruban inni est septuplet (Q;;;;q0;B;F) ou :Qensemble ni d'etat, alphabet ni des symboles du ruban, alphabet ni des symboles d'entree,B2n symbole particulier dit "blanc"q

0etat initialFensemble des etats acceptantsrelation de transitionLa MT est deterministe si pour chaque chaque conguration, elle a

au plus une possibilite d'evolution. IntroductionLangage reconnuFonction calculableIndecidabilite

Relation de transition

Relation de transition

QQ f ;!g

Notation d'une regle :

q;!q0;0;m Predecesseur :q: etat courant de la machinesymbole lu sur le ruban

Successeur :q

0: nouvel etat de la machine

0symbole a ecrire sur le rubanmdeplacement de la t^ete de lectureRelation de transition : sous forme de table ou de diagramme

IntroductionLangage reconnuFonction calculableIndecidabilite

Notion de conguration

La conguration d'une MT decrit l'"etat general" de la machine : etat du ruban, etat courant de la machine et position de la t^ete de lecture. (f;q;p)f:IN! le rubanq2Ql'etat de la machinep2INla position sur le ruban La relation de transition permet alors de calculer chaque element de la nouvelle conguration. IntroductionLangage reconnuFonction calculableIndecidabilite

Langage reconnu

Le langage accepte parM= (Q;;;;q0;B;F) est deni par :

L(M) =fw2tels que :l'etat initial deMestq0le motwest ecrit sur le rubanla t^ete de lecture est positionnee sur la premiere lettre dewMatteint un etat acceptant deFen un nombre ni d'etape

g IntroductionLangage reconnuFonction calculableIndecidabilite

Classe de langages

Une MT s'arr^ete lorsque

elle atteint un etat nal elle ne peut plus eectuer de transition

Langage recursif

Un langage reconnu par une MT qui s'arr^ete sur tous les mots en entree est ditlangage recursifLangage recursivement enumerable Un langage reconnu par une MT qui s'arr^ete sur tous les mots du langage (et peut ne pas s'arr^eter sur les autres) est ditlangage recursivement enumerable{ engendre par une grammaire de type 0. IntroductionLangage reconnuFonction calculableIndecidabilite

Fonction calculee par une machine de Turing

Entree d'une MT :

mot inscrit sur le ruban initialement.Sortie d'une MT : mot inscrit sur le ruban lorsque la MT s'arr^ete.Machine de Turing : point de vue calcul

Fonction de

a valeur dans :

M: !Denition : Fonction calculee

Lafonction calculeepar une MTM, noteefM, est denie par :

Pour toute entreex2sur laquelleM(x) s'arr^ete,

on associe la sortiey2. Pour toute entreex2sur laquelleM(x) ne s'arr^ete pas, aucune image n'est associee ax. Pour toutx2;fM(x) =ysi et seulement siM(x) = (arr^et;y) IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple simple

ab !1b ,!, 1a ,!, 1,!, arr^etaaba

1Exercice 4

Executer la machine de Turing ci-dessus.

Decrire la fonction calculee.

IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple simple

Exercice 4

L'automate associe a tout mot ni, le mot ou les symboleaetb ont ete permute. Plus precisement, f

M4(12:::p) =0

10 2:::0 ptel que0 i=bsii=a asii=b IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : denition de machine

Exercice 5

Denir une chaine de Turing sur l'alphabetfa;b;cgqui enleve les symbolesc.

Par exemple,M(accbbca) =abba

Exercice 6

Denir une chaine de Turing sur l'alphabetfa;b;cgqui projette les mots sur l'alphabetfa;bg, autrement dit, qui "gomme" les symbolesc.

Par exemple,M(accbbca) =abba

IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : correction

Exercice 5

1 seul etat qui deplace la t^ete de lecture a droite jusqu'a la n du mot

repere par la case vide. Lors de la lecture dec, la t^ete ecrit une case vide.abc !1a ,!, 1b ,!, 1,!, 1arr^et IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : correction

Exercice 6

L'etat 1 a la m^eme fonction, excepte lors de la lecture decqui initie le sous-programme "decalage du mot d'une case a gauche". Les etats 3, 4, et 5 memorisent le symbole a recopier dans la case de gauche, l'etat 2 permet la lecture du premier symbole, enn l'etat 6 permet un repositionnnement sur le symbole suivant et l'iteration du sous-programme.abc !1a ,!, 1b ,!, 1,!, 2arr^et

2, , 3, , 4, , 5, , 13a,!, 64b,!, 65c,!, 66,!, 2

IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : calcul en unaire

Il est possible de representer les nombres entiers plus grand que 1 en ecriture unaire.

Le nombrexest represente parx"batons".

Par exemple, le nombre (en ecriture decimal) 3 est represente par :111

Exercice 7

Denir une machine de Turing qui calcule l'addition de 2 nombres ecrits en unaire qui sont separes par un seul espace. Par exemple,

3 + 2 :11111

IntroductionLangage reconnuFonction calculableIndecidabilite

Exemple : calcul en unaire

Exercice 7

De nombreuses solutions sont possibles comme toujours. Ici, le principe consiste a boucher l'espace entre les nombres et eacer le dernier baton.1 !11 ,!, 11,!, 221 ,!, 2, , 33,!, arr^et IntroductionLangage reconnuFonction calculableIndecidabilite Re exion

Questions, re

exions Pourquoi avoir deni une machine de Turing comme cela?

A-t-on deni une machine qui "peut" tout calculer?

Est-ce qu'il existe des machines plus puissantes ou qui calculent autre chose?Relisons Turing in the text

Denition : machines equivalentes

Deux machines de Turing sontequivalentes

si elles calculent la m^eme fonction. IntroductionLangage reconnuFonction calculableIndecidabilite Re exion

Questions, re

exions Pourquoi avoir deni une machine de Turing comme cela?

A-t-on deni une machine qui "peut" tout calculer?

Est-ce qu'il existe des machines plus puissantes ou qui calculent autre chose?Relisons Turing in the text

Denition : machines equivalentes

Deux machines de Turing sontequivalentes

si elles calculent la m^eme fonction. IntroductionLangage reconnuFonction calculableIndecidabilite

Imaginons

Pourquoi ne pas imaginer une machine avec 2 t^etes de lectures pour pouvoir lire plus de choses ou aller plus vite?Exercice 8 Denir une machine de Turing a 2 t^etes de lecture. Montrer que la machine a deux t^etes de lecture est equivalente a une machine de Turing a 1 t^ete de lecture. IntroductionLangage reconnuFonction calculableIndecidabilite

Imaginons : correction

Exercice 8

Une machine a deux t^etes de lecture peut se denir comme ci-dessous.quotesdbs_dbs16.pdfusesText_22

[PDF] calculabilité et complexité exercices corrigés

[PDF] fonction calculable

[PDF] langage récursif

[PDF] épaisseur atmosphère saturne

[PDF] fonction primitive récursive exercice corrigé

[PDF] théorème de godel démonstration

[PDF] codage de godel

[PDF] théorème de gödel pdf

[PDF] arithmétique de robinson

[PDF] nombre de godel

[PDF] godel dieu

[PDF] théorème d'incomplétude pour les nuls

[PDF] incomplétude définition

[PDF] introduction ? la calculabilité pdf

[PDF] indemnité prof principal 2017