|
|
Машина Тьюринга
МАШИНА ТЬЮРИНГА - очень простое вычислительное устройство.
Она имеет ленту бесконечной длины, разделенную на ячейки. Каждая ячейка может быть пустой или содержать символ, выбираемый из некоторого конечного списка. Также машина Тьюринга имеет головку, которая перемещается вдоль ленты и может читать или записывать символы. Машина имеет внутренне состояние, которое может быть либо состоянием останова либо выражается целым числом между 0 и некоторой максимальной величиной. Когда машина переходит в состояние останова, она заканчивает вычисления. Хотя машина Тьюринга очень проста, однако любое вычисление, которое можно сдалать на современном компьютере, может быть выполнено на машине Тьюринга.
Действие, которое будет выполнять машина Тьюринга, завистит только от состояния машины и символа в ячейке, над которой находится головка машины. На основе этой информации (состояния и символа под головкой), машина Тьюринга может выполнить одно из трех действий: записать символ в ячейку (возможно тот же самый, который в ней уже находился )передвинуться на одну ячейку вправо или влевоустановить внутреннее состояние (возможно то же самое, в котором машина находится в данный момент)
Машина Тьюринга работает согласно таблице
правил или программе, которая определяет, что надо делать в случае различных комбинаций текущих состояний и символов, прочитанных с ленты.
Примеры машин Тьюринга
Апплет, реализующий модель машины Тьюринга, предполагает, что на входной ленте могут быть записаны символы 0, 1, x, y, z и $, а сама машина имеет не больше чем 25 состояний. Вычисления, которые может выполнить такая машина, очень нетривиальны.
В апплет могут быть загружены 4 примера машин Тьюринга:
- CopyXYZ.txt: Эта машина начинает работу с левого конца цепочки символов x, y, z. Она должна скопировать исходную цепочку и остановиться на левом конце этой копии.
- GatherDollars.txt: Эта машина начинает работу с левого конца строки, состоящей из символов $, 0, 1, x, y и z. Машина должна переместить все символы $ к левому концу строки, оставив остальные символы в исходном порядке, и остановиться на левом конце построенной строки.
- CountInBinary.txt: Работа начинается на правом конце строки из 0 и 1, которая интерпретируется как двоичное число. Машина добавит к написанному числу 1, и будет продолжать этот процесс бесконечно. Если лента в начальный момент пуста - результатом будет 1. Работайте в режиме "Fastest".
- BinaryAddition.txt: Исходные данные - два двоичных числа, разделенных пробелом. Машина начинает работу с правого конца второго числа и должна сложить эти числа. В результате работы второе число должно быть удалено с ленты, а первое - заменено вычисленной суммой.
Этот апплет написал David Eck для книги по введению в Computer Science The Most Complex Machine.
|
|
