Machine de Turing

Calculabilité

Une fois que nous aurons une notion précise de fonction calculable la définition précédente deviendra aussi rigoureuse. 1.1 Fonctions récursives primitives.

Séance 5 : Fonctions récursives et machine de Turing

Définition V.1.2.2- Fonction calculable nous définissons dans cette partie la première classe des fonctions calculables. On obtiendra.

Calculabilité

Church-Turing et C est appelé l'ensemble des fonctions calculables. L'une des fonction est-elle calculable ou non calculable ?

Calculabilité et décidabilité

La thèse de Church 1 postule que tous ces modèles de calcul sont équivalents : une fonction calculable pour un modèle l'est pour un.

Toute fonction calculable est récursive

Théorème 1. 0 Soit f une fonction ?? ? ?? où ? et ? sont des alphabets. Si f est calculable par machine de. Turing

Initiation à la calculabilité

Jan 27 2017 nous pourrions alors définir toute fonction calculable. Hélas

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

Turin ”On computable numbers

Machine de Turing =? ?-recursif

Savoir coder les fonctions de base en µ-récursif (voir appendice sur les On va montrer que toute fonction calculable par une machine de Turing est une ...

TD 05 – Réels Castor affairé

https://pageperso.lis-lab.fr/~kevin.perrot/documents/2018/calculabilite/TD05_18.pdf

La fonction du castor affairé nest pas calculable

On dit que cette fonction est calculable si il existe une machine de Turing unaire à un seul ruban bi-infini

[PDF] Calculabilité - Irif

La classe de fonctions calculables par machines de Tu- ring est égale `a la classe de fonctions calculables par un algorithme quelconque Pour prouver les deux

[PDF] Toute fonction calculable est récursive

Toute fonction calculable est récursive Manon Ruffini Théorème 1 0 Soit f une fonction ?? ? ?? où ? et ? sont des alphabets Si f est calculable par

[PDF] Séance 5 : Fonctions récursives et machine de Turing

Définition V 1 2 2- Fonction calculable Le problème (UB) est décidable si et seulement si ?B est calculable V 1 2 2 Fonctions récursives primitives

[PDF] Fonctions calculables et récursives - Léo Gayral

On dit que f est calculable si il existe une telle machine qui sur toute entrée ?n? (n ? I) termine avec ?f(n)? sur la gauche du ruban Par induction

[PDF] Calculabilité

Les fonctions peuvent être simples : l'addition ou la multiplication de deux entiers naturels ; ou plus compliquées : étant donné un entier naturel quelle est

[PDF] Cours de calculabilité et complexité

Fonctions calculable par les machines de Turing On peut réénoncé la th`ese de Church-Turing en termes de calcul de fonctions : Les fonctions calculables

[PDF] Initiation à la calculabilité - HAL

27 jan 2017 · On appelle fonction Turing-calculable les fonctions partielles (on peut avoir la valeur spéciale ?) ainsi définies Pour pouvoir définir des

[PDF] Éléments de Théorie de la Calculabilité

Il doit exister une fonction calculable f telle que f(n) est un code pour le n-ième algorithme qui calcule la n-ième fonction calculable fn Supposons

[PDF] Introduction `a la calculabilité - LACL

17 sept 2018 · Nous montrons dans cette section que les fonctions primitives récursives sont exac- tement les fonctions calculables par un programme structuré

[PDF] Initiation à la calculabilité - [Verimag]

24 fév 2013 · On appelle fonction Turing-calculable les fonctions partielles (on peut avoir la valeur spéciale ?) ainsi définies Pour pouvoir définir des

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

[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

[PDF] isoe prof principal

[PDF] hsa prof

[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