Почему это недопустимая машина Тьюринга?

Question

Во время пересмотра экзамена у меня возникли проблемы с ответом на следующий вопрос из книги Сипсера "Введение в теорию вычислений".К сожалению, в книге нет решения этого вопроса.

Объясните, почему приведенное ниже не является законной машиной Тьюринга.

M = {

Входными данными является многочлен p над переменными x1, ..., xn

1. Попробуйте все возможные значения x1, ..., xn для целых чисел
2. Оцените p для всех этих параметров
3. Если какой-либо из этих параметров равен 0, примите;в противном случае отклоните.}

Это сводит меня с ума!Я подозреваю, что это потому, что набор целых чисел бесконечен?Превышает ли это каким-то образом допустимый размер алфавита?

Answer 1

Хотя это довольно неформальный способ описания машины Тьюринга, я бы сказал, что проблема заключается в одном из следующих:

• otherwise reject - в этом я согласен с Уэлбогом.Поскольку у вас есть счетно бесконечный набор возможных настроек, машина никогда не сможет узнать, будет ли еще доступна настройка, для которой она оценивает значение 0, и будет выполнять цикл вечно, если она ничего не найдет - только при обнаружении такой настройки машина может остановиться.Это последнее утверждение бесполезно и никогда не будет истинным, если, конечно, вы не ограничите машину конечным набором целых чисел.

• Порядок следования кодов:Я бы прочитал этот псевдокод как "сначала запишите все возможные настройки, затем оцените p для каждой из них", и вот ваша проблема:Опять же, имея бесконечный набор возможных настроек, даже первая часть никогда не завершится, потому что никогда не бывает последней настройки, которую нужно записать и перейти к следующему шагу.В этом случае машина даже не может сказать "нет значения 0", но она даже не может начать оценку, чтобы найти его.Это тоже можно было бы решить, ограничив набор целых чисел.

В любом случае, я не думаю, что проблема в размере алфавита.Вы бы не стали использовать бесконечный алфавит, поскольку ваши целые числа могут быть записаны в десятичном / двоичном / etc виде, а они используют только (очень) конечный алфавит.

Answer 2

Я немного подзабыл о машинах Тьюринга, но я считаю, что ваши рассуждения верны, т. е. набор целых чисел бесконечен, поэтому вы не можете вычислить их все.Хотя я не уверен, как это теоретически доказать.

Однако самый простой способ разобраться в машинах Тьюринга - это запомнить: "Все, что может вычислить реальный компьютер, может вычислить и машина Тьюринга"..Итак, если вы сможете написать программу, которая при заданном многочлене сможет решить ваши 3 вопроса, вы сможете найти машину Тьюринга, которая также сможет это сделать.

Answer 3

Я думаю, проблема в самой последней части: otherwise reject.

Согласно основы счетного множества, любое векторное пространство над счетным множеством само по себе является счетным.В вашем случае у вас есть векторное пространство над целыми числами размера n, который является счетным.Таким образом, ваш набор целых чисел является счетным, и поэтому можно попробовать любую их комбинацию.(То есть без пропуска какой-либо комбинации.)

Кроме того, вычисляя результат p на заданном наборе входных данных это также возможно.

И переход в принимающее состояние, когда p также возможно значение 0.

Однако, поскольку существует бесконечное число входных векторов, вы можете никогда отклоните вводимые данные.Поэтому ни одна машина Тьюринга не может следовать всем правилам, определенным в вопросе.Без этого последнего правила это возможно.