Проверка, проходит ли Turing Machine, по крайней мере, K> 2 состояния, прежде чем принимать слово

Question

$ l={\ langle m, k \ rangle \ mid \ exists w \ in l (m) \ text {Такая, что $ m $ проходит как минимум $ k> 2 $ Отличительные состояния Перед принятием $ W $} \} $

Я пытаюсь подумать о сокращении, чтобы доказать, что этот язык не является ни RE, ни ядром. Как подойти к этой проблеме?Есть ли подсказка или интуиция?

Я обычно проверяю, можно ли использовать рис, но вопрос здесь не о самом языке

Answer 1

Очевидно, что $ l $ приемлемо (просто имитация $ m $ и отслеживать количество Отличительные состояния, встречающиеся в ходе симуляции). Теперь покажу, что он не является разрешенным.

Если $ l $ были удалены, вы сможете решить проблему остановки следующим образом: Учитывая TM $ t $ и вход $ x \ in \ sigma ^ * $ , построить TM $ m $ , который игнорирует свой вход, имитирует $ t $ с входом $ m $ принимает, то он также проходит как минимум $ 3 $ Отличные состояния Просто пересекание из исходного состояния в другое (отчетное) состояние перед началом моделирования $ T $ .

Теперь проверьте, стоит ли $ \ langle m, 3 \ Rangle \ in l $ . Если ответ является утвердительным, то есть некоторые $ w \ in \ sigma ^ * $ , для которых $ m (w) $ принимает, показывая, что $ t (x) $ останавливает. Если ответ отрицателен, то $ m $ никогда не останавливает, показывая, что $ t (x) $ не остановить.