Машина Тьюринга «базовые примеры»

Министерство образования и науки РФ

Федеральное государственное автономное образовательное учреждение

высшего профессионального образования

«СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ»

 

ФИЛИАЛ ФЕДЕРАЛЬНОГО ГОСУДАРСТВЕННОГО автономного ОБРАЗОВАТЕЛЬНОГО УЧРЕЖДЕНИЯ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «СИБИРСКИЙ ФЕДЕРАЛЬНЫЙ УНИВЕРСИТЕТ» 
В Г. ЖЕЛЕЗНОГОРСКЕ

 

Курсавая работа на тему

Машина Тьюринга «базовые примеры»

 

Выполнил: Клинов А.А 
«__»________2012г. _________ 
Проверил:  Абросимов Н.В 
«__»________2012г. _________

 

 

 

 

 

 

 

Железногорск 2012

 

 

ВВЕДЕНИЕ

      Слово «алгоритм» происходит от algorithmi – латинского написания имени узбекского математика и астронома, жившего в VIII–IX веках (783-850 гг.), Мухаммеда бен Мусы аль-Хорезми. Под этим именем в Средневековой  Европе знали величайшего математика из Хорезма (город в современном    Узбекистане). В своей книге «Об индийском счете» он сформулировал правила записи натуральных чисел с помощью арабских цифр и правила действий над ними. Затем понятие алгоритма стало использоваться в более широком смысле и не только в математике. Как для математиков, так и для практиков понятие алгоритма имеет важное значение.

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

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

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

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

      Создание алгоритма, пусть даже самого простого, – процесс творческий. Он доступен исключительно живым существам, а долгое время считалось, что только человеку. Другое дело – реализация уже имеющегося алгоритма. Ее можно поручить субъекту или объекту, который не обязан вникать в сущность дела, а возможно, и не способен его понять. Такой субъект или объект принято называть формальным исполнителем. Примером формального исполнителя может служить стиральная машина-автомат, которая неукоснительно исполняет предписанные ей действия, даже если вы забыли положить в нее порошок. Человек тоже может выступать в роли формального исполнителя, но в первую очередь формальными исполнителями являются различные автоматические устройства, и компьютер в том числе. Каждый алгоритм создается в расчете на вполне конкретного исполнителя. Те действия, которые может совершать исполнитель, называются его допустимыми действиями. Совокупность допустимых действий образует систему команд исполнителя. Алгоритм должен содержать только те действия, которые допустимы для данного исполнителя.

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

Алгоритм должен обладать следующими свойствами.

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

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

      Результативность (конечность) – алгоритм должен приводить к решению задачи за конечное число шагов.

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

      Теория алгоритмов – это раздел математики, который изучает общие свойства алгоритмов. Различают качественную и метрическую теорию алгоритмов.

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

      Метрическая теория алгоритмов исследует алгоритм с точки зрения их сложности. Этот раздел теории алгоритмов известен также как алгоритмическая теория сложности.

      При отыскании решений некоторых задач долго не удавалось найти соответствующий алгоритм. Примерами таких задач являются: а) указать способ, согласно которому для любой предикатной формулы за конечное число действий можно выяснить, является ли она тождественно-истинной или нет; б) разрешимо ли в целых числах диофантово уравнение (алгебраическое уравнение с целыми коэффициентами). Так как для решения этих задач найти алгоритмов не удалось, возникло предположение, что такие алгоритмы вообще не существуют, что и доказано: первая задача решена А. Черчем, а вторая – Ю.В. Матиясевичем и Г.В. Чудновским. Доказать это с помощью интуитивного понятия алгоритма в принципе невозможно. Поэтому были предприняты попытки дать точное математическое определение понятия алгоритма. В середине 30-х годов ХХ века С.К. Клини, А.А. Марков, Э. Пост, А. Тьюринг, А. Черч и другие предположили различные математические определения понятия алгоритма. Впоследствии было доказано, что эти различные формальные математические определения в некотором смысле эквиваленты: вычисляют одно и то же множество функций. Это говорит о том, что, по-видимому, основные черты интуитивного понятия алгоритма правильно отражены в этих определениях.

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

 

Алан Тьюринг

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

Алгоритм – одно из таких понятий. И вот настал момент, когда формализация его стала необходима. А. Тьюрингу удалось дать определение понятия "алгоритм". В качестве уточнения понятия он предложил некоторую гипотетическую конструкцию – машину, получившую вскоре название "машина Тьюринга". Он сделал свое изобретение в 1937 г. В то время Тьюринг стажировался в Принстонском университете в США. В Англию он вернулся знаменитым ученым.

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

Машина Тьюринга состоит из трех частей: ленты, головки и управляющего устройства (УУ). Лента бесконечна в обе стороны и разбиты на ячейки. В каждой ячейке может быть записан только один символ. Множество возможных символов образует алфавит машины A =  S1, …, Sk. Отсутствие символа в ячейке обозначается специальным (“пустым”) символом. Головка всегда расположена над некоторой ячейкой ленты. Она может читать и писать символы, стирать их, а также перемещать вдоль ленты. Головка в каждый такт работы находится  в одном из состояний, образующих конечное множество Q = {q1, …, qm}. Среди состояний выделяются начальное состояние q1 и заключительное состояние qz.

 

Математическая модель машины Тьюринга

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

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

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

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

      Лента предполагается потенциально бесконечной, разбитой на ячейки (равные клетки). При необходимости к первой или последней клетке, в которой находятся символы пристраивается пустая клетка. Машина работает во времени, которое считается дискретным, и его моменты занумерованы 1, 2, 3, … В каждый момент лента содержит конечное число клеток. В клетки в дискретный момент времени может быть записан только один символ (буква) из внешнего алфавита                    A = {Λ,a1,a2,…,an-1}, n ≥ 2 . Пустая ячейка обозначается символом Λ, а сам символ Λ называется пустым, при этом остальные символы называются непустыми. В этом алфавите A в виде слова (конечного упорядоченного набора символов) кодируется та информация, которая подается в МТ. Машина «перерабатывает» информацию, поданную в виде слова, в новое слово.

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

      Внутренняя память машины представляет собой некоторое конечное множество внутренних состояний                      Q = { q0, q1, q2, ..., qm}, m ≥ 1. Будем считать, что мощность     |Q |≥ 2. Два состояния машины имеют особое значение: q1 – начальное внутреннее состояние (начальных внутренних     состояний может быть несколько), q0 – заключительное состояние или стоп-состояние (заключительное состояние всегда одно). В каждый момент времени МТ характеризуется положением головки и внутренним состоянием. Например, под ячейкой, над которой находится головка, указывается внутреннее состояние машины.

                  

                            a2          a1         Λ       a2        a3

                            q1

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

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

qiai → aj D qj,

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

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

qiai → aj D qj и qtat → ak D qk, то q ≠ qt или ai ≠ at и D € {П, Л, Н}.

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

      Максимальное число команд в программе равно              (n +1) × m, где n +1= |A| и m +1= |Q| .

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

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

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

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

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