Имеется запись многоразрядного целого числа п в десятичной системе счисления; построить машину Тьюринга, которая обеспечивала бы вычисление значение 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 и работа прекращается. Таким образом, описанный алгоритм действительно обеспечивает суммирование любого целого десятичного числа и единицы. Ясно также, что при необходимости произвести сложение не с единицей, а с каким-то целым т, то данный алгоритм необходимо повторить т раз. Умножение целых чисел также может быть сведено к сложению числа с самим собой. Следовательно, машины Тьюринга обладают важным свойством - возможностью построения новой машины путем объединения уже имеющихся - такая операция называется композицией. По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у нее предельно прост набор элементарных операций, производимых головкой - считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты. По этой причине даже такие простые действия как сложение или сравнение двух символов машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель (прототип) реальных вычислительных машин, а для того, чтобы показать принципиальную (теоретическую) возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически. Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: · насколько общим является понятие машины Тьюринга? · можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? · может ли всякий алгоритм задаваться таким образом? На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: |
Кодирование и обработка в компьютере вещественных чисел Системы статические и динамические Вернуться в оглавление: Теоретические основы информатики |