Проблема остановки машины Тьюринга

Размещено на http://www.allbest.ru/

КАБАРДИНО-БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ИМ. Х.М. БЕРБЕКОВА

МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА ИНФОРМАТИКИ И МАТЕМАТИЧЕСКОГО ОБЕСПЕЧЕНИЯ АВТОМАТИЗИРОВАННЫХ СИСТЕМ

Курсовая работа

Проблема остановки машины Тьюринга

Выполнил студент 2 курса МФ отделения

«Прикладная математика и информатика»

очной формы обучения А.А. Вологиров

Научный руководитель

к.т.н., доцент Л.З.-Г. Шауцукова

Нальчик - 2014



Содержание

Введение

1. Определение машины Тьюринга

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

3. Способы задания машин Тьюринга, операции над ними

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

3.2 Проблема вычислимости машины Тьюринга

4. Множество граничных конфигураций. Достаточные условия разрешимости проблемы остановки

5. Машины Тьюринга с двумя символами и не более чем тремя состояниями

Заключение

Список литературы



Введение

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

Проблема остановки машины Тьюринга - это проблема построения такого алгоритма, который мог бы определить закончится или нет вычисление по некоторой задаче. Оказывается, что в общем случае такой алгоритм нельзя построить в принципе, то есть невозможно найти алгоритм, позволяющий по произвольной машине Тьюринга Т и произвольной ее начальной конфигурации q_ia_j определить придет ли машина Т в заключительное состояние q₀, если начнет работу в этой конфигурации.

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

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

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

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

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



1. Определение машины Тьюринга

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

Машина Тьюринга (МТ) - это математическая модель идеализированной цифровой вычислительной машины.[8]

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

Перейдем к подробному описанию машины Тьюринга.

Для описания алгоритма МТ удобно представлять некоторое устройство, состоящее из четырех частей: ленты, считывающей головки, устройства управления и внутренней памяти. [5,6,8]

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

1. Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, ...

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

2. Считывающая головка (некоторый считывающий элемент) перемещается вдоль ленты так, что в каждый момент времени она обозревает ровно одну ячейку ленты. Головка может считывать содержимое ячейки и записывать в нее новый символ из алфавита А. В одном такте работы она может сдвигаться только на одну ячейку вправо (П), влево (Л) или оставаться на месте (Н). Обозначим множество перемещений (сдвига) головки D = {П, Л, Н}. Если в данный момент времени t головка находится в крайней клетке и сдвигается в отсутствующую клетку, то пристраивается новая пустая клетка, над которой окажется головка в момент t +1.

3. Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний . Будем считать, что мощность |Q| > 2. Два состояния машины имеют особое значение: q₁ - начальное внутреннее состояние (начальных внутренних состояний может быть несколько), q₀ - заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоянием.

4. Устройство управления в каждый момент t в зависимости от считываемого в этот момент символа на ленте и внутреннего состояния машины выполняет следующие действия: 1) изменяет считываемый в момент t символ на новый символ (в частности оставляет его без изменений, т. е. ); 2) передвигает головку в одном из следующих направлений: Н,Л, П; 3) изменяет имеющееся в момент t внутреннее состояние машины на новое , в котором будет машина в момент времени t +1 (может быть, что ). Такие действия устройства управления называют командой, которую можно записать в виде:

где - внутреннее состояние машины в данный момент; - считываемый в этот момент символ; - символ, на который изменяется символ (может быть ); символ D есть или Н, или Л, или П и указывает направление движения головки; q _j - внутреннее состояние машины в следующий момент (может быть ). Выражения и называются левой и правой частями этой команды соответственно. Число команд, в которых левые части попарно различны, является конечным числом, так как множества Q \ {q₀} и A конечны.

Не существует команд с одинаковыми левыми частями, т. е. если программа машины T содержит выражения и , то или и D {П, Л, Н}.

Совокупность всех команд называется программой машины Тьюринга. Максимальное число команд в программе равно (n +1) * m, где n +1 = A и m +1 = Q|. Считается, что заключительное состояние команды q₀ может стоять только в правой части команды, начальное состояние q₁ может стоять как в левой так и в правой части команды.

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

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



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

Работа машины полностью определяется заданием в первый (начальный) момент: 1) слова на ленте, т. е. последовательности символов, записанных в клетках ленты (слово получается чтением этих символов по клеткам ленты слева направо); 2) положения головки; 3) внутреннего состояния машины. Совокупность этих трех условий (в данный момент) называется конфигурацией (в данный момент). Обычно в начальный момент внутренним состоянием машины является q₁, а головка находится либо над первой слева, либо над первой справа клеткой ленты.

Заданное слово на ленте с начальным состоянием q₁ и положение головки над первым словом называется начальной конфигурацией [8]. В противном случае говорят, что машина Тьюринга не применима к слову начальной конфигурации.

Другими словами, в начальный момент конфигурация представима в следующем виде: на ленте, состоящей из некоторого числа клеток, в каждой клетке записан один из символов внешнего алфавита A, головка находится над первой слева или первой справа клеткой ленты и внутренним состоянием машины является q₁. Получившееся в результате реализации этой команды слово на ленте и положение головки называется заключительной конфигурацией.[1,2,8]

Например, если в начальный момент на ленте записано слово , то начальная конфигурация будет иметь вид:

Под клеткой, над которой находится головка, указывается внутреннее состояние машины.

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

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

Если в работе машины Тьюринга в некоторый момент t выполняется команда, правая часть которой содержит q₀ , то в такой момент работа машины считается законченной, и говорят, что машина применима к слову на ленте в начальной конфигурации. В самом деле, q₀ не встречается в левой части ни одной команды - этим и объясняется название q₀ «заключительное состояние». Результатом работы машины в таком случае считается слово, которое будет записано на ленте в заключительной конфигурации, т. е. в конфигурации, в которой внутреннее состояние машины есть q₀ . Если же в работе машины ни в один из моментов не реализуется команда с заключительным состоянием, то процесс вычисления будет бесконечным. В этом случае говорят, что машина не применима к слову на ленте в начальной конфигурации.



3. Способы задания машин Тьюринга, операции над ними

Рассмотрим три основные операции, применяемые над машинами Тьюринга.[8]

1. Пусть машины Тьюринга Т₁ и Т₂ имеют соответственно программы П₁ и П₂. - заключительное состояние Т₁, - начальное состояние Т₂. Предположим, что внутренние алфавиты этих машин не пересекаются. Заменим везде в программе П₁ состояние на состояние и полученную программу объединим с программой П₂. Новая программа П определяет машину Т, которая называется композицией машин Т и Т? (по паре состояний (, )) и обозначается Т_{1 o} Т₂ или Т₁Т₂ . Более подробная запись полученной машины будет выглядеть - Т = = Т(Т₁, Т₂, (, )). Внешний алфавит композиции Т_1oТ₂ является объединением алфавитов машин Т1 и Т2.

2. Пусть q₀ - некоторое заключительное состояние машины Т, а q_k - какое-либо состояние этой же машины Т, не являющееся заключительным. Заменим всюду в программе П машины Т символ q₀ на q_k. В результате получим программу П', которая определяет машину Т' (q₀, q_k). Машина Т' называется итерацией машины Т по паре состояний (q₀, q_k).

3. Пусть машины Тьюринга Т₁, Т₂ и Т₃ задаются программами П₁, П₂ и П₃ соответственно. Внутренние алфавиты этих машин не пересекаются. Пусть и - какие-либо заключительные состояния машины Т₁. Заменим в программе П₁ состояние некоторым начальным состоянием машины Т2, а состояние некоторым начальным состоянием машины Т₃. Затем новую программу объединим с программами П₂ и П₃. Получим программу П, задающую машину Тьюринга Т = Т(Т₁(, ),(, ),Т₃), которая называется разветвлением машин Т9 и Т3, управляемым машиной Т.

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

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

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

Имеет место быть следующая теорема: не существует алгоритма (машины Тьюринга), позволяющего по описанию произвольного алгоритма и его исходных данных (и алгоритм и данные заданы символами на ленте машины Тьюринга) определить, останавливается ли этот алгоритм на этих данных или работает бесконечно.[6]

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

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

Проблема остановки машины Тьюринга формулируется следующим образом: дана машина Тьюринга в произвольной конфигурации со строкой непустых ленточных символов конечной длины. Остановиться ли она в конце концов? [4]

Говорят, что эта проблема рекурсивно не разрешима в том смысле, что не существует алгоритма, который для каждой Tm и каждой конфигурации определял бы, остановится ли машина когда-нибудь. Это совсем не значит, что мы не можем определить, остановится ли конкретная Tm в конкретной ситуации.

При описании универсальной машины Тьюринга мы имели кодирование для любой Tm с ленточными символами 0, 1 и B.

Кодированием была цепочка из

{0, 1, c, L, R}*

Мы можем перенумеровать все такие цепочки, перечисляя их в порядке возрастания длины. Цепочки одинаковой длины упорядочиваются в соответствии со значением строки по основанию 5. Предполагается, что эти 5 символов играют роль целых 0, 1, 2, 3, 4 в каком-нибудь порядке. Аналогичным образом цепочки из множества {0, 1}* могут быть тоже упорядочены. Первыми цепочками являются е, 0, 1, 00, 01, 10, 11, 000, 001, ... Таким образом, имеет смысл говорить об i-й цепочке в множестве {0, 1}* Если мы предположим, что каждая цепочка из множества {0, 1, c, L, R}* является машиной Тьюринга (некоторые цепочки будут образованы неправильно - они рассматриваются как Tm без каких-нибудь движений), то также имеет смысл говорить о j-й машине Тьюринга, т.е. о машине, представленной j-й цепочкой из множества {0, 1, c, L, R}*

Рассмотрим язык = { | не принимается }. Ясно, что язык не мог бы приниматься никакой . Если бы это не было так, то существовала бы некоторая машина Тьюринга, скажем , которая бы принимала язык . Возьмем, цепочку . Если ?, то по определению языка не принимается машиной . С другой стороны, машина распознает язык , стало быть принимает ?.

Наше допущение привело к противоречию. Если ?, то не принимается машиной , но тогда по определению языка принимается машиной . Опять противоречие. Остается признать, что язык не принимается никакой Tm.

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

1. Пусть x? на ее входе. Прежде всего, она перечисляет предложения x1, x2, ... до тех пор, пока не обнаружит, что некоторое . Таким образом определяет, что x является i-м предложением в этом перечислении.

2. Затем генерирует код машины Тьюринга .

3. Управление теперь передается машине T0, которая может определить, останавливается с входной цепочкой или нет.

4. Если установлено, что не останавливается с входной цепочкой (т.е. не принимает ), то машина T останавливается и принимает.

5. Если же установлено, что останавливается с входной цепочкой , то управление передается универсальной машине Тьюринга, которая моделирует машину Ti с входной цепочкой .

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

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

Теорема 1.1. Не существует алгоритма (машины Тьюринга, которая гарантированно останавливается) для определения, остановится ли в конце концов произвольная машина Тьюринга, начиная в произвольно заданной конфигурации. [3]

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

Если в машине Тьюринга T, которая кодируется, д(i, a) = ( j, b, D), то подблок, соответствующий состоянию i и входному символу a, будет содержать j единиц, за которыми следует символ D ?{L, R}, а за ним b ? {0, 1}. Если д(i, a) не определено, то соответствующий подблок будет содержать единственный нуль. Так же надо выделить состояния, при которых машина остановится: терминальные (допускающие) состояния. Иначе она будет вечно бегать по бесконечной ленте. Машина Тьюринга не решает проблему остановки. Даны описание алгоритма и его начальные входные данные, требуется определить, сможет ли выполнение алгоритма с этими данными завершиться когда-либо. Альтернативой этому является то, что он работает всё время без остановки. Назовем Анализатором гипотетический алгоритм, который получает на вход пару натуральных чисел(N,X), и

- останавливается и возвращает 1, если другой алгоритм с номером N не останавливается, получив на вход X;

- не останавливается в противном случае (если другой алгоритм с номером N останавливается, получив на вход X);

Если применить алгоритм к самому себе, то он не сможет работать, потому что должен будет остановиться тогда, когда он сам не останавливается, и не останавливаться в том случае, если он сам остановится.

3.2 Проблема вычислимости машины Тьюринга

Проблема вычислимости заключается в том, что есть такие алгоритмы, результат действия которых мы не можем вычислить. Примером такого алгоритма является бесконечная снежинка Коха:[5]

1. Мы рисуем треугольник;

2. На следующем шаге на каждой его стороне мы рисуем еще по треугольнику;

3. На следующем - на каждом из полученных треугольников еще по треугольнику;

4. И так на каждом последующем шаге мы рисуем по треугольнику на каждом из треугольников, полученных на предыдущем шаге (вот так, как это показано на картинке);

Проблема: если мы поставим рядом с такой снежинкой точку, то мы не можем определить, попадет ли эта точка в снежинку, когда та будет разрастаться, на определенном шаге реализации этого алгоритма. Если точка не попадет в снежинку на 55-м шаге, мы не знаем, случится ли это на 70-м или на 125-м шаге - алгоритм бесконечен.

