Пример 7.9

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

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

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

Такт 1 q9→q0L, т.е. 9 будет заменена на 0 и головка сдвинется на разряд десятков - промежуточная конфигурация 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 и работа прекращается.

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

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

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

· насколько общим является понятие машины Тьюринга?

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

· может ли всякий алгоритм задаваться таким образом?

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:

Исполнитель алгоритма

Определение объекта

Пример 4.12

Коды, исправляющие одиночную ошибку

Вернуться в оглавление: Теоретические основы информатики