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

Введение

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

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

В 1947 г. Алан Тьюринг расширил определение, описав "универсальную машину Тьюринга". Позже для решения определенных классов задач была введена ее разновидность, которая позволяла выполнять не одну задачу, а несколько.

Описание машины Тьюринга

Предыстория создания этой работы связана с формулировкой Давидом Гильбертом на Международном математическом конгрессе в Париже в 1900 году неразрешенных математических проблем. Одной из них была задача доказательства непротиворечивости системы аксиом обычной арифметики, которую Гильберт в дальнейшем уточнил как "проблему разрешимости" - нахождение общего метода, для определения выполнимости данного высказывания на языке формальной логики.

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

Приведем характеристику этой работы, принадлежащую Джону Хопкрофту: "Работая над проблемой Гильберта, Тьюрингу пришлось дать четкое определение самого понятия метода. Отталкиваясь от интуитивного представления о методе как о некоем алгоритме, т.е. процедуре, которая может быть выполнена механически, без творческого вмешательства, он показал, как эту идею можно воплотить в виде подробной модели вычислительного процесса. Полученная модель вычислений, в которой каждый алгоритм разбивался на последовательность простых, элементарных шагов, и была логической конструкцией, названной впоследствии машиной Тьюринга".

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

Формально машина Тьюринга может быть описана следующим образом. Пусть заданы:

конечное множество состояний - Q, в которых может находиться машина Тьюринга;

конечное множество символов ленты - Г;

функция д (функция переходов или программа), которая задается отображением пары из декартова произведения Q x Г (машина находится в состоянии qi и обозревает символ i) в тройку декартова произведения Q х Г х {L,R} (машина переходит в состояние qi, заменяет символ i на символ j и передвигается влево или вправо на один символ ленты) - Q x Г-->Q х Г х {L,R}

один символ из Г-->е (пустой);

подмножество У є Г - -> определяется как подмножество входных символов ленты, причем е є (Г - У);

одно из состояний - q0 є Q является начальным состоянием машины.

Решаемая проблема задается путем записи конечного количества символов из множества У є Г - Si є У на ленту:

eS1S2S3S4... ... ... Sne

после чего машина переводится в начальное состояние и головка устанавливается у самого левого непустого символа (q0,w) -, после чего в соответствии с указанной функцией переходов (qi,Si) - ->(qj,Sk, L или R) машина начинает заменять обозреваемые символы, передвигать головку вправо или влево и переходить в другие состояния, предписанные функций переходов.

Остановка машины происходит в том случае, если для пары (qi,Si) функция перехода не определена.

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

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

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

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

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

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

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

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

Который, позаимствовав идею у Эмиля Поста, придумал её, как считается, в 1936 году. Несмотря на довольно сложное формальное определение, идея в принципе проста. Чтобы понять её, давайте прогуляемся по страницам Википедии.

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

Машина Тьюринга

Машина Тьюринга (МТ) - математическая абстракция, представляющая вычислительную машину общего вида. Была предложена Аланом Тьюрингом в году для формализации понятия алгоритма .

Машина Тьюринга является расширением модели конечного автомата и, согласно тезису Чёрча - Тьюринга , способна имитировать (при наличии соответствующей программы) любую машину, действие которой заключается в переходе от одного дискретного состояния к другому.

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

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

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

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

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

1. Для производства белков в клетке с помощью сложно устроенного фермента - РНК-полимеразы - считывается информация с ДНК, своего рода информационной ленты машины Тьюринга. Здесь, правда, не происходит перезапись ячеек самой ленты, но в остальном процесс весьма похож: РНК-полимераза садится на ДНК и двигается по ней в одном направлении, при этом она синтезирует нить РНК - нуклеиновой кислоты, сходной с ДНК. Готовая РНК, отсоединяясь от фермента, несёт информацию к клеточным органеллам, в которых производятся белки.

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

Такая аналогия не нова, и в Википедии она тоже описана в статье «Молекулярный компьютер »:

Молекулярный компьютер

Биомолекулярные вычисления или молекулярные компьютеры или даже ДНК - или РНК -вычисления - все эти термины появились на стыке таких различных наук как молекулярная генетика и вычислительная техника.

