Разрешимость машины Тьюринга неоднозначных случаев
1) Является ли машина Тьюринга M, которая принимает язык L = {ε}, не принимая запись?
С одной стороны, я думаю, что это может быть ложным, потому что пустое слово может быть записью, но с другой, я думаю, что это может быть неразрешимой проблемой.
2) Все ли машины Тьюринга, язык которых разрешим, останавливается на каком-либо входе?
Та же идея, интуитивно я бы сказал да, из-за определения разрешимого, но я не знаю, что-то беспокоит меня.
3) Является ли язык палиндромов разрешимым независимо от алфавита?
Для этого я почти не сомневаюсь, что это Ложь, потому что с помощью теоремы Райс мы можем доказать, что эта проблема неразрешима.
1 ответ
1) Я не уверен, как анализировать это, но если ТМ принимает язык, состоящий только из пустого набора, он в конечном итоге прекратит принимать на пустой ленте. Будет ли это считаться входом или нет, зависит от вашего определения "вход". Я бы посчитал это записью, поэтому ответил бы "нет".
2) Язык, состоящий только из пустой строки, разрешим. Тем не менее, мы можем написать TM, который останавливается, принимает только пустую строку и входит в бесконечный цикл для всех других входных данных. То, что подразумевается под "чьим языком", является спорным, но для ТМ, которые кодируют частичные функции, я бы назвал язык этой ТМ набором строк, на которых он останавливается, поэтому я отвечал бы "нет".
3) Мне кажется, что, учитывая алфавит с n символами, вы всегда можете создать одноленточный детерминированный TM с O(n) -состояниями, которые halt-accept на палиндромах над этим алфавитом и halt-отклоняет другие строки, таким образом решая язык палиндромов над алфавитом. Я бы ответил "да", если термины имеют свои обычные значения. Обратите внимание, что теорема Райс не применима; это применимо к проблеме определения того, принимает ли ТМ язык палиндромов по алфавиту, но на самом деле, конечно, возможно решить, является ли что-то палиндромом (это делают КПК).