Докажите, что этот язык неразрешим

Question

Является ли следующий язык L неразрешимым?

L = { M | M - описание машины Тьюринга, и существует вход x длины k , такой, что M останавливается после самое большее k шагов}

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

Answer 1

Обзор: экземпляр проблемы остановки спрашивает, останавливается ли токарный станок N на входе y . Известно, что эта проблема неразрешима (но полурефицируема).

Ваш язык L действительно неразрешима . Это можно показать, уменьшив проблему остановки до L :

1. Для экземпляра проблемы остановки ( N , y ) создайте новый компьютер M для проблемы L .
2. На входе x , M имитирует ( N , y ) для длинных ( x ) шагов .
3. Если моделирование остановлено в течение этого количества шагов, то M останавливается. В противном случае M сознательно уходит в бесконечный цикл.

Это сокращение действительно, потому что:

• Если ( N , y ) в конечном итоге останавливается с шагом k , то M остановится для всех входов длины k или выше, таким образом M находится в L .
• В противном случае ( N , y ) не останавливается, тогда M не будет останавливаться для любой входной строки независимо от ее длины, таким образом M не входит L .

Наконец, проблема остановки неразрешима, поэтому L неразрешима.