Тема 16.3. Свойства машины Тьюринга как алгоритма

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

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

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

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

На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы: «Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга».

Эта гипотеза получила название тезиса Тьюринга. Её нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением машины Тьюринга.

В принципе, эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы. Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.

На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов.

Дискретность:машина Тьюринга может перейти к- му шагу только после выполнения- го шага, т.к. именно- й шаг определяет, каким будет- й шаг.

Понятность:на каждом шаге в ячейку пишется символ из алфавита, автомат делает одно движение (R, L, S), и машина Тьюринга переходит в одно из описанных состояний.

Детерминированность:в каждой клетке таблицы машины Тьюринга записан лишь один вариант действия; на каждом шаге результат определён однозначно, следовательно, последовательность шагов решения задачи определена однозначно, т.е. если машине Тьюринга на вход подают одно и то же входное слово, то выходное слово каждый раз будет одним и тем же.

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

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

Раздел 17. Машина Поста

В 1936 году американский математик и логик Эмиль Леон Пост (1897–1954) предложил абстрактную вычислительную конструкцию, позволяющую формально определить алгоритм и названную впоследствии машиной Поста. При разработке вычислительной конструкции Пост руководствовался принципом создания максимально простой абстракции: минимумом операций при обработке информации, входная информация должна быть закодирована с использованием минимального набора символов.

Несмотря на «примитивность» машины Поста, любой существующий алгоритм может быть записан в виде программы для машины Поста. В теории алгоритмов существует так называемый «тезис Поста»: «Всякий алгоритм представим в форме машины Поста». Этот тезис одновременно является формальным определением алгоритма. Алгоритм (по Посту) – программа для машины Поста, приводящая к решению поставленной задачи.

Тезис Поста является гипотезой. Его невозможно строго доказать (так же, как и тезис Тьюринга), потому что в нём фигурируют, с одной стороны, интуитивное понятие «всякий алгоритм», а с другой стороны – точное понятие «машина Поста». Для того чтобы опровергнуть гипотезу Поста, необходимо придумать алгоритм, который невозможно записать в виде программы для машины Поста. На сегодняшний день такого алгоритма не существует.

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