Машина Алана Тьюринга.

Сначала. Кто же такой Алан Тьюринг?

Все же думаю, что многим известно имя Алана Тьюринга - британского математика, героя войны, сумевшего разгадать немецкую криптографическую машину Enigma. Но сегодня речь пойдет о его не настолько громком достижении, а именно об одной его научной работе “On Computable Numbers, with an Application to the Entscheidungsproblem” "Entscheidungsproblem - Проблема разрешения", вышедшей 12 ноября 1936 году. В этой статье Тьюринг описал некую закономерность о вычислимости математических функции. Он утверждает, что функция является вычислимой, если можно составить некий алгоритм для механической машины, вычисляющий эту самую функцию. В начале данной статьи, на странице 230 сборника, Алан Тьюринг описывает проблему “вычислимых” чисел, и дает им свое определение: - “Вычислимые числа можно кратко описать как действительные числа, выражения которых в десятичной дроби, поддаются вычислению конечным средствам.”, что подводит нас к поводу создания этой математической модели. А повод - это Проблема разрешения (Entscheidungsproblem) - задача из области оснований математики, сформулированная Давидом Гильбертом в 1928 году: - “Найти алгоритм, который бы принимал в качестве входных данных описание любой проблемы разрешимости (формального языка и математического утверждения «S» на этом языке) - и, после конечного числа шагов, останавливался бы и выдавал один из двух ответов: “Истина” или ”Ложь”, - в зависимости от того, истинно или ложно утверждение «S». Ответ не требует обоснований, но должен быть верным”.

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

Машина Алана Тьюринга - это всего лишь абстрактная математическая модель основанная на “теории конечного автомата” (Теория конечного автомата (КА) – это раздел дискретной математики и информатики, изучающий математические модели вычислений, которые могут находиться в одном из конечного числа состояний и переключаться между ними под воздействием входных сигналов.), созданная для формализации понятия алгоритма, не имеющая прямой реализации, почему именно прямой? Потому что в 1944 Джон (до иммиграции в США - Янош) фон Нейман, в стенах Пенсильванского Университета, вывел “Основы учения об архитектуре вычислительных машин”, а после по ним был собран ЭВМ ЭНИАК, в основе которого стояла схема называемая “архитектурой фон Неймана”, основанная на том что некая машина состоит из Устройства ввода, с которого поступают операнды, центральный вычислительный блок, именуемым Центральным процессором, который в свою очередь состоит из Устройства управления и Арифметико-логического устройства напрямую связанного с блоком оперативной (или постоянной памяти), и именно принцип работы и управления этой самой памятью во многом основанный на принципах работы машины Тьюринга.

Машина Алана Тьюринга основана на принципе чтения и перезаписи различных символов. Эта машина состоит всего из трех частей: бесконечной ленты, разделенной на равные ячейки (в которые может быть записан символ), считывающей/записывающей головки, и таблицы состояний. В последней, записаны различные состояния, а в каждом состоянии описаны действия, которые будут выполнены если головка считает тот или иной символ. Обычно выделяют такие команды: R - движение вправо, на одну ячейку, L - соответственно, движение влево на одну ячейку, “m”(символ) - записывает в ячейку определенный символ, N - бездействие, ! - терминальный оператор (конец программы), и например q0 - переход к состоянию q0.

Но лучше всего понять принципы работы на практике, ниже я опишу работу алгоритма для решения следующей, достаточно популярной задачи со скобками “()”, условие звучит так: “Построить машину Тьюринга, которая: на входе получает слово из скобок ( и ); и проверяет, является ли последовательность правильно скобочной (каждой открывающей скобке соответствует закрывающая); если верно, оставляет на ленте 1, иначе - 0;“.

"Пример программы для построения машины Тьюринга".

Ввод - “λ(()())λ”.

Алфавит - это символы зарегистрированные для обработки считывающей головки.

Алфавит - “()10”

*в данном эмуляторе машины Тьюринга, запись “,”, эквивалентна “λ”, “,” пишется для простоты использования.

Зеленый цвет - положение считывающей головки. "Начало программы".

