Доведіть, що ця мова не розпізнається - turing-машини, формальних мов

Це наступна мова Л нерозв'язна?

Л = {М | М є описом машини Тьюринга і існує вхід х довжини к такий, що М припиняється пізніше к кроки}

Я думаю, що це так, але я не міг це довести. Я намагався подумати про скорочення від проблеми зупинки.

Відповіді:

Огляд: Примірник проблеми зупинки запитує, чи токарська машина N зупиняється на вході у. Проблема, як відомо, є нерозв'язною (але semidecidable).

Твоя мова Л дійсно нерозв'язна. Це може бути показано шляхом зменшення проблеми зупинки Л:

1. Для примірника проблеми зупинки (N, у), створіть нову машину М для Л проблема
2. На вхід х, М імітує (N, у) для довжини (х) кроки.
3. Якщо моделювання зупинилося протягом цього числа кроків, то М припиняється. Інакше М навмисно переходить у нескінченний цикл.

Це зменшення є дійсним, оскільки:

• Якщо (N, у) зупиняється з часом к потім кроки М буде зупинено для всіх входів довжини к або більше, таким чином М є в Л.
• Інакше (N, у) тоді не зупиняється М не зупинятиметься для будь-якого вхідного рядка незалежно від того, наскільки довго він буде, таким чином М не в Л.

І, нарешті, проблема зупинки не може бути вирішена Л є нерозв'язною.