Prova che le lingue sono di Turing-riconoscibili IFF Compositamente enumevole

Question

Una domanda molto piccola su questa prova, che ho trovato come Teorema 3.21 a Sipser's, e nelle mie banconote.

Nella direzione "Solo se", assumiamo che una macchina di tentazione $ m $ riconosce qualche lingua $ l $ . Elenchiamo tutte le stringhe nell'alfabeto di input (in ordine lessicografico, ad esempio) come $ s_1, s_2, s_3, \ punti $

Costruiamo quindi un enumeratore $ e $ per ogni $ i= 1,2,3, \ punti $ Basta eseguire $ m $ per $ i $ Passaggi On ogni ingresso $ s_1, s_2, s_3, \ dots, s_i $ ; Quindi stampa di qualsiasi classe $ s_j $ che è accettata da $ m $ . $ e $ è ciò di cui abbiamo bisogno.

Ora, dal momento che so che le stringhe sono finite, perché dovrei eseguire $ m $ per $ i $ passaggi sulla prima $ i $ stringhe, quando potrei semplicemente eseguirlo sulla $ i $ -th string? Sembra una complicazione inutile.

P.S. È stato chiesto un'altra domanda su questo, ma ha affrontato un diverso dubbio: "Solo se" parte per il teorema "una lingua è tenuto-riconoscibile IFF Alcuni enumerator enumerano."

Answer 1

Se si esegue $ m $ sulla $ i $ -th stringa allora potrebbe non fermarsi mai, quindi il tuo algoritmo sarà bloccato.L'idea è che se $ m $ si fermano sulla $ I $ -th string, dicendo dopo $ J $ Passi, allora lo vedremo una volta arrivato alla $ \ max (I, J) $ -th string.