Prova de que línguas estão turing-reconhecível IFF calpecialmente enumerável

Question

Uma pergunta muito pequena sobre esta prova, que eu encontrei como Teorema 3.21 em Sipser, e nas minhas anotações.

Na direção "somente se", assumimos que uma máquina de Turing $ m $ reconhece alguma linguagem $ l $ . Nós listamos todas as strings no alfabeto de entrada (em ordem lexicográfica, digamos) como $ s_1, s_2, s_3, \ dots $

Em seguida, construímos um enumerador $ e $ para cada $ i= 1,2,3, \ pontos $ simplesmente executa $ m $ para $ i $ etapas Cada entrada $ S_1, S_2, S_3, \ Dots, S_I $ ; Em seguida, imprime qualquer $ s_j $ que é aceito por $ m $ . $ e $ é o que precisamos.

Agora, já que eu sei que as cordas são finitas, por que devo correr $ m $ para $ i $ etapas no primeiro $ i $ strings, quando eu poderia apenas executá-lo na $ i $ -th string? Parece uma complicação desnecessária.

p.s. Outra questão foi feita sobre isso, mas abordou uma dúvida diferente: Pergunta para "Somente se" parte para o teorema "uma linguagem é reconhecer - reconhecível, algum enumerador enumera-o."

Answer 1

Se você executar $ m $ na $ i $ -string, então pode nunca parar, então seu algoritmo ficará preso.A ideia é que, se $ m $ pare na $ i $ -th string, digamos depois de $ J $ etapas, então vamos ver uma vez que chegarmos à $ \ max (i, j) $ -th string.