Биомолекулярные вычисления - это собирательное название для различных техник, так или иначе связанных с ДНК или РНК. При ДНК-вычислениях данные представляются не в форме нулей и единиц, а в виде молекулярной структуры, построенной на основе спирали ДНК. Роль программного обеспечения для чтения, копирования и управления данными выполняют особые ферменты .

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

Молекула получается направленной: начинается с фосфатной группы и заканчивается дезоксирибозой. Длинные цепочки ДНК называют нитями, короткие - олигонуклеотидами. Каждой молекуле ДНК соответствует еще одна ДНК - так называемое дополнение Ватсона - Крика . Она имеет противоположную направленность, нежели оригинальная молекула. В результате притяжения аденина к тимину и цитозина к гуанину получается знаменитая двойная спираль, обеспечивающая возможность удвоения ДНК при размножении клетки. Задача удвоения решается с помощью специального белка-энзимы - полимеразы. Синтез начинается только если с ДНК прикреплен кусочек ее дополнения, Данное свойство активно используется в молекулярной биологии и молекулярных вычислениях. По сути своей ДНК + полимераза - это реализация машины Тьюринга , состоящая из двух лент и программируемого пульта управления. Пульт считывает данные с одной ленты, обрабатывает их по некоторому алгоритму и записывает на другую ленту. Полимераза также последовательно считывает исходные данные с одной ленты (ДНК) и на их основе формирует ленту как бы с результатами вычислений (дополнение Ватсона - Крика).

Немножко фантастические перспективы только подогревают наше любопытство. Между тем, мы еще не всё выяснили относительно машины Тьюринга. Как вы помните, в статье из Википедии её назвали расширением конечного автомата. Что же это такое конечный автомат? На него, к счастью, даётся ссылка. Заходя по ней, узнаём, что:

Конечный автомат

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

С каждым определением мы всё больше вторгаемся в область чистой математики. Язык становится строже, появляются формальные определения, состоящие из математических символов. Если двигаться дальше, мы придём к теории алгоритмов и теории вычислимости. Путешествовать по страницам Википедии можно долго, но лучше запастись водой и едой, на случай забредания в пустыни аксиом и определений, или хотя бы надёжными ссылками на учебники по математике, например http://www.mccme.ru/free-books/ , или статьи журнала «Потенциал» ;)

Надеюсь, после этого объяснения вам стало немного яснее, что же такое машина Тьюринга?

Давайте вернёмся к истории этого термина.

Итак, как мы уже упоминали, Алан Тьюринг поведал миру о своей машине в 1937 году в так называемом Тезисе Чёрча-Тьюринга. Про Алана Тьюринга - первого хакера и пионера информатики, как написано на мемориальной доске гостиницы, где он родился, поведает нам статья «Алан Тьюринг». Текст статьи полностью приводить здесь не будем, но она и сама по себе не очень подробная.

Алан Тьюринг

Тьюринг, Алан Матисон (23 июня 1912 - 7 июня 1954) - английский математик, логик, криптограф, изобретатель Машины Тьюринга.

В самой статье больше про труды Тьюринга: помимо текста про машину Тьюринга, который мы еще приведем дальше, повествуется о том, что он работал над «проблемой зависания» (Забавно, не так ли? Компьютеров еще не было, и системы Windows тоже, а проблема зависания уже была.); героическая история про то, как Тьюринг взломал код «Энигмы» во время Второй Мировой Войны и тем самым спас Великобританию; факт о том, что он является основателем теории искусственного интеллекта, а также упоминание о знаменитом тесте Тьюринга. Сейчас этот тест уже не так часто используется как завязка научно-фантастического рассказа, однако проблема человеческого в машине всегда останется классикой, как и романы Айзека Азимова и Станислава Лема.

Несмотря на свою старомодность, тест Тьюринга всплыл неожиданным образом в современном мире общения по интернету. К примеру, можно встретить текст диалога двух пользователей ICQ, один из которых является «ботом», и задача - определить, какой именно. Или к Вам может постучаться незнакомый пользователь, возможно, ICQ-робот. Узнаете ли вы его? Изучая теорию, Вы, возможно, сумеете вовремя применить тест Тьюринга и не останетесь обмануты. Начать изучение можно с соответствующей статьи в Википедии, а затем пройтись по ссылкам, приводимым в конце статьи:

Тест Тьюринга

