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

Question

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

Answer 1

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

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

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

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