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

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

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

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

Например, алфавит машины Тьюринга, работающей с двоичными числами, задается в виде A = {0, 1, а0}.

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

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

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

Таблица переходов. Описание поведения автомата (каретки) в зависимости от состояния и считанного символа.

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

Записывать символ внешнего алфавита в ячейку (в том числе и пустой), заменяя находившийся в ней (в том числе и пустой).

Передвигаться на одну ячейку влево или вправо.

Менять свое внутреннее состояние.

Поэтому при составлении программы для каждой пары (символ, состояние) нужно определить три параметра : символ ai из выбранного алфавита A, направление перемещения каретки ("←” - влево, "→” - вправо, "точка” - нет перемещения) и новое состояние автомата qk.

Например , команда 1 "←” q2 обозначает "заменить символ на 1, переместить каретку влево на одну ячейку и перейти в состояние q2”.

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

Вопрос 28

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

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

Вопрос 29

Машины Тьюринга с двумя выходами

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

Оказывается, что если заданы две машины Тьюринга T1 и Т2, которые допускают непересекающиеся множества слов Х1 и Х2 соответственно, то всегда можно построить машину Тьюринга T3 с двумя выходами, которая будет допускать Х1 и запрещать Х2. Эти машины Тьюринга будут нам полезны при рассмотрении вопроса о разрешимости.

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

Вопрос 30

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

Каждая лента бесконечна в обоих направлениях. При одном движении, зависящем от состояния конечного управления и сканируемого символа каждой из ленточных головок, машина может: 1) изменить состояние; 2) напечатать новый символ на каждой из сканируемых ячеек; 3) передвинуть каждую из ее ленточных головок независимо друг от друга на одну ячейку влево, вправо или оставить ее на том же месте.

Сначала входная цепочка имеется только на первой ленте, а все другие лен- ты пусты. Мы не будем определять это устройство более формально, предоставляя это читателю.

Теорема 6.2. Если язык L принимается многоленточной машиной Тьюринга, то он принимается одноленточной машиной Тьюринга. Доказательство. Пусть язык L принимается машиной Тьюринга T1 с k лентами. Построим одноленточную машину Тьюринга T2 с 2k дорожками, по две для каждой из лент машины T1. На одной дорожке записывается содержимое соответствующей ленты машины T1, а другая - пустая, за исключением маркера в ячейке, содержащей символ и сканируемой соответствующей головкой машины T1. Такое устройство для моделирования трех лент посредством одной иллюстрируется рис. 6.5. Конечное управление машины T2 запоминает, какие маркеры головок машины T1 находятся слева, а какие - справа от головки T2. Состояния машины T1 тоже запоминаются в конечном управлении машины T2.

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

Который, позаимствовав идею у Эмиля Поста, придумал её, как считается, в 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 пустых символов. Ясно, что в этом процессе мы должны хранить в памяти некоторый конечный объем информации, так что это возможно. После этого уже можно моделировать работу исходной машины по шагам, и для этого тоже достаточно конечной памяти (е конечного числа состояний), так как нам важна только небольшая окрестность головки моделируемой машины. Наконец, надо сжать результат обратно.

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

В гл. XII были разъяснены основные интуитивно очевидные требования, которые предъявляются к алгоритмам. Это требования детерминированности, массовости и применимости («целенаправленности») алгоритмов. Важно, что результат применения алгоритма совершенно не зависит от того, кто его использует. Человек, выполняющий алгоритм, должен действовать, «как машина», заботясь лишь о том, чтобы правильно выполнить предписания. Поэтому, естественно, возникает мысль: нельзя ли действительно поручить выполнение алгоритма машине?

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

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

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

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

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