Машина начинает с первого символа слова (слово - это весь ввод на ленте), головка встречает символ “(“ и в соответствии с инструкцией описанной в состоянии q0, записывает в эту ячейку вспомогательный символ “0” и двигается на одну ячейку вправо и затем переключится на состояние q1. Далее машина видит символ “(“ и в состоянии q1 описана инструкция R, что в свою очередь означает просто перейти к следующей ячейке на ленте, затем считывающая головка встречает “)”, и в инструкции состояния q1 сказано написать 0, пройти влево и переключится в состояние q0, и на этом моменте машина “убрала” первую пару скобок, и находится на втором символе слова, и теперь машина по точно такому же алгоритму переводит все слово в “000000”.

И далее машина просто заменяет все символы “0” на “λ”, и в связи с выполненным условием пишет “1”.

Также ещё можно сказать про “другие” виды Машин Тьюринга, например: “универсальная машина Тьюринга”, и “вероятностная машина Тьюринга”.

Универсальной машиной Тьюринга называют детерминированную машину Тьюринга, которая может заменить собой любую машину Тьюринга. Получив на вход программу и входные данные, она вычисляет ответ, который вычислила бы по входным данным машина Тьюринга, чья программа была дана на вход. Также согласно теореме “об универсальной машине Тьюринга”, что у подобной машины не может быть более чем квадратичное замедление (то есть если исходная машина произвела n шагов, то универсальная произведет не более cn^2). Теореме об универсальной машине Тьюринга была доказана самим Аланом Тьюрингом в 1947 году.

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

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

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

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

Это не какая-то принципиально новая модель вычислений. Она эквивалентна классической одноленточной машине Тьюринга в том смысле, что может решать точно такие же задачи. Однако она гораздо мощнее и эффективнее с точки зрения сложности вычислений (скорости и использования памяти).

Так же на машине Тьюринга можно имитировать машину Поста, нормальные алгоритмы Маркова и любую программу для обычных компьютеров, преобразующую входные данные в выходные по какому-либо алгоритму. В свою очередь, на различных абстрактных исполнителях можно имитировать Машину Тьюринга. Исполнители, для которых это возможно, называются полными по Тьюрингу .

Так можно сказать про так называемые “аналоги” машины Тьюринга, например про Машину Поста.

Из википедии и других источников мы знаем: Машина Поста - абстрактная вычислительная машина, предложенная Эмилем Постом в 1936 году, создана независимо от машины Тьюринга, но сообщение о машине Поста опубликовано на несколько месяцев позднее. Отличается от машины Тьюринга большей простотой, притом обе машины алгоритмически «эквивалентны» и обе разработаны для формализации понятия алгоритма и решения задач об алгоритмической разрешимости, то есть, демонстрации алгоритмического решения задач в форме последовательности команд для машины Поста.

Машина Поста состоит из каретки (или считывающей и записывающей головки) и разбитой на ячейки бесконечной в обе стороны ленты. Каждая ячейка ленты может находиться в 2 состояниях — быть либо пустой — 0, либо помеченной меткой 1. За такт работы машины каретка может сдвинуться на одну позицию влево или вправо, считать, изменить символ в своей текущей позиции.

Работа машины Поста определяется программой, состоящей из конечного числа строк. Для работы машины нужно задать программу и ее начальное состояние (то есть состояние ленты и позицию каретки). Кареткой управляет программа, состоящая из пронумерованных не обязательно упорядоченных строк команд, если в каждой команде указана строка, на которую нужно перейти. Обычно принимается, что если в команде переход не указан, то переход происходит на следующую строку. Каждая команда имеет следующий синтаксис: i. K j; где i — номер команды, K — действие каретки, j — номер следующей команды (ссылка).

Подводя итог ко всему вышеперечисленному, можно сказать что вклад Алана Тьюринга в решение “Проблемы разрешимости”, и в целом, в математику, криптографию, компьютерную науку поистине огромен, ведь как я писал выше, в основе устройства памяти компьютера и лежит знаменитая, востребованная и актуальная по сей день модель Машины Алана Тьюринга.

Спасибо, что заглянули!

Ссылки на материалы: