probleme de l'arrêt

[Lvrk]

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
-----

[invite73192618]

- return 0 si M¨

(I don't think so) Une machine de Turing "ordinaire" soit s'arrête après un temps fini, soit ne s'arrête pas. Ici tu définis une machine de Turing qui soit s'arrête après un temps fini, soit s'arrête après un temps infini. Ce n'est donc pas une machine de Turing ordinaire, et la démonstration par l'absurde n'est donc pas valide.

[invite73192618]

A la réflexion tu postules ce que fait M2, ce qui est valide dans le cadre d'une démonstration par l'absurde. Je retire donc ma réponse précédente.

Question: pourquoi M2 prend deux paramètres M et m alors que M et M3 semblent n'en prendre qu'un?

[minushabens]

je ne comprends pas comment de l'existence de M2 on déduit celle de M3.

[A voir en vidéo sur Futura]