Wie ist für eine Turing-Maschine der Satz von Maschinen die „kürzer“ als und die dieselbe Sprache akzeptieren, entscheidbar?

Ich frage mich, warum die folgende Sprache in . $\mathrm R$

$L_{M_1}=\Bigl\{\langle M_2\rangle \;\Big|\;\; M_2 \text{ is a TM, and } L(M_1)=L(M_2), \text{ and } |\langle M_1\rangle| > | \langle M_2 \rangle| \Bigr\}$

(Ich weiß, dass es in da es eine Antwort auf diese Auswahlfrage gibt, aber ohne Erklärung). $\mathrm R$

Ich dachte sofort, dass das da wir wissen, dass die Überprüfung, ob zwei Maschinen dieselbe Sprache akzeptieren, nicht wirklich entscheidbar ist, kam ich zu dem Gedanken: Ist es unmittelbar "Falsch", aber es kann nicht sein, da es viele Turing-Maschinen gibt, die die gleiche Antwort akzeptieren und unterschiedliche Codierungen haben. $L_{M_1} \notin \textrm{co-RE} \cup \textrm{RE}$

Vielen Dank!

computability undecidability Jozef
quelle

Antworten:

ist in einfach weil die Anzahl der Maschinenbeschreibungen, die kleiner als eine gegebene Maschinenbeschreibung sind, endlich ist und jede endliche Sprache in . $L_{M_1}$ $R$ $R$

Dave Clarke
quelle

Ein wichtiger Hinweis: Obwohl die Sprache

entscheidbar ist, ist die Funktion

, die tatsächlich den Entscheider für diese Sprache findet, nicht berechenbar. Ich denke, dies ist wahrscheinlich der Grund, warum das Ergebnis anfänglich nicht intuitiv ist.

L_{M_{1}}

$L_{M_1}$

f (M) = L_{M}

$f(M) = L_M$

Templatetypedef