4. Множество граничных конфигураций. Достаточные условия разрешимости проблемы остановки

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

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

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

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

Рассмотрим множество вычислений из на словах длины п. Отбросим те из бесконечных вычислений рассматриваемого множества, в которых головка ни разу не выходит левее ,если она начала работать в , или правее , если она начала работать в . Для остальных вычислений обозначим максимальное число тактов от начала работы до ближайшего из двух возможных событий: «вычисление закончилось» и «головка вышла за конец участка , отличный от того, на котором она начала работать».

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

Лемма 1. Если функция вычислима, то существует алгоритм, позволяющий для любой начальной конфигурации и любого определить, содержит ли соответствующее вычисление этап , а если вычисление содержит этапов, то заканчивается ли оно.[7]

Доказательство. Пусть нам известно, что некоторое вычисление содержит . Тогда можно определить машинную конфигурацию в момент t первого посещения головкой ячейки . Для определенности положим, что на этапе головка уходит из налево. После этого оказывается возможным ответить на вопрос, существует ли , а если не существует, то конечный ли . После момента t должно произойти одно из четырех событий: 1 - 2) головка остается на и останавливается или работает бесконечно; 3 - 4) головка впервые покидает выходя правее или левее . В случаях 1) - 3) ответ очевиден. В четвертом случае для ответа на поставленный вопрос вычисляем длину участка и просматриваем еще тактов вычисления. Если за это время головка остановилась, то - последний этап, а если она вышла правее , то существует . Если же головка не остановилась и не вышла правее , этап Е_т - бесконечный. В случае, когда на этапе Е_т головка из уходит направо, рассуждение дословно повторяет предыдущее с той лишь разницей, что вместо рассматривается

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

Теорема 1. Если функции и вычислимы, то проблема остановки разрешима для Z.[7]

Доказательство. Сделаем одно предварительное замечание. По одному из свойств разбиений вычислений на этапы для просмотра входного слова длины п требуется не более 2п -1 этапов, а значит, участок ленты, ограниченный ячейками и , содержит , в себе или совпадает с ним. Таким образом, к моменту начала работы головки на концами слова являются ячейки и . На этапе головка уходит с участка, ограниченного и т.е. осуществляется граничная конфигурация. Перейдем непосредственно к доказательству теоремы. Рассмотрим произвольное вычисление на слове длины п. Из леммы 1 вытекает, что существует алгоритм, позволяющий определить, содержит ли это вычисление этап , а если оно содержит меньшее число этапов, то заканчивается ли оно. Для тех вычислений, которые содержат , определяем конфигурацию в момент t ухода головки с участка, ограниченного ячейками и . По сделанному выше замечанию, эта конфигурация принадлежит . Вычисляем длину участка ленты, просмотренного головкой за t тактов работы, и определяем, содержит ли вычисление еще хотя бы этапов, а в случае, когда оно после содержит не более этапов, заканчивается ли оно. Заметим следующее. Если конечное вычисление на слове длины начинается с граничной конфигурации, то число полных этапов после выхода головки за конец слова, противоположный тому, на котором она начала работать, не превосходит . Поэтому, если рассматриваемое вычисление после содержит более этапов, оно бесконечно. Теорема доказана.



5. Машины Тьюринга с двумя символами и не более чем
тремя состояниями

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

Чтобы Z была О-машиной, должны выполняться три условия: 1, 2 и За (3б).

Множество - выметаний 1 -1 - -регулярно.

Для любого входного символа х почти все - выметания имеют на х продолжения одного типа.

За. Множество - слов 1- 1- 0 - регулярно.

36. Множество - выметаний - регулярно.

Будем рассматривать только машины с входным алфавитом из двух символов -0 и 1, причем в качестве пустого символа используется 0. Машинами (2, s) назовем машины с числом внутренних состояний головки, равным s.

Теорема. Для любой из машин (2, 2) или (2, 3) проблема остановки разрешима.[7]

Лемма 1. Любая из машин (2, 5), программа которой содержит только одну левую команду, является О -машиной, для которой выполнены условия следствия 2.[7]

Доказательство. Если в программе машины имеется только одна левая команда , то след любого L - выметания есть при некотором п, а выполнение его заканчивается в состоянии .Отсюда следует, что почти все продолжения L - выметаний на символе х одного типа, а множество выметаний 1-1- - регулярно. Поэтому любая из рассматриваемых машин является О-машиной. Если , то одностороннее продолжение любого L -выметания отлично от правого. Когда , одностороннее продолжение любого -выметания отлично от левого. Следовательно, для такой машины выполнены условия следствия 2. Лемма 1 доказана.

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

