Как спроектировать машину Тьюринга, которая проверяет, является ли число простым или нет?

Question

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

Answer 1

Ну, если подойдет любая старая ТМ, это легко понять.

1. лента ввода #(n)#
2. используйте TM, чтобы записать это на ленту: #(n):(2):(n)#
3. используйте ТМ, чтобы вычесть все, что находится между: от вещи после обоих: снова и снова, пока либо (1) у вас слишком мало символов для удаления (не делится), либо (2) осталось ровно ноль символов (равномерно делится), В случае (1) продолжить, в противном случае - в случае (2) - остановить-отклонить как не простое число.
4. используйте ТМ для записи этого на ленту: #(n):(m+1):(n)#
5. используйте ТМ, чтобы проверить, есть ли вещь перед первым: больше, чем вещь между двумя:. Если это так, перейдите к шагу 3. В противном случае остановите-примите (так как исходный ввод не может быть делится на число больше, чем он сам)

Возьмите все описанные ТМ и создайте единую ТМ, включающую все это поведение в различных состояниях. Это ТМ для языка простых чисел.

Предполагая унарное кодирование (то есть натуральное число n представлено строкой 11...1, где 1 повторяется n раз), вот еще несколько указателей по созданию отдельных TM:

1. оригинальный ввод
2. перейдите к первому пробелу после ввода и напишите:. Затем перейдите направо и напишите 1. Затем перейдите направо и напишите еще один. Затем перейдите направо и напишите еще один:. Затем отскок назад и вперед от начала до первого пробела в конце, копируя унарные цифры входного натурального числа. Для этого измените входные цифры на другой символ, например, A, чтобы вы помнили те, которые уже скопировали. Остановите этот процесс, когда слева от первого находится знак A:. Затем установите все А обратно на 1.
3. подпрыгивая назад и вперед, удалите 1 из крайней правой секции для каждой 1 в самой внутренней секции, обновляя самую внутреннюю секцию, чтобы использовать А, чтобы отметить их. Как только все в самом внутреннем разделе помечено, установите их обратно в 1 и повторяйте процесс, пока не закончится 1 в самом правом разделе.
4. сотри второе: и все после него; затем напишите 1 в конце, затем a: и сделайте то, что делает TM, описанный в 2.
5. подпрыгивайте вперед и назад между крайним левым и самым внутренним участками, отмечая каждый из них по мере продвижения. Если у вас закончились символы в самом внутреннем разделе, число будет меньше, чем введенное число; если у вас кончатся одновременно, числа совпадают, это означает, что входное число сначала делится само по себе, поэтому оно простое.