МАШИНА ТЬЮРИНГА Поздняков Сергей Николаевич

Зачем нам нужно определение алгоритма? Можно ли написать программу для любой задачи? Например, существует ли программа, которая по тексту другой программы определяет, зациклится она или нет? Без строгого определения алгоритма ответ на этот вопрос невозможен.

Алгоритм – это автомат? У автомата есть строгое определение: Входные и выходные символы Состояния автомата Начальное состояние Функция перехода между состояниями Функция выхода

Граф автомата Автомат обычно изображается графом: Это автомат для сложения двоичных чисел произвольной длины

Может ли автомат перемножать числа произвольной длины? Пусть такой автомат существует и имеет N состояний Умножим с его помощью число 10 N+1 +1 на себя: результат будет 10…010…01, где число нулей между соседними единичками равно N После того, как на выходе появятся первые N+2 цифры (исходное число), следующие N+1 цифр должны появится при пустом входе Сначала должны появится N нулей, но после этого атомат перейдёт в одно из пройденных состояний и последняя единичка никогда на выходе не появится

Добавим к автомату бесконечную ленту Автомат с присоединенной лентой и есть машина Тьюринга. Вот как изображают результат в «википедиях» на различных языках.

Формальное определение машины Тьюринга Алфавит (входной и выходной языки) Состояния. Начальное и конечное состояния. Функции перехода, вывода и сдвига вдоль ленты (R - вправо, L - влево, E - на месте). Их можно описать в форме таблицы, графа, набора «команд»

Пример машины Тьюринга Проверка на чётность числа символов (единичек), записанных на ленте q 1 1 –> q 2 R * q 2 1 –> q 1 R * q 1 * –> q 0 E чётное q 2 * –> q 0 E нечётное

Многоленточные и многоголовочные машины Тьюринга Реализовать содержательный алгоритм на машине Тьюринга очень трудоёмко, поэтому рассматривают более удобные вариации машины Тьюринга, сводящиеся к ней. Решим задачу проверки делимости натурального числа на меньшее: делимое будет записано на верхней ленте, а делитель – на нижней: q 1 (1,1) –> q 1 (R,R)(1,1) q 1 (1,*) –> q 2 (E,L)(1,*) q 2 (1,1) –> q 2 (E,L)(1,1) q 2 (1,*) –> q 1 (E,R)(1,*) q 1 (*,*) –> q 0 (E,E)(делится,*) q 1 (*,1) –> q 0 (E,E)(не делится,1)

Зачем придумали машину Тьюринга? Проблема останова Проблема самоприменимости Предположим, что некто придумал алгоритм, который может определить, зацикливается ли любой представленный ему на анализ алгоритм или нормально заканчивает свою работу. Теперь, когда у нас есть строгое понятие алгоритма, мы можем переформулировать задачу так: некто придумал машину Тьюринга A, которая, читая команды любой другой машины Тьюринга X, может определить, придёт ли она когда-нибудь в конечное состояние. Тогда на основе этой машины Тьюринга мы сконструируем новую машину B, которая будет зацикливаться, при анализе машиной A останавливающейся машины X и останавливаться при анализе машиной A зацикливающейся машины X. Теперь машину B мы представим на анализ машине A. Каков будет ответ? Если X будет проанализирована как останавливающаяся, это будет означать, что B зацикливается, но X=B!!!

Что должны знать все программисты? Из изложенного следует, что у теории алгоритмов есть границы. Не для каждой задачи можно построить решающий её алгоритм. Это должен знать каждый программист, который не хочет потратить свою жизнь на создание «вечного двигателя». Чем ещё полезна машина Тьюринга? На формализации идеи алгоритма построена теория сложности алгоритмов. Оказывается, что есть такие алгоритмы, которые работают так долго, что практически применять их невозможно. Для того, чтобы разделить «хорошие» алгоритмы от «плохих», рассмотрим понятие НЕДЕТЕРМИНИРОВАННОЙ машины Тьюринга.

Недетерминированная машина Тьюринга Как построить машину Тьюринга для определения простоты числа на ленте? Можно воспользоваться предыдущей машиной Тьюринга для определения делимости Тогда для заданного числа N (N единичек на ленте) можно создать N-2 машины Тьюринга, на которых будет записано от 2 до N-1 единиц и запустить их всех сразу, если все машины дадут отрицательный результат, то число N-простое Такая конструкция называется недетерминированной машиной Тьюринга Понятно, что появление такого определения связано с решением задач «подбором» или более точно «перебором» всех вариантов

Как определяется сложность алгоритмов? Предположим, что на ленте записано N символов и посчитаем, сколько шагов T сделает машина Тьюринга прежде, чем остановится. Зависимость T(N) и можно рассматривать как меру сложности алгоритма Для первого алгоритма (определение чётности числа) машина Тьюринга сделает N шагов, для второго (деление числа M на N) MN шагов Но во втором случае мы рассматривали многоленточную машину Тьюринга. Если заменить её машиной с одной лентой, то шагов будет существенно больше. Может ли тогда трудоемкость иметь порядок T 2, T 3 или больше? Может, но это всегда будет степенная функция! Поэтому все такие алгоритмы объединяют в один класс сложности P – алгоритмы ПОЛИНОМИАЛЬНОЙ сложности

Проблема на миллион долларов В алгоритме для проверки простоты числа сразу работают N полиномиальных алгоритмов, класс сложности таких задач называют классом алгоритмов НЕДЕТЕРМИНИРОВАННОЙ ПОЛИНОМИАЛЬНОЙ сложности До сих пор неизвестно, можно ли их свести к обычным «непереборным» алгоритмам. Эта задача называется задачей PNP и входит в число задач, поставленных для решения в XXI веке. Например, существует «задача коммивояжера», состоящая в том, что надо найти кратчаший маршрут между городами, соединенными транспортной сетью. Проверить, что предложенный маршрут меньше какого либо заданного числа просто, но найти маршрут, длина которого меньше заданного числа, трудно. Это и демонстрирует суть проблемы PNP.

Задача о занятом бобре

Неоптимальное решение

Для тех, кто хочет попробовать себя в исследовании алгоритмов Сайт конкурса:

Тьюрмиты и Тримувьи – плоские и пространственные машины Тьюринга

Галерея изображений, построенных трехмерной машиной Тьюринга

Журнал «Компьютерные инструменты в школе» Электронное приложение «Журнал в журнале»

Все, желающие найти статьи про машину Тьюринга, занятых бобров, тьюрмитов, тримувьев и прочее, могут получить БЕСПЛАТНЫЙ доступ к архивам журнала Для этого надо зарегистрироваться на сайте журнала и отправить электронное письмо с просьбой открыть архивы Позднякову С.Н. Сайт журнала: