Une machine de Turing peut-elle décider du langage

Laissez

Il semble que la même technique utilisée pour montrer que $\{A \mid A \text{ is a DFA and } L(A)=\emptyset\}$ devrait également fonctionner ici.

Par marquage, vous entendez probablement une analyse d'accessibilité - à la recherche d'un chemin allant de l'état initial à un état acceptant. En effet, la langue d'un DFA est vide si ce chemin n'existe pas.

Commençons par un exemple expliquant pourquoi cela échoue dans les MT. Considérons une MT qui, en , ignore son entrée, mais écrit un sur sa bande, déplace la tête vers la droite et passe à l'état q 1 , puis en q 1, elle ignore à nouveau l'entrée, écrit a , déplace la tête vers la gauche et va à q 2 . Dans q 2 , s'il lit a , alors il écrit a , déplace la tête vers la droite et revient à q 1 .$q_0$$a$$q_1$$q_1$$a$$q_2$$q_2$$a$$a$$q_1$

C'est, la machine écrit juste et alterne entre deux états ( q 1 et q 2 ) et a toujours deux à côté d' un « s sur la bande.$a$$q_1$$q_2$$a$

Nous ajoutons maintenant une transition de qui, lors de la lecture de b, passe à un état d'acceptation et s'arrête.$q_2$$b$

La langue de cette machine est vide. En effet, la course est toujours bloquée dans la boucle et n'atteindra jamais l'état d'acceptation. Pourtant, il existe une voie étatique vers un état acceptant. Alors qu'est-ce qui a mal tourné?$q_1-q_2$

Eh bien, intuitivement, `` l'état '' d'une MT n'est pas suffisamment informatif pour décrire la suite de la course. Pour avoir toutes les informations, vous avez besoin de la configuration de la MT, qui comprend l'état, la position de la tête et le contenu de la bande. Si vous trouvez un chemin de configuration (qui est appelé une exécution ) vers une configuration acceptante, alors la langue n'est pas vide et c'est une condition siff.

Le problème avec l'utilisation de l'analyse d'accessibilité sur le graphique de configuration est qu'elle peut être infinie. C'est pourquoi décider du vide du langage est indécidable.

C'est aussi pourquoi le non-vide du langage est reconnaissable - vous pouvez effectuer un BFS sur le graphique de configuration infini. S'il existe un chemin vers un état acceptant, vous le trouverez éventuellement. S'il n'y en a pas, cependant, vous pouvez vous retrouver coincé dans une recherche infinie.

est indécidable à cause duthéorèmedeRice$A$ , qui déclare que les propriétés non triviales des fonctions partielles ne sont pas décidables.

1. Il existe une MT qui n'accepte aucune chaîne. (Qui passe directement à l'état de rejet).
2. Il existe une MT qui accepte chaque chaîne. (Qui va directement à l'état d'acceptation).

Cela signifie que les fonctions calculées par les éléments de ont une propriété non triviale. Par conséquent, A n'est pas décidable.$A$$A$

