Предпосылки возникновения теории алгоритмов. Основные требования к алгоритмам. Подходы к уточнению понятия «алгоритм». Три основных типа универсальных алгоритмических моделей.
Алгоритм – предписание однозначно задающее процесс преобразования исходных данных в требуемый результат.
Процесс преобразования состоит из элементарных дискретных шагов, применение которых, конечное число раз, приводит к конечному результату. Теория алгоритмов – метатеория изучающая различные (качественное и количественное) свойства алгоритмов.
Основные требования к алгоритмам:
Каждый алгоритм имеет дело с данными — входными, промежуточными и выходными Þ необходимо уточнить понятие данных
Данные для своего размещения требуют памяти
Алгоритм состоит из отдельных элементарных шагов, или действий, причем множество различных шагов, из которых составлен алгоритм, конечно
Последовательность шагов алгоритма детерминирована
Результативность (сходимость)
Следует различать: а) описание алгоритма (инструкцию или программу); б) механизм реализации алгоритма (например, компьютер); в) процесс реализации алгоритма.
Подходы к уточнению понятия «алгоритм»:
Выбирается конечный набор исходных объектов, которые объявляются элементарными, и конечный набор способов построения из них новых объектов
уточнение понятия «данные» — множества слов в конечных алфавитах
для уточнения детерминизма будем использовать либо блок-схемы и эквивалентные им словесные описания, либо описание механизма реализации алгоритма
нужно!!! зафиксировать набор элементарных шагов и договориться об организации памяти
Три основных типа универсальных алгоритмических моделей:
Первый тип связывает понятие алгоритма с наиболее традиционными понятиями математики — вычислениями и числовыми функциями. Наиболее развитая и изученная модель этого типа — рекурсивные функции.
Второй тип основан на представлении об алгоритме как о некотором детерминированном устройстве, способном выполнять в каждый отдельный момент лишь весьма примитивные операции. Основной теоретической моделью этого типа является машина Тьюринга.
Третий тип алгоритмических моделей — это преобразования слов в произвольных алфавитах, в которых элементарными операциями являются подстановки, т. е. замены куска слова (подслова) другим словом. Преимущества этого типа — в его максимальной абстрактности и возможности применить понятие алгоритма к объектам произвольной (не обязательно числовой) природы.
Машина Тьюринга. Конфигурация машины Тьюринга. Функция, правильно вычислимая по Тьюрингу. Эквивалентные машины Тьюринга. Композиция машин Тьюринга.
Машина Тьюринга:
управляющего устройства, которое может находиться в одном из состояний, образующих конечное множество Q = {q1, …, qn};
ленты, разбитой на ячейки, в каждой из которых может быть записан один из символов конечного алфавита А = {а1 ..., аm};
устройства обращения к ленте, т. е. считывающей и пишущей головки, которая в каждый момент времени обозревает ячейку ленты, в зависимости от символа в этой ячейке и состояния управляющего устройства записывает в ячейку символ, сдвигается на ячейку влево или вправо или остается на месте; при этом управляющее устройство переходит в новое состояние (или остается в старом)
Среди состояний выделены начальное состояние q1 и заключительное состояние qz
Память машины Тьюринга — это конечное множество состояний (внутренняя память) и лента (внешняя память).
Лента бесконечна в обе стороны
Данные машины Тьюринга — это слова в алфавите ленты; на ленте записываются и исходные данные, и окончательные результаты.
Элементарные шаги машины — это считывание и запись символов, сдвиг головки на ячейку влево и вправо, а также переход УУ в следующее состояние.
Конфигурация машины Тьюринга:
Полное состояние машины Тьюринга определяется ее внутренним состоянием, состоянием ленты (т.е. словом, записанным на ленте) и положением головки на ленте.
Полное состояние будем называть конфигурацией, или машинным словом, и обозначать тройкой a1qia2, где qi — текущее внутреннее состояние, a1 — слово слева от головки, а a2 — слово, образованное символом, обозреваемым головкой, и символами справа от него, причем слева от a1 и справа от a2 нет непустых символов.
Стандартной начальной конфигурацией назовем конфигурацию вида q1a
Стандартной заключительной конфигурацией назовем конфигурацию вида qza
Ко всякой незаключительной конфигурации К машины Т применима ровно одна команда, которая К переводит в конфигурацию К‘:
Последовательность конфигураций однозначно определяется исходной конфигурацией K1 и полностью описывает работу машины Т, начиная с K1. Она конечна, если в ней встретится заключительная конфигурация, и бесконечна в противном случае.
Функция, правильно вычислимая по Тьюрингу:
Пусть f — функция, отображающая множество векторов над Аисх в множество векторов над Арез.
Машина Т правильно вычисляет функцию f, если:
1)
для любых V
и W,
таких, что f(V)
= W,
выполняется q1V
Wqz,
2) для любого V, такого, что f(V) не определена, машина Т, запущенная в стандартной начальной конфигурации q1V, работает бесконечно.
Если для f существует машина Т, которая ее правильно вычисляет, функция f называется правильно вычислимой по Тьюрингу.
Всякой правильно вычисляющей машине Тьюринга можно поставить в соответствие вычисляемую ей функцию.
Две машины Тьюринга с одинаковым алфавитом Аисх эквивалентны, если они вычисляют одну и ту же функцию.
Эквивалентная машина Тьюринга – универсальная машина Тьюринга. Машина Тьюринга называется универсальной, если она может при определенных начальных входных данных вычислить любую функцию, которая вычислима на какой-либо машине Тьюринга. Иначе говоря, с учетом тезиса Тьюринга можно сказать, что универсальная машина Тьюринга способна вычислить любую вычислимую функцию.
Вычисление предикатов на машине Тьюринга.
Машина Т вычисляет предикат Р(а) (а — слово в Aисх), если Т(а) = омега, где омега = И, когда Р(а) истинно, и омега = Л, когда Р(а) ложно. Если же Р(а) не определен, то машина Т, как и при вычислении функций, не останавливается.
Машина Т вычисляет Р(а) с восстановлением, если Т(а) = а*омега.
Универсальная машина Тьюринга. План построения универсальной машины Тьюринга.
Систему команд машины Тьюринга можно интерпретировать и как описание работы конкретного механизма, и как программу, т.е. совокупность предписаний, однозначно приводящих к результату.
Словесное описание алгоритма воспроизведения работы машины Тьюринга по заданной программе:
«Для текущей конфигурации a1akqiaja2 найти в системе команд команду с левой частью qiaj. Если правая часть этой команды имеет вид q¢ia¢jR, то заменить в текущей конфигурации qiaj на a¢jq¢i (получится конфигурация a1aka¢jq¢ia2); если же правая часть имеет вид q¢ia¢jL, то заменить akqiaj на q¢iaka¢j (случай с Е можно не рассматривать)».
Формулировка задачи: построить МТ U, вычисляющую функцию от двух переменных, и такую, что для любой машины Т с системой команд ST U(ST, a) =Т(а), если Т(а) определена (т.е. если машина Т останавливается при исходных данных a), и U(ST, а) не останавливается, если Т(а) не останавливается.
Любую машину U, обладающую указанным свойством, будем называть универсальной машиной Тьюринга.
Первая проблема построения универсальной машины U — проблема алфавита и множества состояний — всегда найдется машина Т, алфавиты АT и QT которой превосходят по мощности АU, QU или просто не совпадают с ними). Выход — символы АT и QT кодировать словами в алфавите АU. Пусть |АT| = mT, |QT| = nT. Будем всегда считать, что a1 = 1. Обозначим коды qi и aj через S(qi) и S(aj)
План построения машины Тьюринга.
Будем считать, что машина Т всегда работает на правой полуленте. Тогда ленту U можно разделить на две бесконечные полуленты с границей Z между ними: в правой полуленте записывается текущая конфигурация машины Т (в силу нашего предположения конфигурация машины Т при этой имитации никогда не зайдет на левую полуленту), а в левой полуленте записан код системы команд S(ST).
Начальная конфигурация U имеет вид u1S(ST)ZS(q1)S(a)
u1 — начальное состояние машины U,
q1 — начальное состояние Т,
а — исходное слово Т.
Выполнению одной команды Т соответствует цикл машины U, реализующей основное действие, с той разницей, что оно будет осуществляться не над конфигурацией К машины Т, а над ее кодом S(K). Благодаря выбранному кодированию длины всех слов вида S(qiaj) и S(ajqi) равны, поэтому при заменах S(qiaj) на S(a¢jq¢i) или S(akqi) на S(q'ia¢j), имитирующих движение головки машины Т, окрестность заменяемых слов не затрагивается и никаких сдвигов или раздвигов не требуется. Сама длина заменяемого слова равна числу символов между ® и ближайшим символом движения (R или L) на левой полуленте.
Тезис Тьюринга.
Всякий алгоритм может быть реализован машиной Тьюринга
Тезис Тьюринга позволяет, с одной стороны, заменить неточные утверждения о существовании эффективных процедур (алгоритмов) точными утверждениями о существовании машин Тьюринга, а с другой стороны, утверждения о несуществовании машин Тьюринга истолковывать как утверждения о несуществовании алгоритмов вообще.
Проблема остановки как пример алгоритмически неразрешимых проблем.
Требование результативности: по любому алгоритму А и данным a можно было определить, приведет ли работа А при исходных данных a к результату или нет. Иначе говоря, нужно построить алгоритм В, такой, что В (А, а)=И, если А(а) дает результат, и В (А, а) =Л, если А(а) не дает результата.
В силу тезиса Тьюринга эту задачу можно сформулировать как задачу о построении машины Тьюринга: построить машину T0 такую, что для любой машины Тьюринга Т и любых исходных данных a для машины Т T0(ST, а) =И, если машина Т(а) останавливается, и T0(ST, а) = Л, если машина Т(а) не останавливается.
Теорема 4. Не существует машины Тьюринга T0, решающей проблему остановки для произвольной машины Тьюринга Т
Предположим, что T0 существует. Для определенности будем считать, что маркером между ST и a на ленте машины T0 служит * . Построим машину T1(ST) = T0(Tкоп(ST)). Исходными данными машины T1 являются системы команд (точнее, их коды) любой машины Т. Запись ST на ленте машина T1 преобразует в ST * ST, а затем работает как машина T0. Таким образом, T1 также решает проблему остановки для любой Т, но только в том случае, когда на ленте Т в качестве данных aT написана ее собственная система команд ST. Иначе говоря, T1(ST) = И, если T(ST) останавливается, и T1(ST) =Л, если машина T(ST) не останавливается.
Пусть q1n — заключительное состояние T1. Добавим к системе команд T1 одно состояние q1,n+1, объявив его заключительным, и m команд (m—число символов T1) q1n Л® q1,n+1 E, q1n aj ® q1n R для любого aj, (в том числе И), кроме Л. Получим T¢1(ST), которая останавливается, если Т не останавливается, и не останавливается, если Т останавливается.
Запишем теперь на ленте T¢1 ее собственную систему команд ST¢1. Тогда T¢1 остановится, если она не останавливается, и не остановится, если она останавливается.
Очевидно, такая машина T¢1 невозможна. Но поскольку она получена из T0 вполне конструктивными, не вызывающими сомнений средствами и при этом никак не связана с конкретной структурой машины T0, остается заключить, что никакая машина T0, решающая проблему остановки, невозможна.
В силу тезиса Тьюринга невозможность построения машины Тьюринга означает отсутствие алгоритма решения данной проблемы. Поэтому полученная теорема дает первый пример алгоритмически неразрешимой проблемы, а именно, алгоритмически неразрешимой оказывается проблема остановки для машин Тьюринга, т. е. проблема определения результативности алгоритмов.