Основные положения машины Тьюринга

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

3

Содержание

Введение

1. Основные положения машины Тьюринга

2. Алгоритмически неразрешимые проблемы

3. Постановка задачи

4. Выбор структуры данных

5. Решение на языке Haskell

Заключение

Приложение

Введение

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

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

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

1. Основные положения машины Тьюринга

Машина Тьюринга (Turing machine) получила свое название по имени английского математика Алана Тьюринга, предложившего в 1937 г. способ формального задания алгоритмов с помощью некоторой абстрактной машины. Суть работы сводится к следующему. Имеется потенциально бесконечная лента, разбитая на ячейки, в каждой из которых может быть записан один символ из некоторого конечного алфавита. Машина Тьюринга имеет головку чтения/записи, которая позволяет прочитать символ в текущей ячейке, записать символ в ячейку, а также сдвинуть головку влево или вправо в соседнюю ячейку. Машина работает дискретно, по тактам и на каждом такте находится в одном из возможных состояний, которых конечное число. Для каждой пары (состояние, обозреваемый символ) определена тройка (записываемый символ, движение головки, новое состояние). До начала работы машина Тьюринга находится в начальном состоянии, а головка чтения-записи обозревает на ленте самую левую непустую ячейку. Таким образом, обозревая очередной символ, машина записывает новый символ (может быть, тот же самый), сдвигает головку влево, вправо или остается на месте и переходит в новое состояние или остается в прежнем.

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

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



Рисунок 1 Схема машина Тьюринга

Машина Тьюринга работает в некотором произвольном конечном алфавите A = {_, a1…an} - этот алфавит называется внешним. В нем выделяется специальный символ - _, называемый пустым знаком - его посылка в какую-либо ячейку стирает тот знак, который до этого там находился, и оставляет ячейку пустой. В каждую ячейку ленты может быть записан лишь один символ. Информация, хранящаяся на ленте, изображается конечной последовательностью знаков внешнего алфавита, отличных от пустого знака.

Головка всегда расположена над одной из ячеек ленты. Работа происходит тактами (шагами). Система исполняемых головкой команд предельно проста: на каждом такте она производит замену знака в обозреваемой ячейке ai знаком aj. При этом возможны сочетания:

1) аj = аi - означает, что в обозреваемой ячейке знак не изменился;

2) аi ? _, аj = _ - хранившийся в ячейке знак заменяется пустым, т.е. стирается;

3) аi = _, аj ? _ - пустой знак заменяется непустым (с номером j в алфавите), т.е. производится вставка знака;

4) аi ? аj ? _ - соответствует замене одного знака другим.

Таким образом, в машине Тьюринга реализуется система предельно простых команд обработки информации. Эта система команд обработки дополняется также предельно простой системой команд перемещений ленты: на ячейку влево, на ячейку вправо и остаться на месте, т.е. адрес обозреваемой ячейки в результате выполнения команды может либо измениться на 1, либо остаться неизменным. Однако, хотя фактически происходит перемещение ленты, обычно рассматривается сдвиг головки относительно обозреваемой секции. По этой причине команда сдвига ленты влево обозначается R (Right), сдвига вправо - L (Left), отсутствие сдвига - S (Stop). Мы будем говорить именно о сдвиге головки и считать R, L и S командами ее движения. Элементарность этих команд означает, что при необходимости обращения к содержимому некоторой ячейки, она отыскивается только посредством цепочки отдельных сдвигов на одну ячейку. Разумеется, это значительно удлиняет процесс обработки, зато позволяет обойтись без нумерации ячеек и использования команд перехода по адресу, т.е. сокращает количество истинно элементарных шагов, что важно в теоретическом отношении. Обработка информации и выдача команд на запись знака, а также сдвига ленты в машине Тьюринга производится логическим устройством (ЛУ). ЛУ может находиться в одном из состояний, которые образуют конечное множество и обозначаются Q ={q1…qm, q0} , причем состояние q0 соответствует завершению работы, а q1 является начальным (исходным). Q совместно со знаками R, L, S образуют внутренний алфавит машины. ЛУ имеет два входных канала (ai, qi) и три выходных (ai+1, qi+1, Di+1). Схема ЛУ машины Тьюринга изображена на рисунке 2.

Рисунок 2 Схема ЛУ машины Тьюринга

Понимать схему необходимо следующим образом: на такте i на один вход ЛУ подается знак из обозреваемой в данный момент ячейки (ai), а на другой вход - знак, обозначающий состояние ЛУ в данный момент (qi). В зависимости от полученного сочетания знаков (ai, qi) и имеющихся правил обработки ЛУ вырабатывает и по первому выходному каналу направляет в обозреваемую ячейку новый знак (ai+1), подает команду перемещения головки (Di+1 из R, L и S), а также дает команду на переход в следующее состояние (qi+1). Таким образом, элементарный шаг (такт) работы машины Тьюринга заключается в следующем: головка считывает символ из обозреваемой ячейки и, в зависимости от своего состояния и прочитанного символа, выполняет команду, в которой указано, какой символ записать (или стереть) и какое движение совершить. При этом и головка переходит в новое состояние. Схема функционирования такой машины представлена на рисунке 3.

Рисунок 3 Схема функционирования машины Тьюринга

В данной схеме отражено разделение памяти на внешнюю и внутреннюю. Внешняя представлена, как указывалось, в виде бесконечной ленты - она предназначена для хранения информации, закодированной в символах внешнего алфавита. Внутренняя память представлена двумя ячейками для хранения следующей команды в течение текущего такта: в Q передается из ЛУ и сохраняется следующее состояние (qi+1), а в D - команда сдвига (Di+1). Из Q по линии обратной связи qi+1 поступает в ЛУ, а из D команда поступает на исполнительный механизм, осуществляющий при необходимости перемещение ленты на одну позицию вправо или влево.

Общее правило, по которому работает машина Тьюринга, можно представить следующей записью: qi aj > qi' aj' Dk, т.е. после обзора символа aj головкой в состоянии qi в ячейку записывается символ aj', головка переходит в состояние qi', а лента совершает движение Dk. Для каждой комбинации qi aj имеется ровно одно правило преобразования (правил нет только для q0, поскольку, попав в это состояние, машина останавливается). Это означает, что логический блок реализует функцию, сопоставляющую каждой паре входных сигналов qi aj одну и только одну тройку выходных qi'aj'Dk - она называется логической функцией машины и обычно представляется в виде таблицы (функциональной схемой машины), столбцы которой обозначаются символами состояний, а строки - знаками внешнего алфавита. Если знаков внешнего алфавита n, а число состояний ЛУ m, то, очевидно, общее число правил преобразования составит nЧm.

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

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

Перед началом работы на пустую ленту записывается исходное слово a конечной длины в алфавите A; головка устанавливается над первым символом слова a, ЛУ переводится в состояние q1 (т.е. начальная конфигурация имеет вид q1a). Поскольку в каждой конфигурации реализуется только одно правило преобразования, начальная конфигурация однозначно определяет всю последующую работу машины, т.е. всю последовательность конфигураций вплоть до прекращения работы.

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

1) после конечного числа тактов машина останавливается по команде остановки; при этом на ленте оказывается конечная конфигурация, соответствующая выходной информации;

2) остановки не происходит.

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

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

2. Алгоритмически неразрешимые проблемы

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

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

Успехи математики к концу XIX века привели к формированию мнения, которое выразил Д. Гильберт - «в математике не может быть неразрешимых проблем», в связи с этим формулировка проблем Гильбертом на конгрессе 1900 года в Париже была руководством к действию, констатацией отсутствия решений в данный момент.

