Всегда ли машина останавливается?

22

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

Может ли кто-нибудь привести пример никогда не останавливавшейся машины, которая не зацикливается?

computability turing-machines halting-problem hollow7
источник

1

Только примечание: лента также может быть различным: достаточное (но не обязательно) условие для бесконечной петли , когда ТМ поступает в ту же ячейку на этапе , и на этапе в том же состоянии, является то , что на этапе часть ленты, которую посещает головка между этапом и этапом , равна соответствующей части непосредственно перед входом в .

t_{1}

$t_1$

t_{2} > t_{1}

$t_2 > t_1$

t_{2}

$t_2$

t_{1}

$t_1$

t_{2}

$t_2$

t_{1}

$t_1$

Вор

4

Если бы TM пришлось выполнить цикл, чтобы не остановить его, вы бы смогли довольно легко решить проблему остановки для TM: запомните все предыдущие конфигурации и на каждом шаге проверяйте, находитесь ли вы в конфигурации, которую вы видели раньше, и если да, то вы знаете, что вещь не останавливается (в противном случае, поскольку мы предполагаем, что она должна зацикливаться, чтобы работать вечно, она не будет работать вечно, то есть остановится, и в этом случае мы в конечном итоге знать об этом).

Patrick87

Вдохновленный ответом @Niel de Beaudrap: машина Тьюринга может вычислить последовательность oeis.org/A014445 и остановиться, когда получит нечетное число. Он может вычислить oeis.org/A016742 как текущую сумму и остановиться, если число нечетное. Он может вычислить, x^2где xциклы между -100и циклом 100выполняются по модулю и останавливаются, если результат отрицательный. Он может вычислить, x%2где x находится в диапазоне от нуля до положительной бесконечности, и останавливаться, когда результат равен 2. На языке ассемблера циклы do / while / for все сводятся к минимуму с условным переходом, но только cond jump означает мало.

Леонид

Предположение вопроса верно только для детерминированных машин.

Рафаэль

15

Рассмотрим TM, который всегда перемещает головку ленты вправо и печатает специальный непустой символ ленты на каждом шаге. Это означает, что TM никогда не останавливается, поскольку он всегда перемещается вправо и никогда не повторяет состояние, поскольку после k шагов головка ленты находится над k-й ячейкой машины. Следовательно, каждая конфигурация машины отличается от всех других, и машина всегда работает в цикле.

Мы также можем неконструктивно показать существование таких машин. Предположим для противоречия, что каждая TM, которая никогда не останавливается, в конце концов зацикливается. Это означает, что если вы запустите TM для строки , в конечном итоге произойдет одно из следующих действий: $M$ $w$

$M$ останавливается, или
$M$ повторяет конфигурацию.

В этом случае проблема остановки будет решаться следующим образом. Если задано значение TM и строка , смоделируйте для , в каждой точке записывая содержимое ленты, текущее состояние и текущее положение ленты. Если эта конфигурация является дубликатом, вывод «не останавливается». В противном случае, если останавливается на , выводится «halts». Поскольку одно из них гарантированно произойдет в конце концов, этот процесс всегда завершается, поэтому у нас будет алгоритм для решения проблемы остановки, который, как мы знаем, не существует. $M$ $w$ $M$ $w$ $M$ $w$

Надеюсь это поможет!

templatetypedef
источник

Ха, побью тебя до этого редактирования. Смотрите мой комментарий по этому вопросу. Мне нравится этот способ объяснения, почему не все не прерывающиеся ТМ должны зацикливаться ... это создает интуицию.

Patrick87

@ Patrick87 - Извините, я не заметил комментарий. Я подумал о добавлении в мои поездки и сел, чтобы войти в него, как только я вернулся.

templatetypedef

Нет проблем, чувак ... Я рад, что вы добавили это, так как я думаю, что это хороший способ объяснить это. Я добавил это только как комментарий, а не как ответ, так как вы меня опередили. : D

Patrick87

На самом деле, с точки зрения проблемы остановки, такой, что возврат и изменение ленты до бесконечности кажутся «настоящей проблемой». Те, кто ходят по пустотам, вы можете обнаружить.

Рафаэль

12

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

Более интересным (но также неоднозначным) случаем может быть машина Тьюринга, которая итеративно вычисляет функцию Коллатца на своем входе, завершается тогда и только тогда, когда оно получает целое число 1. Известная гипотеза Коллатца заключается в том, что для любого ввода эта процедура в конечном итоге останавливается. Но неизвестно, так ли это. В принципе, он может потерпеть неудачу двумя разными способами: либо он может найти последовательность целых чисел, которая зацикливается (соответствует существованию целого числа n, такого что для некоторого числа композиций, где n ≠ 1); или может быть, что есть цепочки целых чисел

f (n) = {\begin{cases} 3 n + 1, & if n is odd; \\ n / 2, & if n is even, \end{cases}

$f(n) = \begin{cases} 3n+1 , & \text{if $n$ is odd}; \\ n/2, & \text{if $n$ is even}, \end{cases}$

f \circ f \circ \dots f (n) = n

$f \circ f \circ \cdots f(n) = n$ n , f (n) , f (f (n)) , ... которые асимптотически расходятся в бесконечность. Если существуют какие-либо последовательности последнего рода, это будет означать, что машина Тьюринга, которую я описал выше, будет неповторяющейся, поскольку лента будет непрерывно заменяться на все большее и большее число.

Ниль де Бодрап
источник

Мне нравится играть с цифрами pi. ТМ может остановиться, когда квадрат любой цифры piравен ровно 7.

Леонид

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

Ниль де Бодрап,

10

Рассмотрим любую машину без остановок Тьюринга, которая никогда не перемещает головку чтения / записи влево.

JeffE
источник

Некоторые из них все еще находятся в цикле. </ nitpicking>

Рафаэль

5

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

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

RecursivelyIronic
источник

Что этот ответ добавляет к ответу templatetypedef ?

Рафаэль

Я думаю, что нет. Извините, я почему-то пропустил этот ответ, когда написал свой.

RecursivelyIronic

Всегда ли машина останавливается?

Ответы: