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

КАБАРДИНО–БАЛКАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМ. Х.М. БЕРБЕКОВА

 

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

 

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

АВТОМАТИЗИРОВАННЫХ СИСТЕМ

 

 

 

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

 

 

 

 

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

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

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

 

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

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

 

 

Нальчик – 2014

 

Содержание

 

Введение …………………………………………………….………….……  3

1. Определение машины Тьюринга ……………………………….. …..….  5
2. Работа машины Тьюринга  ………………………………………….....  8

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

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

2. .  Проблема вычислимости машины Тьюринга ……….……..……..         15
4. Множество граничных конфигураций. Достаточные условия

разрешимости проблемы остановки…………………………..……......            16

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

не более чем тремя состояниями …………………....……………..…..         19

Заключение …………………………………..…………………..………. ..            23

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

 

Введение

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

 

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

1. Пусть машины Тьюринга Т1 и Т2 имеют соответственно программы П1 и П2. – заключительное состояние Т1, – начальное состояние Т2. Предположим, что внутренние алфавиты этих машин не пересекаются. Заменим везде в программе П1 состояние на состояние и полученную программу объединим с программой П2. Новая программа П определяет машину Т, которая называется композицией машин Т и Т? (по паре состояний (, )) и обозначается Т1 o Т2 или Т1Т2 . Более подробная запись полученной машины будет выглядеть - Т = = Т(Т1, Т2, (, )). Внешний алфавит композиции Т1oТ2 является объединением алфавитов машин Т1 и Т2.
0.      2.  Пусть q0 – некоторое заключительное состояние машины Т, а qk – какое-либо состояние этой же машины Т, не являющееся заключительным. Заменим всюду в программе П машины Т символ q0 на qk. В результате получим программу П’, которая определяет машину Т’ (q0, qk). Машина Т’ называется итерацией машины Т по паре состояний (q0, qk).

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

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

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