Тест Тьюринга - тест, предложенный Аланом Тьюрингом в 1950 г. в статье «Вычислительные машины и разум» (Computing machinery and intelligence) для проверки, является ли компьютер разумным в человеческом смысле слова.

Судья (человек) переписывается на естественном языке с двумя собеседниками, один из которых - человек, другой - компьютер. Если судья не может надёжно определить, кто есть кто, компьютер прошёл тест. Предполагается, что каждый из собеседников стремится, чтобы человеком признали его. С целью сделать тест простым и универсальным, переписка сводится к обмену текстовыми сообщениями.

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

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

Тьюринг предложил тест, чтобы заменить бессмысленный, по его мнению, вопрос «может ли машина мыслить?» на более определённый.

Тьюринг предсказал, что компьютеры в конечном счёте пройдут его тест. Он считал, что к 2000 году, компьютер с памятью 1 миллиард бит (около 119 Мб) в ходе 5-минутного теста сможет обмануть судей в 30 % случаев. Это предсказание не сбылось. (Правда, на первом конкурсе Лебнера компьютерная программа «PC Therapist» на IBM PC 386 смогла ввести в заблуждение 5 судей из 10, но ей не засчитали результат, а в 1994 году конкурс усложнили.) Тьюринг также предсказал, что сочетание «мыслящая машина» не будет считаться оксюмороном , а обучение компьютеров будет играть важную роль в создании мощных компьютеров (с чем большинство современных исследователей согласны).

Пока что ни одна программа и близко не подошла к прохождению теста. Такие программы, как Элиза (ELIZA), иногда заставляли людей верить, что они говорят с человеком, как, например, в неформальном эксперименте, названном AOLiza. Но такие «успехи» не являются прохождением теста Тьюринга. Во-первых, человек в таких беседах не имел никаких оснований считать, что он говорит с программой, в то время как в настоящем тесте Тьюринга человек активно пытается определить, с кем он беседует. Во-вторых, документированые случаи обычно относятся к таким чатам, как IRC , где многие беседы отрывочны и бессмысленны. В-третьих, многие пользователи IRC используют английский как второй или третий язык, и бессмысленный ответ программы, вероятно, спишется ими на языковый барьер. В-четвертых, многие пользователи ничего не знают об Элизе и ей подобных программах и не могут распознать совершенно нечеловеческие ошибки, которые эти программы допускают.

Ежегодно производится соревнование между разговаривающими программами, и наиболее человекоподобной, по мнению судей, присуждается приз Лебнера (Loebner). Есть дополнительный приз для программы, которая, по мнению судей, пройдёт тест Тьюринга. Этот приз ещё не присуждался.

Самый лучший результат в тесте Тьюринга показала программа A.L.I.C.E. выиграв тест 3 раза (в 2000, 2001 и 2004).

Ссылки

• Тьюринг А. М. Вычислительные машины и разум. // В сб.: Хофштадер Д., Деннет Д. Глаз разума. - Самара: Бахрах-М, 2003. - С. 47-59.
• Книга на английском: Roger Penrose «The Emperor’s New Mind».
• Статья Алана Тьюринга:
  • Alan Turing, «Computing Machinery and Intelligence», Mind, vol. LIX, no. 236, October 1950, pp. 433-460.
  • В сети:
• Статья Дж. Оппи (G. Oppy) и Д. Дави (D. Dowe) о тесте Тьюринга из Стэнфордской Философской Энциклопедии (на английском)
• «Turing Test: 50 Years Later» обзор 50-летней работы над тестом Тьюринга, с точки зрения 2000 г. (на английском).

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

Выдержка из статьи Википедии «Алан Тьюринг»

Любая интуитивно вычислимая функция является частично вычислимой, или, эквивалентно, может быть вычислена с помощью некоторой машины Тьюринга.

