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

Question

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

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

М = {

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

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

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

Answer 1

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

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

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

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

Answer 2

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

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

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

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

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

Answer 3

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

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