Докажите, что конкретный язык не является полуразрешимым

Question

Я должен доказать, что язык L = {: |L(M)| <= 2016} НЕ является полуразрешимым. Теперь я подумал сделать это так:

Возьмем случайный алфавит E. Теперь в E. есть бесконечное количество слов. Мы можем только заключить, что | L (M) | <= 2016, передавая каждое слово из E* в качестве входных данных для M. Но поскольку существует бесконечное количество слов, это означает, что нам придется передавать входные данные для M бесконечное число раз. Но это подразумевает, что машина Тьюринга, которая выполняет эти проверки, оказывается в бесконечном цикле и, следовательно, никогда не возвращает, принимает и отклоняет свой ввод. Таким образом, язык L не является полуразрешимым.

Но я думаю, что это может быть недостаточно формальным? Главным образом потому, что я просто предполагаю, что машина Тьюринга, которая проверяет этот язык, позволит M запускать каждое слово из E*. Это предположение верно, или я должен быть более формальным в этом?

Answer 1

Рассмотрим дополнение к L: язык кодировок машин Тьюринга, языки которых содержат более 2016 строк. Мы можем легко доказать, что этот язык полуразрешим. Учитывая этот факт, предположим, что L также полуразрешима. Поскольку L и его дополнение являются полуразрешимыми, у нас есть эффективная процедура для определения каждого: запускайте TM для L и его дополнения поочередно, и один из них в конечном итоге перечислит входные данные.

Чтобы увидеть, что дополнение L является полуразрешимым, представьте себе TM, который выполняет один шаг M на каждом возможном входе, чередуя ходы, так что каждая строка в конечном итоге обрабатывается произвольным количеством ходов TM. Порядок, в котором он будет посещать входы, будет выглядеть так:

e,
e, 0,
e, 0, 1,
e, 0, 1, 00, 
e, 0, 1, 00, 01, ...

Очевидно, что любая строка ввода будет в конечном итоге обрабатываться любое возможное количество раз. Наша машина, которая имитирует M, работающий на всех возможных входных строках, по одному шагу за раз, в конечном итоге обнаружит, что строки 2017 имеют причину, по которой M прекращает прием, или она будет работать вечно. Если он находит строки 2017 года, которые работают, он прекращает принимать.