Управляющее устройство имеет конечное число внутренних состояний и работает в дискретном времени . Входом управляющего устройства являются символы , выдаваемые считывающей и записывающей головкой, выходом - команды на действия головки: какой символ головка должна записать в соответствующей ячейке и куда передвинуться. Пусть в момент времени t считывающая и записывающая головка находилась напротив (считая слева) ячейки, в которой был записан символ , а управляющее устройство находилось в состоянии . Управляющее устройство в зависимости от состояния и входа выдает символ (в соответствии с которым головка стирает старый символ и печатает новый ), а затем один из символов П, Л или С («право»? «лево», "стоп"), в соответствии с которым головка передвигается на одну клетку вправо или влево, или остается на месте. После этого управляющее устройство переходит в новое состояние (также определяемое однозначно символами ).

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

Таблица 13.1

Таблица 13.2

Таблица 13.3

Таблица 13.3

Например, если таблица автомата есть табл. 13.1, таблица первого преобразователя - табл. 13.2, второго - табл. 13.3, то совмещенная таблица, целиком описывающая работу машины Тьюринга, имеет вид табл. 13.4.

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

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

2) вторым символом в клетке столбца этой строки является тот же символ (и никогда при );

3) третьим символом в каждой клетке этой строки является символ С (и никогда П или Л) (см. пример табл. 13.5).

Таблица 13.5

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

Таблица 13.6

Таблица 13.7

В дальнейшем для простоты будем предполагать, что алфавит символов состоит всего лишь из двух символов: «пустого» 0 и «непустого» 1.

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

1) Машина А (табл. 13.7). Если в начальный момент машина А находится в состоянии и воспринимает заполненную клетку, то она «отыскивает» на ленте первую пустую (т. е. заполненную символом 0) клетку справа от той, на которой находится головка, «печатает» там символ 1 и останавливается. Если же вначале головка находилась напротив пустой клетки, то машина ее «заполняет» и останавливается, не передвигая головку.

В табл. 13.8 и 13.9 приведены два варианта работы машины.

Таблица 13.8

Черта над соответствующей ячейкой ленты означает, что считывающая и записывающая головка находится в данный момент как раз напротив этой ячейки. Символ над чертой - состояние управляющего устройства в этот момент.

Таблица 13.9

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

2) Машина В (табл. 13.10). Эта машина имеет также лишь одно состояние (не считая состояния покоя). Она «стирает» единицу в той ячейке, где находится головка (если эта ячейка непуста), или в первой слева непустой ячейке, передвигает головку еще левее на ячейку и останавливается. Один вариант работы машины В приведен в табл. 13.11.

Таблица 13.10

Таблица 13.11

3) Машина С (табл. 13.12). Эта машина отыскивает первую после группы нулей группу единиц справа от начальной ячейки и останавливается около последней из этих единиц. Вариант работы машины С приведен в табл. 13.13.

Таблица 13.12,

Таблица 13.13

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

Таблица 13.14

4) Машина D (табл. 13.14). Эта машина заполняет первый промежуток справа между двумя группами единиц, оставляя всего одну незаполненную ячейку. Если головку машины в нулевой такт не помещать напротив пустой ячейки в состоянии , то сочетания и никогда не встретятся и в дальнейшем: состояние вообще никогда не повторится, а в машина может прийти лишь тогда, когда единица уже напечатана. Вариант работы машины приведен в табл. 13.15.

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

Что такое формальный исполнитель? Что значит — один формальный исполнитель имитирует работу другого формального исполнителя? Если Вы играли в компьютерные игры — на экране объекты беспрекословно подчиняются командам играющего. Каждый объект обладает набором допустимых команд. В то же время компьютер сам является исполнителем, причем не виртуальным, а реальным. Вот и получается, что один формальный исполнитель имитирует работу другого формального исполнителя.

Рассмотрим работу Машины Тьюринга.

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

Таким образом Машина Тьюринга формально описывается набором двух алфавитов:

A={a1, a2, a3, …, an} — внешний алфавит, служит для записи исходных данных