Это означает, в частности, что для машин (2, 2) п.о. разрешима

Рассмотрим теперь машины с программами, содержащими две левые команды. Если для таких машин проблема остановки разрешима, то она будет разрешима и в случае, когда число правых команд в программе равно двум. Отсюда будет вытекать разрешимость проблемы остановки для машин (2, 3). Занумеруем команды любой из рассматриваемых программ так, чтобы левыми командами были . Для удобства просмотра машин (2, 3) введем понятие графа машины, строящегося по ее программе. Каждой команде поставим в соответствие вершину графа. В каждый граф введем вершину «стоп». Вершины графа будем изображать точками, около которых напишем названия соответствующих вершин. От каждой вершиныпроведем стрелку к каждой вершине такой, что Если после этого окажется, что из вершины выходит менее двух стрелок, то из проводим стрелку также к вершине «стоп». Граф любой из машин (2, 3) при подходящей нумерации команд содержит какой-либо подграф, изображенный на рис. 5 или полученный из него заменой одной или нескольких правых вершин вершиной «стоп». Для машин, графы которых содержат подграф вида VII, п. о. разрешима ввиду конечности числа -выметаний. Далее мы рассмотрим последовательно машины типа I-VI и докажем разрешимость п. о. в каждом из этих случаев. Под машиной типа I, или I-машиной, будем понимать машину, граф которой содержит подграф вида I или полученный из I заменой некоторых правых вершин вершиной «стоп». Так же определим I I , . . ., VI машины.

Лемма 2. I-машина есть О-машина, удовлетворяющая условиям или теоремы 7, или следствия 2.[7]

Доказательство. Из структуры подграфа I (рис. 5) видно, что выполнение любого L - выметания дальности, не меньшей 2, заканчивается головкой всегда в состоянии , а след такого выметания есть слово при некотором п. Отсюда, во-первых, следует что если продолжение -выметания С, , на символе х левое, то и для любого -выметания продолжение на х также левое. Во-вторых, множество всех правых продолжений - выметаний на одном и том же символе есть некоторое 1-1- - регулярное множество. Из первого получаем, что множество - выметаний бесконечно только в случае, когда почти все продолжения L - выметаний на одном из символов левые, а на другом -правые. Поэтому множество - выметаний 1-1- - регулярно. Таким образом, любая I-машина есть О-машина. Пусть почти все продолжения L -выметаний на -левые (тогда в графе существует переход ), а на -правые. Если , то выполнены условия следствия 2. Если для некоторого - выметания С С содержит , то множество -выметаний, а значит, и -слов 0 -1 - -регулярно. Пусть ни при каком -выметании & Сх₄ не содержит . Тогда Сх₄ может содержать, только если в графе существуют где C - L -выметание, , т. e. множество - слов 0 - 1- 0 - регулярно. Для машин с 0 - 1- р -регулярным множеством - слов выполнены условия теоремы 7. При продолжения почти всех - выметаний бесконечны, а при продолжения почти всех - выметаний бесконечны, т.е. выполняются условия следствия 2. Лемма 2 доказана.



Заключение

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

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

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



Список литературы

1. Макконнелл Дж. Основы современных алгоритмов. 2-е дополненное издание. - М.: Техносфера, 2004. - с. 310-317.

2. Плотников А. Д. Дискретная математика : учеб. пособие / А. Д. Плотников. - М. : Новое издание, 2005. - 288 с.

3. Фалевич Б.Я. Теория алгоритмов. - М.: ИНФРА-М, 2006. - с. 324.

4. Фалина Н.М. Машина Тьюринга // Информатика. - №26. - 2005.

- с.12-15.

5. Свободная энциклопедия - [Электронный ресурс]. Режим доступа: http://ru.psyphy.wikia.com/wiki/15.

6. Учебный контент - [Электронный ресурс]. Режим доступа: http://ref.rushkolnik.ru/v62794/?page=4

7. Павлоцкая Л. М. О машинах Тьюринга, связных относительно свойства неразрешимости проблемы остановки. //Матем. заметки, 71:5 (2002).

- с. 732-741.

8. Кацарин Т.К, Строева Л.Н. Машины Тьюринга и рекурсивные функции: учеб. пособие / изд.-полиграф. центр, Воронежский гос. университет, 2008. - с. 5-17.

Размещено на Allbest.ru

...