Алан Тьюринг высказал предположение (известное как Тезис Чёрча-Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.

В статье под названием «Те́зис Чёрча-Тью́ринга» про него пишут так:

Те́зис Чёрча-Тью́ринга

Те́зис Чёрча-Тью́ринга - фундаментальное утверждение для многих областей науки, таких, как теория вычислимости , информатика , теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

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

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

Физический тезис Чёрча-Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга .

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

Универсальная машина Тьюринга

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

Формальное определение

Программу любой детерминированной машины Тьюринга можно записать, используя некоторый конечный алфавит, состоящий из символов состояния, скобок, стрелки и т. п.; обозначим этот машинный алфавит как Σ 1 {\displaystyle \Sigma _{1}} . Тогда универсальной машиной Тьюринга U для класса машин с алфавитом Σ 2 {\displaystyle \Sigma _{2}} и k входными лентами называется машина Тьюринга с k+1 входной лентой и алфавитом Σ 1 ∪ Σ 2 {\displaystyle \Sigma _{1}\cup \Sigma _{2}} такая, что если подать на первые k лент входное значение, а на k+1 - правильно записанный код некоторой машины Тьюринга , то U выдаст тот же ответ, какой выдала бы на этих входных данных M 1 {\displaystyle M_{1}} , или будет работать бесконечно долго, если M 1 {\displaystyle M_{1}} на этих данных не остановится.

Теорема об универсальной машине Тьюринга утверждает, что такая машина существует и моделирует другие машины с не более чем квадратичным замедлением (то есть если исходная машина произвела t шагов, то универсальная произведёт не более ct 2 ). Доказательство у этой теоремы конструктивное (такую машину несложно построить, надо только аккуратно её описать). Теорема была предложена и доказана Тьюрингом в 1936-37 г.

Программная реализация на языке программирования Delphi достаточно проста. С одной из таких реализаций можно ознакомиться на сайте http://kleron.ucoz.ru/load/24-1-0-52 . Предусмотрена возможность загрузки и сохранения в файл Excel.

Недетерминированная машина Тьюринга

Вероятностная машина Тьюринга

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

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

Существует также альтернативное определение:

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

Класс алгоритмов, завершающихся за полиномиальное время на вероятностной машине Тьюринга и возвращающих ответ с ошибкой менее 1/3, называется классом BPP .

До сих пор нам было удобно ссылаться на программистский опыт , говоря об алгоритмах, программах, интерпретаторах, пошаговом выполнении и т.д. Это позволяло нам игнорировать детали построения тех или иных алгоритмов под тем предлогом, что читатель их легко восстановит (или хотя бы поверит все-таки не каждый читатель в своей жизни писал интерпретатор паскаля на паскале).

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

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

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

Машины Тьюринга: определение

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

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

Таким образом, чтобы задать машину Тьюринга, надо указать следующие объекты:

Таблица переходов устроена следующим образом: для каждой пары указана тройка . Здесь сдвиг одно из чисел -1 (влево), 0 (на месте) и 1 (направо). Таким образом, таблица переходов есть функция типа S x A -> S x A x {-1,0,1} , определенная на тех парах, в которых состояние не является заключительным.

Остается описать поведение машины Тьюринга. В каждый момент имеется некоторая конфигурация , складывающаяся из содержимого ленты (формально говоря, содержимое ленты есть произвольное отображение Z -> A ), текущей позиции головки (некоторое целое число ) и текущего состояния машины (элемент S ). Преобразование конфигурации в следующую происходит по естественным правилам: мы смотрим в таблице, что надо делать для данного состояния и для данного символа, то есть выясняем новое состояние машины, меняем символ на указанный и после этого сдвигаем головку влево, вправо или оставляем на месте. При этом, если новое состояние является одним из заключительных, работа машины заканчивается. Остается договориться, как мы подаем информацию на вход машины и что считается результатом ее работы. Будем считать, что алфавит машины, помимо пробела, содержит символы 0 и 1 (а также, возможно, еще какие-то символы). Входом и выходом машины будут конечные последовательности нулей и единиц (двоичные слова). Входное слово записывается на пустой ленте, головка машины ставится в его первую клетку, машина приводится в начальное состояние и запускается. Если машина останавливается, результатом считается двоичное слово , которое можно прочесть, начиная с позиции головки и двигаясь направо (пока не появится символ, отличный от 0 и 1 ).

Таким образом, любая машина Тьюринга задает некоторую частичную функцию на двоичных словах. Все такие функции естественно назвать вычислимыми на машинах Тьюринга .

Машины Тьюринга: обсуждение

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

Как понять, какие изменения безобидны, а какие нет? Видимо, тут необходим некоторый опыт практического программирования на машинах Тьюринга, хотя бы небольшой. После этого уже можно представлять себе возможности машины, не выписывая программы полностью, а руководствуясь лишь приблизительным описанием. В качестве примера опишем машину, которая удваивает входное слово (изготавливает слово XX , если на входе было слово X ).

Если машина видит пробел ( входное слово пусто), она кончает работу. Если нет, она запоминает текущий символ и ставит пометку (в алфавите помимо символов 0 и 1 будут еще их " помеченные варианты" и ). Затем она движется направо до пустой клетки, после чего пишет там копию запомненного символа. Затем она движется налево до пометки; уткнувшись в пометку, отходит назад и запоминает следующий символ и так далее, пока не скопирует все слово .

Имея некоторый опыт , можно за всеми этими фразами видеть конкретные куски программы для машины Тьюринга. Например, слова " запоминает символ и движется направо" означают, что есть две группы состояний, одна для ситуации, когда запомнен нуль, другая когда запомнена единица , и внутри каждой группы запрограммировано движение направо до первой пустой клетки.

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

77 . Покажите, что функция " обращение", переворачивающая слово задом наперед, вычислима на машине Тьюринга.

Другой пример неформального рассуждения: объясним, почему можно не использовать дополнительных символов, кроме 0 , 1 и пустого символа. Пусть есть машина с большим алфавитом из N символов. Построим новую машину, которая будет моделировать работу старой, но каждой клетке старой будет соответствовать блок из k клеток новой. Размер блока (число k ) будет фиксирован так, чтобы внутри блока можно было бы закодировать нулями и единицами все символы большого алфавита. Исходные символы 0 , 1 и пустой будем кодировать как 0 , за которым идут (k-1) пустых символов, 1 , за которым идут (k-1) пустых символов, и группу из k пустых символов. Для начала надо раздвинуть буквы входного слова на расстояние k , что можно сделать без дополнительных символов (дойдя до крайней буквы, отодвигаем ее, затем дойдя до следующей, отодвигаем ее и крайнюю и так далее); надо только понимать, что можно идентифицировать конец слова как позицию, за которой следует более k пустых символов. Ясно, что в этом процессе мы должны хранить в памяти некоторый конечный объем информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (е конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.

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

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

В каждой машине Тьюринга есть две части:

1) неограниченная в обе стороны лента , разделенная на ячейки;

2) автомат (головка для считывания/записи, управляемая программой).