n'est décidable que dans l'hypothèse où les DFA sont encodés d'une manière spéciale comme une table de transition d'état ou etc. (nous ne pouvons pas décider si une MT n'accepte que des langues régulières, à cause du théorème de Rice!). Dans ce casthéorème de riz n'est pas applicable parce que le codage particulier d'un élément est nécessaire pour décider E . Nous ne décidons donc pas uniquement des fonctions partielles.$E$$E$

(C'est-à-dire si le problème était, décider si une MT particulière est un DFA - ou DFA calculable - et le langage accepté par elle est vide, serait indécidable via le théorème de Rice. Notez que dans ce cas A = E .)$E$$A = E$

Autre indice: essayez de réduire le problème d'arrêt à .$L_\emptyset$

(L'astuce d'origine est d'utiliser le théorème de Rice, mais dans ce cas, une preuve directe est également assez simple.)

Lemme 1 : Si L est indécidable, le complément de L. l'est aussi

On sait que le problème d'arrêt, $H_{TM}$ est indécidable. Par conséquent, selon le complément du lemme 1 du problème d'arrêt, $H_{TM}^c$ est également indécidable.

$H_{TM}$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M halts on input x } \}$

$H_{TM}^c$ =$\{\langle M, x \rangle { }\mid \text{ M is a TM and M loops on input x } \}$

$E_{TM}$ = $\{\langle M \rangle { }\mid \text{ M is a TM and L(M) = } \emptyset \}$

Supposons que $E_{TM}$ est décidable. Nous réduirons $H_{TM}^c$ à $E_{TM}$ - en d' autres termes , nous montrerons comment construire une machine de Turing $M_{H_{TM}^c}$ qui décide $H_{TM}^c$ à l' aide du TM, $M_{E_{TM}}$ qui décide $E_{TM}$ . Cela nous donne une contradiction, car nous savons que $H_{TM}^c$ est indécidable, et donc $M_{H_{TM}^c}$ cannot exist. The word “reduce” simply means solving a given problem by converting it into another problem which we already know to solve. So, the Turing Machine for $H_{TM}^c$ can be constructed as follows:

$M_{H_{TM}^c}$ = “on input $\langle M,x \rangle$

$\qquad$ 1. Construct the code for a TM, $M_1$ that does the following:

$\qquad$ $\quad$ $M_1$ = "on input $w$

$\qquad$ $\quad$ 1. Simulate $M$ on $x$.

$\qquad$ $\quad$ 2. Accept if $M$ halts."

$\qquad$ 2. Run $M_{E_{TM}}$ on $\langle M_1 \rangle$

$\qquad$ 3. Accept if $M_{E_{TM}}$ accepts, reject otherwise."

It is crucial to understand that the TM $M_1$ is never actually simulated – such simulation could go into an infinite loop. All we are doing is constructing the code for $M_1$.

$M_1$ is constructed such that on any input $w$ given to it, it will simulate $M$ with input $x$. $M$ can halt or loop on $x$ and hence there can be two cases:

$\quad$ 1. $M_1$ accepts all inputs $w$ if $M$ halts on $x$. $M_{E_{TM}}$ will reject $M_1$ as $L(M_1) \neq \emptyset$.

$\quad$ 2. If $M$ loops on $x$, $M_1$ will also loop for every input $w$ given to it. Anyway, as $M_{E_{TM}}$ is a $\quad$decider it will reject and halt on input $M_1$ as $L(M_1) = \emptyset$.

$Correctness$$M_{E_{TM}}$$M_{H_{TM}^c}$$M_{H_{TM}^c}$$M_{E_{TM}}$$L(M_1) = \emptyset$$M$$x$
$M_{H_{TM}^c}$ rejects if $M_{E_{TM}}$ rejects that is $L(M_1) \neq \emptyset$ which happens if $M$ halts on $x$. Thus, $M_{H_{TM}^c}$ decides $H_{TM}^c$ which is a contradiction as $H_{TM}^c$ is undecidable.

$Nb:$

Let R be the reduction from $H_{TM}^c$ to $E_{TM}$.

The reduction gives:

i) $\langle M, x \rangle \in H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \in E_{TM}$

$\qquad$ M loops on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts nothing

ii) $\langle M, x \rangle \notin H_{TM}^c \Leftrightarrow R(\langle M,x \rangle) \notin E_{TM}$

$\qquad$ M halts on input x iff the language recognised by $R(\langle M,x \rangle)$ accepts something

Proof by contradicting $A_{TM}= \{\langle M,w\rangle \mid M \text{ is a Turing Machine which accepts w}\}$, (which we know is undecidable).

Assume the existence of $R_{TM}$, a TM that decides $L_\emptyset$

Use can then use $R_{TM}$ in the construction of a TM $S_{TM}$, which is a decider for $A_{TM}$

$S_{TM}=^{definition}$ "On input $\langle M,w\rangle$, where $M$ is the encoding of a TM and $w$ is a string:

1. Modify $M$, taking into account the input $w$, such that the new $M$ (call it $M_1$) rejects all input which is not equal to $w$, where $w$ is built into its description. If the input is equal to $w$, then $M_{1}$ runs $M$ on $w$ and outputs whatever $M$ outputs.

2. Run $R_{TM}$ with the input $\langle M_1,w\rangle$

3. Output the opposite of $R_{TM}$s output."

The assumption that there exists a Turing Machine deicer for $L_\emptyset$, allows us to construct a decider for $A_{TM}$, which is a contradiction.

E={ | M is a TM and L(M)=Φ}. Is E Turing-recognizable?

E is a language, to accept language E we construct a Turing Machine. Suppose we create a Turing EM for the language E.

EM will be provided as input the encoding of another Turing machines, If that inputted machine M accepts an empty language then it will be a member of language E, else it will be not a member of language.

Suppose we have a Turing Machine M, we need to check if it accepts an empty language. Turing Machine EM have M and strings eps, a, b, aa, bb, ..... EM will check if M can reach a final state for at least on a single input, and if it accepts at least a single input it will be discarded and not included in language E. Now, see a possibility T.M M gets into a loop so M will keep on running and we couldn't decide whether it can accept or can't accept anything. Hence, this given language E is NOT RE.

PS: I think the complement of this given Language E will be RE.