Beweis, dass Sprachen traurig anerkennbar sind, eigentlich atf

Question

Eine sehr kleine Frage an diesem Beweis, die ich als Theorem 3.21 in Sipser und in meinen Vorlesungsnotizen fand.

In der "nur wenn" Richtung gehen wir davon aus, dass eine Turing-Maschine $ M $ einige Sprache erkennt $ L $ . Wir listen alle Zeichenfolgen im Input-Alphabet auf (in lexikografischer Reihenfolge, sagen), wie $ s_1, s_2, s_3, \ dots $

Wir konstruieren dann einen Enumerator $ E $ Das für jeden $ i= 1,2,3, \ Punkte $ läuft einfach $ M $ für $ i $ Schritte on Jeder Eingang $ S_1, S_2, S_3, \ Punkte, S_I $ ; Dann druckt es jeden $ s_j $ , der von $ M $ akzeptiert wird. $ E $ ist das, was wir brauchen.

Nun, da ich weiß, dass Saiten endlich sind, warum sollte ich $ M $ für $ i $ Schritte auf der ersten $ i $ Saiten, wenn ich es einfach auf dem ausführen könnte> $ i $ -th-Zeichenfolge? Es fühlt sich an wie eine unnötige Komplikation.

p.s. Eine andere Frage wurde darum gefragt, aber es wurde ein anderer Zweifel angesprochen: Frage für "Nur wenn" Teil für den Satz "eine Sprache trägt, die erkennbare IFF ist, lächert ein Enumerator auf."

Answer 1

Wenn Sie $ M $ auf der $ I $ -Th-Zeichenfolge ausgeführt werden, kann es möglicherweise nie bleiben, also wird dein Algorithmus stecken.Die Idee ist, dass, wenn $ M $ auf dem Het-I $ -th-String hält, sagen Sie nach $ J $ Schritte, dann werden wir es sehen, sobald wir den $ \ max (i, j) $ -te String.