Bonjour,
J'ai fais une preuve du problème de l'arrêt qui ne correspond pas à celle de mon professeur. Je doute donc de sa véracité même si elle me parait correct, j'aimerais ainsi vous demander si mon raisonnement est correct ou pas du tout.
Merci, voici ma preuve (¨ signifie que la machine sarrette, ^ siginifie qu'elle diverge):
Proposition 2.2: On s’intéresse désormais au problème de l’arrêt qui prouve l’existence de problèmes indécidables.
On assimile le code d’une machine de Turing et la machine de Turing par la notation M.
On essaye de démontrer qu’il n’existe pas de machine de Turing M2 qui décide si la machine de Turing M boucle pour un mot m.
On pose alors par l’absurde qu’il existe une tel machine :
(1). On créer alors M2 qui prend en argument une machine de Turing M et un mot m tel que M2:
- return 1 si M(m)^
- return 0 si M(m)¨
On définit ensuite :
(2). On créer alors M3 qui prend son propre code en argument tel que M3:
- return 1 si M^
- return 0 si M¨
On s’imagine alors que M3 se prend en argument tel que M3(M3). Ainsi par définition,
M3 return 1 si M3^. On aboutit alors à une contradiction. M3 ne peut pas exister donc M2 ne peut pas exister non plus. Le problème de l’arret est indécidable par une Machine de Turing.
Merci
-----
Envoyé par Lvrk 