Первой фундаментальной теоретической работой, связанной с доказательством алгоритмической неразрешимости, была работа К. Гёделя - его известная теорема о неполноте символических логик. Это была строго формулированная математическая проблема, для которой не существует решающего ее алгоритма. Усилиями различных исследователей список алгоритмически неразрешимых проблем был значительно расширен. Сегодня принято при доказательстве алгоритмической неразрешимости некоторой задачи сводить ее к ставшей классической задаче - «задаче останова».

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

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

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

а) отсутствие общего метода решения задачи.

Проблема 1: распределение девяток в записи числа .

Определяется функция f(n) = i, где n - количество девяток подряд в десятичной записи числа , а i - номер самой левой девятки из n девяток подряд: =3,141592… f(1) = 5.

Задача состоит в вычислении функции f(n) для произвольно заданного n.

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

Проблема 2: вычисление совершенных чисел.

Совершенные числа - это числа, которые равны сумме своих делителей, например: 28 = 1+2+4+7+14.

Определется функция S(n) = n-ое по счёту совершенное число и ставится задача вычисления S(n) по произвольно заданному n. Нет общего метода вычисления совершенных чисел, не известно даже, множество совершенных чисел конечно или счетно, поэтому алгоритм должен перебирать все числа подряд, проверяя их на совершенность. Отсутствие общего метода решения не позволяет ответить на вопрос об останове алгоритма;

Проблема 3: десятая проблема Гильберта.

Пусть задан многочлен n-ой степени с целыми коэффициентами - P, су-ществует ли алгоритм, который определяет, имеет ли уравнение P=0 решение в целых числах?

Ю.В. Матиясевич показал, что такого алгоритма не существует, т.е. отсутствует общий метод определения целых корней уравнения P=0 по его целочисленным коэффициентам;

б) информационная неопределенность задачи;

в) логическая неразрешимость.

Проблема 1: проблема «останова»;

Проблема 2: проблема эквивалентности алгоритмов.

По двум произвольным заданным алгоритмам (например, по двум машинам Тьюринга) определить, будут ли они выдавать одинаковые выходные результаты на любых исходных данных;

Проблема 3: проблема тотальности.

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

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

В частности, проблема останова так же является частично разрешимой проблемой, а проблемы эквивалентности и тотальности не являются таковыми.

3. Постановка задачи

Машина Тьюринга должна обладать всеми свойствами алгоритма:

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

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

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

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

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

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

тьюринг алгоритм абстрактный

4. Выбор структуры данных

Так как машина Тьюринга задаётся множеством состояний Q, каждое из которых имеет вид qiaj>qi1aj1dk, , то на языке Haskell это множество задаётся с помощью константы machine, равной списку кортежей, каждый из которых имеет структуру (qi, aj, aj1, dk, qi1).

Поскольку мы будем работать с десятичными числами, то внутренний алфавит машины Тьюринга зададим как `1', `2', `3', `4', `5', `6', `7', `8', `9', `0', и пустой символ - `_'.

Для задания самой ленты разумнее всего выбрать список символов. То есть число 123 будет представлено в виде ['1','2','3'], однако поскольку в языке Haskell есть строковый тип данных, представляющий собой как раз список символов, то в Haskell можно просто заключить число в “”. Поэтому число 123 можно представить в виде “123”.

5. Решение на языке Haskell

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

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

Для реализации на Haskell машины Тьюринга был определён следующий список основных функций:

get_next

get_direction

get_new_symbol

get_new_state

rewrite_symbol

get_structure

get_n_elem

get_second_elem

get_first_elem

turing

Также создана функция start, она «запускает» работу машины Тьюринга (функции turing), используя стартовое состояние Q1. Строка символов str реверсируется, а также в начало и в конец добавляются символы «_», которые «ограничивают» строку. Сначала символ «_» добавляется в начало списка, затем список реверсируется, и снова добавляется пустой символ в начало списка. Реверсирование списка необходимо, так как умножение будет происходить начиная с последнего разряда, для реализации возможности переноса единицы в старший разряд.

