Алгоритмические машины
Информация - Компьютеры, программирование
Другие материалы по предмету Компьютеры, программирование
рации возможны два варианта развития событий:
- после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;
- остановки не происходит.
В первом случае говорят, что данная машина применима к начальной информации, во втором нет. Вся совокупность входных конфигураций, при которых машина обеспечивает получение результата, образуют класс решаемых задач. Очевидно, применять машину Тьюринга для задачи, не входящей в класс решаемых, бессмысленно. С другой стороны, во многих случаях возможно расширение класса решаемых задач за счет создания другой машины Тьюринга.
По своему устройству машина Тьюринга крайне примитивна. Она намного проще самых первых компьютеров. Примитивизм состоит в том, что у нее предельно прост набор элементарных операций, производимых головкой считывание и запись, а также в том, что доступ к ячейкам памяти (секциям ленты) в ней происходит не по адресу, как в компьютерах, а путем последовательного перемещения вдоль ленты. По этой причине даже такие простые действия, как сложение или сравнение двух символов, машина Тьюринга производит за несколько шагов, а обычные операции сложения и умножения требуют весьма большого числа элементарных действий. Однако машина Тьюринга была придумана не как модель или прототип реальных вычислительных машин, а для того, чтобы показать принципиальную теоретическую возможность построения сколь угодно сложного алгоритма из предельно простых операций, причем сами операции и переход от одной к последующей машина выполняет автоматически.
Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы:
- насколько общим является понятие машины Тьюринга?
- можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным?
- может ли всякий алгоритм задаваться таким образом?
На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:
Если некоторая процедура четко определена и по природе своей механистична, то модно вполне обоснованно предположить, что найдется машина Тьюринга, способная ее выполнить.
Эта гипотеза получила название тезиса Тьюринга. Как и тезис Черча, ее нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением машины Тьюринга.
В принципе, эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.
5. Универсальная машина Тьюринга
Машина Тьюринга представляет собой цифровой автомат, оперирующий словами единичной длины (т.е. символами) и снабженный запоминающим устройством в виде бесконечной ленты, на которой записываются символы входного слова, промежуточные результаты, а в итоге работы и выходное слово.
Внешний алфавит информационных слов, с которыми оперирует машина Тьюринга, может быть произвольным, но конечным. Помимо него, необходим внутренний алфавит для обозначения внутренних состояний и некоторых особых ситуаций. В результате работа машины Тьюринга допускает символическое описание в виде специальной таблицы переходов. В каждой строке этой таблицы текущему входному символу и текущему состоянию ставится в соответствие выходной символ, новое состояние и указание, слева или справа от текущего нужно взять следующий обрабатываемый символ. Строки таблицы называются командами, а таблица в целом программой. Работа машины Тьюринга начинается с настройки на начальное внутреннее состояние и первый символ входного слова. По ним в программе находится нужная команда, а в результате выходной символ, новое состояние и место, откуда нужно считать следующий входной символ. Так происходит до тех пор, пока не будет достигнуто особое, конечное состояние, соответствующее решению задачи.
Основной результат идеи Тьюринга заключается не в том, что для любого алгоритма в интуитивном смысле может быть построена соответствующая машина, хотя этот факт и не вызывает сомнений в результате многочисленных проверок. С помощью результатов работы Тьюринга можно доказать, что машина не может решать задачи, которые интуитивно неразрешимы.
Неразрешимость таких задач на машине Тьюринга не есть следствие ее примитивности. Тьюринг, действительно, искал как можно более простую схему, позволяющую не только формализовать процесс решения, но и обладающую применимостью к любым задачам. Предположение Тьюринга о том, что всякий алгоритм может быть реализован соответствующей машиной, было всего лишь гипотезой. Однако весь последующий опыт позволил возвести этот тезис в ранг формального определения алгоритма. И, пожалуй, самым впечатляющим доказательством справедливости идеи Тьюринга явилось установление эквивалентности этого определения другими формальными определениями, данными независимо Э. Постом и русскими математиками А.А. Марковым и А.Н. Колмогоровым.
Машина Тьюринга воображаемая конструкция. Построить ее значит выбрать подходящий для данной задачи алфавит, написать символическую программу и убедиться, будет ли достигнуто в ходе ее выполнения конечное состояние. Это можно сделать путем рассуждений, даже не получив конечного результата.
Рабо