С каждой машиной Тьюринга связаны два конечных алфавита : алфавит входных символов A = {a 0 , a 1 , ..., a m }и алфавит состояний Q = {q 0 , q 1 , ..., q p }. (С разными машинами Тьюринга могут быть связаны разные алфавиты A и Q .) Состояние q 0 называется пассивным . Считается, что если машина попала в это состояние, то она закончила свою работу. Состояние q 1 называется начальным . Находясь в этом состоянии, машина начинает свою работу.

Входное слово размещается на ленте по одной букве в расположенных подряд ячейках. Слева и справа от входного слова находятся только пустые ячейки (в алфавит А всегда входит пустая буква а 0 - признак того, что ячейка пуста).

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

Автомат каждый раз “видит” только одну ячейку. В зависимости от того, какую буквуai он видит, а также в зависимости от своего состояния qj автомат может выполнять следующие действия:

• · записать новую букву в обозреваемую ячейку;
• · выполнить сдвиг по ленте на одну ячейку вправо/влево или остаться неподвижным;
• · перейти в новое состояние.

То есть у машины Тьюринга есть три вида операций. Каждый раз для очередной пары (q j , a i ) машина Тьюринга выполняет команду, состоящую из трех операций с определенными параметрами.

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

Клетка (q j , a i ) определяется двумя параметрами - символом алфавита и состоянием машины. Команда представляет собой указание: куда передвинуть головку чтения/записи, какой символ записать в текущую ячейку, в какое состояние перейти машине. Для обозначения направления движения автомата используем одну из трех букв: “Л” (влево), “П” (вправо) или “Н” (неподвижен).

После выполнения автоматом очередной команды он переходит в состояние q m (которое может в частном случае совпадать с прежним состоянием q j ). Следующую команду нужно искать в m -й строке таблицы на пересечении со столбцом a l (букву a l автомат видит после сдвига).