Q={q1, q2, q3,…, qm} — внутренний алфавит, описывает набор состояний считывающе-печатного устройства.

Каждая ячейка ленты может содержать символ из внешнего алфавита A = {a0,a1,…,an} (В нашем случае A={0, 1})

Допустимые действия Машины Тьюринга таковы:

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

2) сместиться в соседнюю ячейку

3) сменить состояние на одно из обозначенных символом внутреннего алфавита Q

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

Строки в таблице соответствуют символам выбранного алфавита A, а столбцы — состояниям автомата Q = {q0,q1,…,qm}. В начале работы машина Тьюринга находится в состоянии q1. Состояние q0 — это конечное состояние, попав в него, автомат заканчивает работу.

В каждой клетке таблицы, соответствующей некоторому символу ai и некоторому состоянию qj, находится команда, состоящая из трех частей
· символ из алфавита A
· направление перемещения: «>» (вправо), «<» (влево) или «.» (на месте)
· новое состояние автомата

В приведенной выше таблице алфавит A ={0, 1, _} (содержит 3 символа), а внутренний алфавит Q={q1, q2, q3, q4, q0}, q0 — состояние, заставляющее каретку остановиться.

Рассмотрим несколько задач решением. Скачать машину Тьюринга Вы можете на сайте в разделе СКАЧАТЬ .

Задача 1. Пусть A={0, 1, _}. На ленте в ячейках находятся символы из алфавита в следующем порядке 0011011. каретка находится над первым символом. Необходимо составить программу, которая заменит 0 на 1, 1 на 0 и вернет каретку в первоначальное положение.

Теперь определимся с состояниями каретки. Я называю их — «желания каретки что-то сделать».

q1) Каретка должна пойти вправо: если видит 0 меняет его на 1 и остается в состоянии q1, если видит 1 — меняет его на 0 и остается в состоянии q1, если видит _ — возвращается назад на 1 ячейку «желает что-то другое», т. е. переходит в состояние q2. Запишем наши рассуждения в таблицу исполнителя. Синтаксис смотрите в справке к программе)

q2) Теперь опишем «желание каретки» q2. Мы должны вернуться в первоначальное положение. Для этого: если видим 1 оставляем ее и остаемся в состоянии q2 (с тем же желанием дойти до конца ряда символов); если видим 0 — оставляем его и продолжаем двигаться влево в состоянии q2; видим _ — сдвигается вправо на 1 ячейку. Вот вы оказались там, где требуется в условии задачи. переходим в состояние q0.

Посмотреть работу программы можно на видео:

Задача 2. Дано: конечная последовательность 0 и 1 (001101011101). Необходимо выписать их после данной последовательности, через пустую ячейку, а в данной последовательности заменить их на 0. Например:

Из 001101011101 получим 000000000000 1111111.

Как видите, семь единиц записались после данной последовательности, а на их местах стоят нолики.

Приступим к рассуждениям. Определим, какие состояния необходимы каретке и сколько.

q1) увидел 1 — исправь на нолик и перейди в другое состояние q2 (новое состояние вводится, чтобы каретка не поменяла на нули все единицы за один проход)

q2) ничего не менять, двигаться к концу последовательности

q3) как только каретка увидела пустую ячейку, она делает шаг вправо и рисует единичку, если она видит единичку — то движется дальше, чтобы подписать символ в конце. Как только нарисовал единицу, переходим в состояние q4

q4) проходим по написанным единицам, ничего не меняя. Как только доходим до пустой ячейки, разделяющей последовательность от единиц, переходим с новое состояние q5

q5) в этом состоянии идем начало последовательности, ничего не меняя. Доходим до пустой ячейки, разворачиваемся и переходим в состояние q1

Состояние q0 каретка примет в том случае, когда она пройдет в состоянии q1 до конца данной последовательности и встретит пустую ячейку.

Получим такую программу:

Работу Машины Тьюринга можете посмотреть на видео ниже.