Функция get_next в зависимости от выбранного направления получает номер следующего элемента. Если необходимо движение вправо, то к значению текущего положения прибавляется единица, если необходимо движение влево, то единица вычитается. В противном случае значение остается неизменным.

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

Функция get_new_symbol получает из кортежа символ, который нужно записать (значение с).

Функция get_new_state получает из кортежа новое состояние машины (значение е).

Функция rewrite_symbol вставляет новый символ на нужную позицию заменяя старый. Новый символ возвращает функция get_new_symbol.

Функция get_structure находит в списке machine нужный кортеж по заданным первым 2 его элементам.

Функция get_n_elem находит в списке n-ый элемент.

Функции get_first_elem и get_second_elem возвращают соответственно первый и второй элемент кортежа.

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

Заключение

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

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

Приложение А

Листинг программы на языке Haskell

type Structure a b c= (a,b,b,c,a)

data States = Q0|Q1|Q2|Q3

deriving (Eq, Show, Ord) --Состояния машины

data Directions = Right_|Left_|Stop_

deriving (Eq, Show, Ord) --Перемещения считывающей головки

machine :: [Structure States Char Directions]

machine =

{-q1-} [ (Q1,'_','_',Right_,Q2),

{-q2-} (Q2,'_','_',Stop_,Q0), (Q2,'0','0',Right_,Q2), (Q2,'1','2',Right_,Q2), (Q2,'2','4',Right_,Q2), (Q2,'3','6',Right_,Q2),

(Q2,'4','8',Right_,Q2), (Q2,'5','0',Right_,Q3), (Q2,'6','2',Right_,Q3), (Q2,'7','4',Right_,Q3), (Q2,'8','6',Right_,Q3), (Q2,'9','8',Right_,Q3),

{-q3-} (Q3,'_','1',Stop_,Q0), (Q3,'0','1',Right_,Q2), (Q3,'1','3',Right_,Q2), (Q3,'2','5',Right_,Q2), (Q3,'3','7',Right_,Q2),

(Q3,'4','9',Right_,Q2), (Q3,'5','1',Right_,Q3), (Q3,'6','3',Right_,Q3), (Q3,'7','5',Right_,Q3), (Q3,'8','7',Right_,Q3),

(Q3,'9','9',Right_,Q3)]

--Точка входа

start :: String -> String

start str = turing Q1 (head new_str) new_str 1 --Вызываем функцию turing с начальным

where new_str = '_' : ( reverse ( '_' : str)) --состоянием, указатель на начало

turing :: States -> Char -> String -> Int -> String

--Базовый случай

turing Q0 _ str _ = reverse str

--Общий случай

turing state_ char_ string_ n = turing (new_state) (next_char) (new_string) (new_n)

where

structure = get_structure machine state_ char_ --Получаем кортеж из "таблицы"

new_state = get_new_state structure --Новое состояние машины

new_string = rewrite_symbol (string_) (get_new_symbol structure) n --Лента с новым символом

new_n = get_next (state_) (char_) n --Номер следующего символа

next_char = get_n_elem (string_) (new_n) --Следующий символ ленты--

get_first_elem :: (a,b,c,d,e) -> a --Получает первый элемент кортежа

get_first_elem (a,b,c,d,e) = a

get_second_elem :: (a,b,c,d,e) -> b --Получает второй элемент кортежа

get_second_elem (a,b,c,d,e) = b

get_n_elem :: String -> Int -> Char

get_n_elem (x : xs) 1 = x

get_n_elem (x: xs) n = get_n_elem xs (n-1)

get_structure :: [Structure States Char Directions] -> States -> Char -> Structure States Char Directions

get_structure list state_ char_

| (get_first_elem (head list) == state_) && (get_second_elem (head list) == char_) = head(list)

| otherwise = get_structure (tail list) state_ char_

rewrite_symbol :: String -> Char -> Int -> String

rewrite_symbol str char_ n = (reverse ((char_) : reverse (take (n-1) str))) ++ (drop n str)

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

...