Договоримся, что когда лента содержит входное слово, то автомат находится против какой-то ячейки в состоянии q 1. В процессе работы автомат будет перескакивать из одной клетки программы (таблицы) в другую, пока не дойдет до клетки, в которой записано, что автомат должен перейти в состояние q 0 . Эти клетки называются клетками останова . Дойдя до любой такой клетки, машина Тьюринга останавливается .

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

Машина Поста

Машина Поста (МП) - абстрактная вычислительная машина, предложенная Эмилем Леоном Постом, которая отличается от машины Тьюринга большей простотой. Обе машины «эквивалентны» и были созданы для уточнения понятия «алгоритм».

Принцип работы

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

где i - номер команды, K – действие каретки, j - номер следующей команды (отсылка).

Всего для машины Поста существует шесть типов команд:

1) V j - поставить метку, перейти к j-й строке программы.

2) X j - стереть метку, перейти к j-й строке программы.

3) <- j - сдвинуться влево, перейти к j-й строке программы.

a. j - сдвинуться вправо, перейти к j-й строке программы.

4) ? j1; j2 - если в ячейке нет метки, то перейти к j1-й строке программы, иначе перейти к j2-й строке программы.

5) ! – конец программы (стоп).

У команды «стоп» отсылки нет. После запуска возможны варианты:

Работа может закончиться невыполнимой командой (стирание несуществующей метки или запись в помеченное поле);

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

Что это и кто создал

Алан Тьюринг стремился описать наиболее примитивную модель механического устройства, которая имела бы те же основные возможности, что и компьютер. Тьюринг впервые описал машину в 1936 году в статье "О вычислимых числах с приложением к проблеме разрешимости", которая появилась в Трудах Лондонского математического общества.

Машина Тьюринга является вычислительным устройством, состоящим из головки чтения/записи (или «сканера») с бумажной лентой, проходящей через него. Лента разделена на квадраты, каждый из которых несет одиночный символ - "0" или "1". Назначение механизма состоит в том, что он выступает и как средство для входа и выхода, и как рабочая память для хранения результатов промежуточных этапов вычислений.

Из чего состоит устройство

Каждая такая машина состоит из двух составляющих:

1. Неограниченная лента. Она является бесконечной в обе стороны и разделена на ячейки.
2. Автомат - управляемая программа, головка-сканер для считывания и записи данных. Она может находиться в каждый момент в одном из множества состояний.

Каждая машина связывает два конечных ряда данных: алфавит входящих символов A = {a0, a1, ..., am} и алфавит состояний Q = {q0, q1, ..., qp}. Состояние q0 называют пассивным. Считается, что устройство заканчивает свою работу, когда попадает именно на него. Состояние q1 называют начальным - машина начинает свои вычисления, находясь на старте в нем. Входное слово располагается на ленте по одной букве подряд в каждой позиции. С обеих сторон от него располагаются только пустые ячейки.

Как работает механизм

Машина Тьюринга имеет принципиальное отличие от вычислительных устройств - ее запоминающее приспособление имеет бесконечную ленту, тогда как у цифровых аппаратов такое устройство имеет полосу определенной длины. Каждый класс заданий решает только одна построенная машина Тьюринга. Задачи иного вида предполагают написание нового алгоритма.

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

Свойства механизма

Машина Тьюринга, как и другие вычислительные системы, имеет присущие ей особенности, и они сходны со свойствами алгоритмов:

1. Дискретность. Цифровая машина переходит к следующему шагу n+1 только после того, как будет выполнен предыдущий. Каждый выполненный этап назначает, каким будет n+1.
2. Понятность. Устройство выполняет только одно действие для одной же ячейки. Оно вписывает символ из алфавита и делает одно движение: влево или вправо.
3. Детерминированность. Каждой позиции в механизме соответствует единственный вариант выполнения заданной схемы, и на каждом этапе действия и последовательность их выполнения однозначны.
4. Результативность. Точный результат для каждого этапа определяет машина Тьюринга. Программа выполняет алгоритм и за конечное число шагов переходит в состояние q0.
5. Массовость. Каждое устройство определено над допустимыми словами, входящими в алфавит.

Функции машины Тьюринга

