Доказательство того, что языки - узнаваемый Turging IFF, вычисляемо

Question

Очень маленький вопрос на этом доказательстве, который я нашел как теорема 3.21 в Sperser, и в моих лекциях.

В направлении «только если» мы предполагаем, что Turging Machine $ m $ распознает некоторые языки $ l $ . Считаем все строки в входном алфавите (в лексикографическом порядке, скажем) как $ s_1, s_2, s_3, \ dots $

Затем мы построим перечисленное устройство $ e $ что для каждого $ i= 1,2,3, \ dots $ просто работает $ m $ для $ i $ Шаги Каждый вход $ s_1, s_2, s_3, \ dots, s_i $ ; Затем он печатает любой $ s_j $ , который принимается $ m $ . $ E $ - это то, что нам нужно.

Теперь, поскольку я знаю, что строки конечны, почему я должен запускать $ m $ для $ I $ Этапы на первом $ i $ strings, когда я мог бы просто запустить его на $ i $ -th string? Это похоже на ненужное осложнение.

P.S. О другом вопросе об этом задали вопрос, но это решало другое сомнение: вопрос для «Только если« часть для теоремы »язык - узнаваемая Turing IFF, некоторые перечислены его перечисления."

Answer 1

Если вы запускаете $ m $ на $ i $ -th, тогда это может никогда не остановитьТаким образом, ваш алгоритм будет застрять.Идея состоит в том, что если $ m $ halt на $ i $ -th String, скажем,Spaness Class="Математический контейнер"> $ j $ Шаги, то мы увидим его, как только мы доберемся до $ \ max (i, j) $ -th String.