Machine de Turing

Calculabilité

Introduction. 0.1 Quelques exemples. Les cours d'informatique que vous avez eu peuvent donner une impression que pour chaque probl`eme on peut trouver un

Introduction `a la calculabilit´e

Théor`eme. Toute fonction µ-récursive est calculable par une machine de Turing. 1. les fonctions primitives récursives de bases sont calculables par machine de

Introduction à la calculabilité et à la complexité

Ou encore : « Toute fonction mécaniquement calculable est Turing-calculable. » Voici donc notre définition d'algorithme : les machines de Turing. 2.4 Langages.

Cours de calculabilité et complexité

Introduction et motivations (IV). Deux situations sont possibles : (i) vous avez malheureusement renoncé `a suivre le cours de calculabilité et complexité

Calculabilité Cours 1 : machines de Turing

1 Introduction. Une machine de Turing est un objet mathématique défini en 1936 par Alan Turing

Calculabilité - Décidabilité I. Introduction II. Problèmes de décision

Comme tout langage actuel peut être compilé en assembleur il peut aussi être compilé en langage des machines de Turing. Les fonctions calculables et les

Calculabilité et complexité

Voici un nouveau livre d'introduction à la théorie des langages de la calculabilité et de langages formels que la calculabilité et la complexité.

Cours Logique et Calculabilité

Calculabilité. Ce cours est basé sur le livre de Sipser [Sip06] et le cours de Kari [Kar13]. 3.1 Introduction. Une machine de Turing est un objet

Complexité et calculabilité

3 sept. 2022 Introduction to Automata Theory Languages & Computation. ... Langages formels

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

Introduction. Langage reconnu. Fonction calculable. Indécidabilité. Objectifs de la séance 04. Connaitre la définition d'une machine de Turing.

[PDF] Introduction `a la calculabilit´e - ORBi

Référence Pierre Wolper Introduction `a la calculabilité - 2i`eme édition Dunod 2001 1 Page 2 Chapitre 1 Introduction 2

[PDF] INTRODUCTION À LA CALCULABILITÉ

22 jan 2017 · Cet ouvrage a pour vocation de résumer de façon claire l'ensemble des résul- tats fondamentaux en calculabilité en particulier en ce qui

[PDF] Introduction à la calculabilité et à la complexité - Irif

1 Introduction Dans ce cours : – Formaliser la notion de calcul : qu'est-ce qu'une « méthode effective de calcul »? Qu'est-ce qu'un algorithme ?

[PDF] Calculabilité - Irif

1 1 1 Définition de fonctions récursives primitives Dans le cadre défini dans l'introduction un prédicat P sur Nk correspond au probl`eme (U B)

(PDF) Introduction à la calculabilité Pierre Wolper - Academiaedu

1 Chapitre 1 Introduction 2 1 1 Motivation • Comprendre les limites de l'informatique • Distinguer probl` emes solubles et insolubles par des algorithmes

[PDF] Calculabilité Cours 1 : introduction et machines de Turing

Une machine de Turing universelle enti`erement mécanique a été réalisée en Lego 1 Remarquons que l'existence de fonctions non calculables implique que pour d'

[PDF] Cours Logique et Calculabilité

6 avr 2017 · 3 1 Introduction 3 5 1 Thèse de Church-Turing version physique certaines fonctions ne sont pas calculables : il n'existe pas

[PDF] Introduction `a la calculabilité - Loria

d'optimisation et complexite Conclusion Introduction `a la calculabilité 1 Motivation 2 Que signifie“calculer” ? Les automates Les machines de Turing

[PDF] Cours de calculabilité et complexité

Introduction et motivations (II) En est-il de même pour certains projets en in- formatique Y a-t-il des limites `a ce que nous

[PDF] Introduction `a la calculabilité - LACL

17 sept 2018 · 1 2 1 Les choses calculables Nous allons conduire une études théorique de la puissance de calcul des programmes informatiques

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

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

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 transitionquotesdbs_dbs45.pdfusesText_45

[PDF] indemnité prof principal 2017

[PDF] isoe prof principal

[PDF] hsa prof

[PDF] indemnite tuteur stagiaire education nationale

[PDF] prime prof principal contractuel

[PDF] evaluation anglais 6ème description physique

[PDF] indemnité prof principal agrégé terminale

[PDF] indemnités vacances éducation nationale

[PDF] enseignant contractuel vacances d'été

[PDF] entretien d'embauche la meilleure défense c'est d'être préparé

[PDF] cdi prof contractuel

[PDF] planification annuelle français secondaire 1

[PDF] planification annuelle français secondaire 3

[PDF] planification français secondaire 4

[PDF] dernier pays indépendant dans le monde

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

Machine de Turing

Informatique Theorique 2

Licence 3 informatique

Universite du Littoral C^ote d'Opale

Laboratoire LISIC

Equipe OSMOSE

Objectifs de la seance 04

Connaitre la denition d'une machine de Turing

Savoir executer une machine de Turing

Questions principales du jour :

Qu'est-ce qu'une procedure eective?

1Introduction

2Langage reconnu

3Fonction calculable

4Indecidabilite

Introduction

D'apres P. Dehornoy, universite de CaenAutomate :

Version formalisee du calcul au sens general

Bibliographie

Turing, Jean Lassegue, Les belles lettres, 2003.

Alan Turing

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

1935 : devient Fellow de Kibg's College

1936 : Prouve le resultat negatif de la decidabilite propose par

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

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

1952 : Publication "La base chimique de la morphogenese"

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

Les inter^ets scientiques de M. Turing

Cryptologie

Construction eective des premiers ordinateurs

Morphogenese

Articles majeurs

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

1950 : Lien entre logique et biologie. Etude des processus

Entscheidungsproblem", nov 1936.

Articles majeurs

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

1950 : Lien entre logique et biologie. Etude des processus

Entscheidungsproblem", nov 1936.

Calculabilite

Intuition de calculable

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

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

Introduction par les langages

LangagesGrammairesProcedure eective

3Rationnelsregulieres a droite

2algebriquesalgebriques, non-contextuellesAutomates

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

Automate ni

A: ! f0;1g

Repond a un probleme de decision :

MT: ! f0;1g

Repond a un probleme de decision :

Mais :

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats

Caracteristiques d'un automate ni

Automate ni

Etats : memoire nie,

Lecture des symboles,

Programme : fonction de transition d'etats