Prueba de que los idiomas son reconocibles, IFF computable, enumerable

Question

Una pregunta muy pequeña sobre esta prueba, que encontré como teorema 3.21 en Sipser's, y en mis notas de conferencia.

En la dirección "solo si", asumimos que una máquina de Turing $ m $ reconoce algún idioma $ l $ . Enumeramos todas las cadenas en el alfabeto de entrada (en orden lexicográfico, digamos) como $ s_1, s_2, s_3, \ puntos $

Luego construimos un enumerador $ e $ para cada $ i= 1,2,3, \ puntos $ simplemente funciona $ m $ para $ i $ pasos en Cada entrada $ s_1, S_2, S_3, \ DOTS, S_I $ ; Luego, imprime cualquier $ s_j $ que es aceptado por $ m $ . $ e $ es lo que necesitamos.

Ahora, ya que sé que las cuerdas son finitas, ¿por qué debería ejecutar $ m $ para $ i $ pasos en el primer $ i $ cadenas, cuando solo pude ejecutarlo en el $ i $ -th string? Se siente como una complicación innecesaria.

P.s. Se hizo otra pregunta sobre esto, pero abordó una duda diferente: Pregunta para "Solo si" parte para el teorema ", un idioma es el que se reconoce, el enumerador lo enumera".

Answer 1

Si ejecuta $ m $ en el $ i $ -th string, entonces nunca podría detenerse, por lo que tu algoritmo estará atascado.La idea es que si $ m $ se detiene en el $ i $ -th cadena, digamos después de $ J $ Pasos, entonces veremos una vez que lleguemos al $ \ max (i, j) $ -th cadena.