В решении алгоритмов часто требуется реализация функции. В зависимости от возможности написания цепочки для вычисления, функцию называют алгоритмически разрешимой или неразрешимой. В качестве множества натуральных или рациональных чисел, слов в конечном алфавите N для машины рассматривается последовательность множества В - слова в рамках двоичного кодового алфавита В={0.1}. Также в результат вычисления учитывается «неопределенное» значение, которое возникает при «зависании» алгоритма. Для реализации функции важно наличие формального языка в конечном алфавите и решаемость задачи распознавания корректных описаний.

Программа для устройства

Программы для механизма Тьюринга оформляются таблицами, в которых первые строка и столбец содержат символы внешнего алфавита и значения возможных внутренних состояний автомата - внутренний алфавит. Табличные данные являются командами, которые воспринимает машина Тьюринга. Решение задач происходит таким образом: буква, считываемая головкой в ячейке, над которой она в данный момент находится, и внутреннее состояние головки автомата обусловливают, какую из команд необходимо выполнять. Конкретно такая команда находится на пересечении символов внешнего алфавита и внутреннего, находящихся в таблице.

Составляющие для вычислений

Чтобы построить машину Тьюринга для решения одной определенной задачи, необходимо определить для нее следующие параметры.

Внешний алфавит. Это некоторое конечное множество символов, обозначающихся знаком А, составляющие элементы которого именуются буквами. Один из них - а0 - должен быть пустым. Для примера, алфавит устройства Тьюринга, работающего с двоичными числами, выглядит так: A = {0, 1, а0}.

Непрерывная цепочка букв-символов, записываемая на ленту, именуется словом.

Автоматом называется устройство, которое работает без вмешательства людей. В машине Тьюринга он имеет для решения задач несколько различных состояний и при определенно возникающих условиях перемещается из одного положения в другое. Совокупность таких состояний каретки есть внутренний алфавит. Он имеет буквенное обозначение вида Q={q1, q2...}. Одно из таких положений - q1 - должно являться начальным, то есть тем, что запускает программу. Еще одним необходимым элементом является состояние q0, которое является конечным, то есть тем, что завершает программу и переводит устройство в позицию остановки.

Таблица переходов. Эта составляющая представляет собой алгоритм поведения каретки устройства в зависимости от того, каковы в данный момент состояние автомата и значение считываемого символа.

Алгоритм для автомата

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

1. Запись символа внешнего алфавита в позицию, в том числе и пустого, осуществляя замену находившегося в ней, в том числе и пустого, элемента.
2. Перемещение на один шаг-ячейку влево или же вправо.
3. Изменение своего внутреннего состояния.

Таким образом, при написании программ для каждой пары символов либо положений необходимо точно описать три параметра: a i - элемент из выбранного алфавита A, направление сдвига каретки ("←” влево, "→” вправо, "точка” — отсутствие перемещения) и q k - новое состояние устройства. К примеру, команда 1 "←” q 2 имеет значение "заместить символ на 1, сдвинуть головку каретки влево на один шаг-ячейку и сделать переход в состояние q 2 ”.

Машина Тьюринга: примеры

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

Решение. В случае если последняя цифра равняется 9, то ее нужно заменить на 0 и затем прибавить единицу к предшествующему символу. Программа в этом случае для данного устройства Тьюринга может быть написана так:

Здесь q 1 — состояние изменения цифры, q 0 — остановка. Если в q 1 автомат фиксирует элемент из ряда 0..8, то он замещает ее на один из 1..9 соответственно и затем переключается в состояние q 0 , то есть устройство останавливается. В случае если же каретка фиксирует число 9, то замещает ее на 0, затем перемещается влево, останавливаясь в состоянии q 1 . Такое движение продолжается до того момента, пока устройство не зафиксирует цифру, меньшую 9. Если все символы оказались равными 9, они замещаются нулями, на месте старшего элемента запишется 0, каретка переместится влево и запишет 1 в пустую клетку. Следующим шагом будет переход в состояние q 0 - остановка.

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

Состояние q 1: если встречен символ “(”, то совершить сдвиг вправо и переход в положение q 2 ; если определен “a 0 ”, то остановка.

Состояние q 2: проводится анализ скобки “(” на наличие парности, в случае совпадения должно получиться “)”. Если элемент парный, то сделать возврат каретки влево и перейти в q 3 .

Состояние q 3: осуществить удаление сначала символа “(”, а затем “)” и перейти в q 1 .