Машина Тьюринга. Пример 7.9

Имеется запись многоразрядного целого числа п в десятичной системе счисления; выстроить машину Тьюринга, которая обеспечивала бы вычисление значение n + 1.

Используем наружный алфавит А = {0,1,…,9, ∆}, в каком знак ∆ соответствует пустому знаку. Внутренний алфавит, как и в предшествующей задачке, появляется 2-мя состояниями — рабочим (q) и остановкой (z) (Q = {q, z}). Начальное число п, а также итог — п + 1 — записываются в десятичной системе, при этом, числа располагаются по одной в примыкающих ячейках без пропусков. Многофункциональную схему представляется таблицей (для удобства строчка будут соответствовать состоянию q, а столбцы — знакам наружного алфавита):

Пусть исходной конфигурацией будет 21 q9.

Такт 1 q9→q0L, т.е. 9 будет заменена на 0 и головка двинется на разряд 10-ов — промежная конфигурация 2q10.

Такт 2 q1→z2S, т.е. 1 будет заменена на 2 и произойдет остановка с конечной конфигурацией 2z20, т.е. получен итог сложения 219 + 1.

Пусть исходной будет конфигурация 99q9.

Такт 1 q9→q0L, т.е. сформируется промежная конфигурация 9q90.

Такт 2 q9→ q0L — возникнет конфигурация q900.

Такт 3 q9→q0L — возникнет q∆000.

Такт 4 q∆→z1S — возникнет z1000 и работа прекращается.

Таким образом, описанный метод вправду обеспечивает суммирование хоть какого целого десятичного числа и единицы. Ясно также, что по мере надобности произвести сложение не с единицей, а с каким-то целым т, то данный метод нужно повторить т раз. Умножение целых чисел также может быть сведено к сложению числа с самим собой. Как следует, машины Тьюринга владеют принципиальным свойством — возможностью построения новейшей машины методом объединения уже имеющихся — такая операция именуется композицией.

По собственному устройству машина Тьюринга очень примитивна. Она намного проще самых первых компов. Примитивизм заключается в том, что у нее максимально прост набор простых операций, производимых головкой — считывание и запись, также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а методом поочередного перемещения повдоль ленты. По этой причине даже такие обыкновенные деяния как сложение либо сопоставление 2-ух знаков машина Тьюринга производит за пару шажков, а обыденные операции сложения и умножения требуют очень огромного числа простых действий. Но машина Тьюринга была выдумана не как модель (макет) реальных вычислительных машин, а для того, чтоб показать принципную (теоретическую) возможность построения сколь угодно сложного метода из максимально обычных операций, при этом сами операции и переход от одной к следующей машина делает автоматом.

Машина Тьюринга дает один из путей уточнения понятия метода. В связи с этим появляются вопросы:

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