Une machine de Turing (TM) peut-elle décider si le problème d'arrêt s'applique à toutes les MT?

9

Sur ce site, il existe de nombreuses variantes sur la question de savoir si les MT peuvent décider du problème d'arrêt, que ce soit pour toutes les autres MT ou certains sous-ensembles. Cette question est quelque peu différente.

Il demande si le fait que le problème d'arrêt s'applique à toutes les MT peut être décidé par une MT. Je crois que la réponse est non et je souhaite vérifier mon raisonnement.

Définissez le langage méta-stopper comme le langage composé de MT qui décident si un TM s'arrête. $L_{MH}$

L_{M H} = {M : \forall_{M^{'}, w} M (M^{'}, w) accepts if M^{'} (w) halts, rejects otherwise}

$L_{MH} = \{ M : \forall_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\}$

$L_{MH}= \emptyset$ raison du problème d'arrêt.

Ainsi, la question du titre énonce plus précisément: est-il décidable si ? $L_{MH} = \emptyset$

Selon le théorème de Rice, il est indécidable si une re langue est vide.
Dans les deux cas, si est ou non re, il est indécidable que . $L_{MH}$ $L_{MH} = \emptyset$
Par conséquent, il est indécidable que . $L_{MH} = \emptyset$

Cela prouve qu'une MT ne peut pas décider si le problème d'arrêt s'applique à toutes les MT.

Ma compréhension est-elle correcte?

MISE À JOUR: J'essaie de montrer qu'une MT ne peut pas "prouver le problème d'arrêt" pour une définition de "prouver" qui semble intuitivement correcte. Voici une illustration de la raison pour laquelle je pense que c'est correct.

Nous pouvons créer un TM qui génère de la manière suivante. La TM prend un tuple . Il simule pour les itérations d' . Si accepte toutes les qui s'arrêtent et rejette toutes les autres, alors accepte . Sinon, il rejette si décide incorrectement ou ne s'arrête pas. $M_{MH}$ $L_{MH}$ $(M_i,M_j,w_k,steps)$ $M_i(M_j, w_k)$ $steps$ $M_i$ $(M_j, w_k)$ $M_{MH}$ $M_i$ $M_i$ $M_i$

$M_{MH}$ ne s'arrête pas, car il doit évaluer un nombre infini de paires pour chaque . De plus, tous les ne s'arrêteront pas. ne pourra accepter ou rejeter aucun car il ne saura pas par simulation que tous les ne s'arrêteront pas. Ainsi, le langage qu'il définit n'est ni ré ni décidable. $M_i$ $M_i$ $M_{MH}$ $M_i$ $M_i$

$M_{MH}$ capture mon intuition de ce que je pense que cela signifie pour une MT de prouver le problème d'arrêt. D'autres suggestions, telles que rejetant tous les ou sortant une preuve connue donnent à une connaissance préalable que le problème d'arrêt s'applique à tous les . Cela ne peut pas compter comme prouvant quelque chose puisque la prémisse du est la conclusion qu'il prouve, et est donc circulaire. $M_{MH}$ $M_i$ $M_{MH}$ $M_i$ $M_{MH}$ $M_{MH}$

computability turing-machines undecidability halting-problem yters
la source

3

Votre solution n'aide pas. Un problème sans paramètre est toujours décidable, soit par une machine de Turing qui sort toujours OUI, soit par une machine qui sort toujours NON. Votre argumentation ne fonctionne tout simplement pas, malheureusement. Le véritable analogue du théorème de Gödel est le théorème de Rice.

Yuval Filmus

5

"Il demande si le fait que le problème d'arrêt s'applique à toutes les MT peut être décidé par une MT." - cette requête n'a pas de sens car le problème d'arrêt ne "s'applique" pas à un ensemble de MT. Au moins, je ne sais pas ce que ça veut dire.

Raphael

4

Vous avez mal compris le théorème de Rice. Le théorème de Rice déclare (dans un cas particulier) que le langage est indécidable. Il n'indique pas que est indécidable; en fait, est décidable.

{M : L (M) = \emptyset}

$\{ M : L(M) = \emptyset \}$

\emptyset

$\emptyset$

\emptyset

$\emptyset$

Yuval Filmus

7

Je pense que le malentendu réside dans la signification de l'expression "décider X". Formellement, X doit être un prédicat sur les chaînes, puis une machine décidant que X est celle qui, en entrée s, affiche la valeur de vérité de X ( s ). Quel est le prédicat dans votre cas? Quelle est sa contribution et quand est-ce vrai?

Yuval Filmus

5

La question est une erreur de catégorie. La décidabilité est une propriété des langages (ensembles de chaînes), et non des propositions mathématiques. Toute question du formulaire " est-il décidable?" où n'est pas un ensemble de chaînes n'a tout simplement aucun sens.

X

$X$

X

$X$

David Richerby

5

Autre point de vue: soit une formalisation de la déclaration " " dans ZFC ; (trivialement) nous avons: $\varphi$ $L_{MH} = \emptyset$

l'ensemble est décidable; $P = \{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\}$
vous pouvez également construire un TM qui énumère les preuves dans ZFC et s'arrête s'il trouve une preuve de ou une preuve de ; clairement s'arrête; $M$ $\varphi$ $\neg \varphi$ $M$
l'ensemble est indécidable $\{ M \mid M \mbox{ decides } P \}$

Vor
la source

19

Le langage des machines de Turing décidant du problème d'arrêt est décidable. Une machine de Turing qui décide qu'elle produit simplement toujours NO.

En d'autres termes, est décidable. $\emptyset$

Vous pourriez être confondu avec le fait que le langage des machines de Turing dont le langage est vide est indécidable. Autrement dit, il n'y a pas de machine de Turing qui, sur l'entrée , décide si . $T$ $L(T) = \emptyset$

Yuval Filmus
la source

7

La langue vide est décidable. Faites avec.

Yuval Filmus

15

Le langage des machines de Turing décidant du problème d'arrêt est vide. La langue vide est décidable. Par conséquent, le langage des machines de Turing décidant du problème d'arrêt est décidable.

Yuval Filmus

1

La question est de savoir si une MT peut décider du langage des machines de Turing pour décider que le problème d'arrêt est vide. Une MT ne peut pas faire cela comme je l'ai montré ci-dessus.

yters

1

@yters Demandez-vous si une MT peut prouver que cette langue est vide? Il peut facilement le faire, en sortant simplement une preuve connue existante.

user253751

3

Qu'est-ce que cela signifie même pour une MT de prouver quelque chose?

Yuval Filmus

2

Vous comprenez mal le théorème de Rice.

Dans ce contexte, le théorème de Rice dit que vous ne pouvez pas décider du problème "T décide-t-il de la langue vide?".

Votre problème n'est pas de décider si une machine de Turing arbitraire décide de la langue vide. Votre problème est de savoir s'il existe ou non un M qui décide de la langue vide.

Et ces M existent. Vous pouvez faire encore mieux que cela: vous pouvez réellement construire un tel M et fournir une preuve qu'il décide du langage vide.

Le problème général n'étant pas décidable ne signifie pas que vous ne pouvez pas résoudre des cas spécifiques. En fait, par le dispositif habituel d'énumération de toutes les preuves, il existe une machine de turing qui:

Accepte chaque machine de turing pour laquelle il existe une preuve qu'il décide de la langue vide
Rejette toute machine de turing pour laquelle il existe une preuve qu'elle ne décide pas de la langue vide
Ne s'arrête pas si cela ne peut pas être prouvé de toute façon.

la source

1

La définition de la décidabilité de Wikipedia :

Un langage récursif est un langage formel pour lequel il existe une machine de Turing qui, lorsqu'elle est présentée avec une chaîne d'entrée finie , s'arrête et accepte si la chaîne est dans la langue, et s'arrête et rejette dans le cas contraire. La machine de Turing s'arrête toujours: elle est connue comme décideur et déciderait du langage récursif.

En d'autres termes, il est décidable que s'il existe une machine de Turing qui décide de toutes les chaînes d'entrée. Il est indécidable si pour chaque machine Turing, il ne décide pas de toutes les chaînes d'entrée, ce qui signifie qu'il ne peut en décider aucune ou certaines chaînes, mais il y en a au moins une (mais pratiquement au moins infinie) qu'il ne peut pas décider.

Dans votre cas, la machine triviale de Turing ne décide pas pour chaque entrée , si , mais elle sait précisément si . $L$ $L = \emptyset$ $L_{MH} = \emptyset$

user23013
la source

Une machine de Turing (TM) peut-elle décider si le problème d'arrêt s'applique à toutes les MT?

Réponses: