Problème d'arrêt pour la machine à turir fixe et une entrée fixe

Question

On sait que le problème d'arrêt est indéchérable même lorsque nous réparons la machine de Turing $ m $ ou l'entrée $ w $ .

Et si nous corrigions la machine et l'entrée?C'est-à-dire que c'est décidé pour chaque machine à turing fixe $ m_0 $ et chaque entrée fixe $ w_0 $ que $ M_0 $ Arrêtez-vous sur $ W_0 $ Entrée?

Answer 1

On sait que le problème d'arrêt est indéchérable même lorsque nous réparons la machine de Turing $ m $ ou l'entrée $ w $ .

Vous devez faire plus attention à cette déclaration. Ce n'est pas vrai pour une machine à turing fixe $ M $ que le problème d'arrêt $ \ text {halt} _m > (Décider de l'entrée $ w $ si $ m $ s'arrête sur $ w $ ) est indécitable. Par exemple, si $ M $ est une machine qui s'arrête toujours, nous pouvons facilement décider $ \ text {halt} _m $ juste en émettant "oui".

Qu'est-ce que vous vouliez probablement dire est les faits suivants, qui sont vrais:

1. il existe une machine de Turing $ M $ tel que le problème $ \ TEXTE {HALT} _M $ (Décider de l'entrée $ W $ Si $ M $ s'arrête sur $ w $ ) est indécitable.

2. pour tous les mots mots $ w $ , le problème $ \ text { Halt} _w $ (décidant de l'entrée $ m $ si $ M $ s'arrête sur < span class="math-conteneur"> $ w $ ) est indécitable.

en particulier pour le fait 1, nous pouvons prendre $ M $ pour être la machine de Turing universelle.

Et si nous corrigions la machine et l'entrée? C'est-à-dire que c'est décidé pour chaque machine à turing fixe $ m_0 $ et chaque entrée fixe $ w_0 $ que < SPAN CLASS="MATH-CONTENEUR"> $ M_0 $ Arrêtez-vous sur $ W_0 $ Entrée?

Oui, le problème devient trivialement décidable. Définir la langue $ \ text {halt} _ {m_0, w_0} $ Pour être le problème de décider si $ M_0 $ s'arrête sur $ w_0 $ . Mais remarquez que ce problème n'a plus d'introuvable que la réponse dépend de la réponse, comme les deux choses que la réponse pourrait dépendre de ( $ m_0 $ et $ w_0 $ ) sont maintenant fixés, c'est-à-dire une partie de la définition de la langue, pas une partie de l'entrée. Cela signifie que la réponse est simplement "oui" ou "non". Nous pouvons donc décider de manière triviale de ce problème à l'aide d'un programme qui dit toujours "oui" ou un programme qui dit toujours "non".

Ceci est un piège commun sur la suppicidité: Il n'est utile que de demander si un problème est décidé ou non lorsque le nombre d'entrées possibles est infini. s'il n'y a que de nombreuses entrées possibles, alors Tous les problèmes deviennent décidables. Vous avez demandé si un problème avec seulement 1 entrée possible (l'entrée vide) est décritable et la réponse à celle-ci est toujours oui.