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

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

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

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

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

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

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

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

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

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

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

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