[PDF] Machine de Turing =? ?-recursif

View - Download Machine de Turing =? ?-recursif

Previous PDF

Next PDF

Agrégation 2018/2019

Machine de Turing=)-recursif

Leçons :912;913

Références :WOLPER,Introduction à la calculabilité(p.135) [?] et CARTON, Langages formels, calculabilité et complexité(p.185) [?] et

LESESVRE-MONTAGNON-LE BARBENCHON-PIERRON,131

développements pour l"oral(p. 687) [?]

Prérequis :-Savoir coder les fonctions de base en-récursif (voir appendice sur lesfonctions -récursives)

Introduction :

On va montrer que toute fonction calculable par une machine de Turing est une fonction-

récursive, c"est un étape pour valider la thèse de Church qui nous dit que toute fonction calculable

par une procédure effective est en fait une fonction calculable par une machine de Turing. En effet, on va pouvoir remplacer machine de Turing par-calcul ou fonctions-récursives quand on

aura prouver que ces trois modèles de calcul sont équivalents. On prouve ici une implication de

cette équivalence.Théorème 1. Tout fonction (totale) calculable par une machine de Turing est calculable par une fonction (totale)-récursive.Démonstration. SoitM= (Q;;;;q0;F;#)une machine de Turing déterministe à ruban

bi-infini qui boucle sur ces états finals1telle que sinest écrit en unaire sur son ruban, à la fin de

l"exécution, il y a écritf(n)en unaire.

On représente :

l"ensem bledes états Qpar des entiersf0;:::;mgoù l"état initialq0= 0 l"alphab etde lecture =f1g2 l"alphabet d"écriture =f0;:::;k1goùk=jjet le symbole blanc#est représenté par 0.

On représente la configuration

#:::##g j:::g 1g 0d 0d 1:::d i##::: par le triplet d"entiers(g;q;d)oùq2 f0;:::;mgetg;dsont les entiers en basekdes mots avant et après la tête de lecture deM.3 g=g

0:::gjk=jX

p=0g pkpetd=d

0:::dik=iX

p=0d pkp La fonction1Fest primitive récursive car c"est une somme finie d"indicatrice. La fonctionest primitive récursive car elle est aussi à support fini.1

. pour permettre à la fonctionconfig_suivanted"être totale, car toutes les fonctions primitives récursives sont

totales

2. carnest écrit en unaire

3. avec bit de poids faible au niveau de la tête de lectureENS Rennes - Université de Rennes 1 1 Pierre Le Barbenchon

Agrégation 2018/2019On va maintenant décrire le fonctionnement de la machine de Turing par des fonctions

primitives récursives et-récursives et donc écrire la fonctionfsous la forme d"une fonction -récursive. init:8 >:N!N3 n7!

0;0;n1X

p=0k p

La fonctioninitest primitive récursive car la somme et l"exponentiation sont primitives récursives.4

config_suivante:8 :N 3!N3 (g;q;d)7!( (gk+;q0;d==k)sidir=! (g==k;q0;g0+k(+ (d==k)k))sidir= pour(q;d0) = (q0;;dir).5 La fonctionconfig_suivanteest primitive récursive car on utilise que des fonctions primitives récursives (mod,==,+,). config:8 :N 3N!N3 (~x;k)7!( ~xsik= 0 config_suivante(config(~x;k1))sinon La fonctionconfigest primitive récursive en utilisant le principe de récursion. temps_arret:( N3!N ~x7!i(1F(32(config(~x;i)))) La fonctiontemps_arretest-récursive car utilise une minimisation non bornée. somme:( N!N p7!(i6p)(ki> p)

La fonctionsommeest primitive récursive, elle permet de retrouver l"entier en unaire qui correspond

au nombre en basek.

Ainsi on pose la fonction

f(n) =somme(31(config(init(n);temps_arret(init(n))))) La fonctionconfig(init(n);temps_arret(init(n)))renvoie une configuration, il faut ensuite récupérer legetdcorrespondant d"où l"utilisation de projections. On a donc réussi à simuler la machine de Turing avec une fonction-récursive.4

. Elle représente le ruban au début de l"exécution de la machine car la tête de lecture est sur la première case

du mot (doncg= 0), dans l"état initialq0= 0et il y anfois le symbole1sur le ruban donc représenté par

n1X p=0k p en basek.

5. oùg0=gmodketd0=dmodkENS Rennes - Université de Rennes 1 2 Pierre Le Barbenchon

Agrégation 2018/2019

Remarques :C"est en fait une équivalence de modèle de calcul et on prouve l"autre sens par induction, en

simulant les fonctions de base des fonctions-récursives par une machine de Turing. Le symbole#est représenté par0ce qui coïncide bien avec le fait que###:::#|{z} rg j:::g0 s"écritg= jX l=1g lkl rX l=1

0ki+l. Autrement dit, cela ne change rien d"ajouter des 0 à gauche (ou

à droite si on pense àd) des nombres que l"on écrit en basek.Astuces de l"agrégatif :

les notations, ici ce qui facilite c"est que l"on code tout en unaire pour l"entrée et sortie de la

machine de Turing.

Questions possibles :-

Justifier que l"on peut considérer une machine de Turing qui vérifie les hypothèses de

l"énoncé (déterminisme, ruban bi-infini, unaire, unique état initial et final, boucle sur l"état

final). Montrer que toute fonction-récursive est calculable par une machine de Turing en explicitant les machines de Turing. Montrer que les fonctions arithmétiques utilisées dans ce développement sont primitives récursives. Mon trerque la compa raisonest un prédicat primitif récursif. Montrer que la conditionnelle est une fonction primitif récursif,i.e.siPest un prédicat primitif récursif etf;gdeux fonctions primitives récursives, alors la fonction qui anassocie ifP(n)thenf(n)elseg(n)est primitive récursive.

Mon trerque la minim isationb ornéeest une fonc tionprimitiv erécursiv e.ENS Rennes - Université de Rennes 1 3 Pierre Le Barbenchon

quotesdbs_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