РЕШЕНИЕ ЗАДАЧ С ПОМОЩЬЮ МАШИНЫ ТРЬЮРИНГА

 

 

§1. История создания машины Тьюринга

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

Заслуги Алана Тьюринга по расшифровке немецких военных кодов, которые спасли жизни сотен тысяч людей, во время Второй мировой войны были проигнорированы. Однако официальные публичные извинения были принесены только спустя 55 лет после его смерти. Математика с его смертью лишилась одного из самых ярких и оригинальных мыслителей. Алан М. Тьюринг не только решил одну из труднейших математических проблем, а фактически он предложил намного большее – новый метод решения математических задач (машину Тьюринга), который в конечном счете привел к возникновению computer science и современных компьютеров.

Алан Тьюринг стоял у самых истоков искусственного интеллекта и программирования. У данного ученого него не было учеников в общепринятом смысле, но определенно можно утверждать, что любой программист или же человек, непосредственно связанный с информатикой,  даже не осознавая того, является если и не учеником, но уж точно его последователем. Именем Алана Тьюринга названа своего рода  Нобелевская премия в области computer science , которая называется премией Тьюринга. Данной награды удостаиваются те, кто внес выдающийся вклад в эту область исследований.

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

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

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

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

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

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

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

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

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

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

        

§2. Структура и такт работы машины Тьюринга

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

Рисунок 1.

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

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

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

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

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

Автомат может выполнять три элементарных действия:

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

2.     сдвигаться на одну клетку вправо или влево (то есть «перепрыгивать» сразу через несколько клеток автомат не может);

3.     переходить в новое состояние.

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

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

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

2.     сдвигается на одну клетку влево (обозначение –, от left), либо на одну клетку вправо (обозначение – , от right), либо остается неподвижным (обозначение – ).

3.     переходит в некоторое состояние  (в частности, может остаться в прежнем состоянии).

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

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

На примере машины Тьюринга хорошо прослеживаются свойства алгоритмов.

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

1.     Дискретность.

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

2.     Понятность.

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

3.      Детерминированность.

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

4.     Результативность.

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

5.     Массовость.

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

 

 

§3. Программа для машины Тьюринга и правила ее выполнения

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

Таблица 1. Программа для МТ.

			…		…
…
				, ,
…

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

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

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

Правила выполнения программы:

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

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

Во-вторых, автомат установлен в состояние , которое указано в таблице первым, и размещен под его первым (самым левым) символом входного слова:

Рисунок 2.

Если входное слово пустое, то автомат может смотреть в любую клетку, так как они все пусты.

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

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

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

Вообще говоря, возможны два исхода работы машины Тьюринга над входным словом:

1.     Первый исход (считается «хорошим»):  

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

Будем считать, что в момент остановки должны выполняться следующие условия:

a)     внутри выходного слова не должно быть пустых клеток . Так же необходимо отметить, что во время выполнения программы внутри обрабатываемого слова пустые клетки могут быть, но в конце их уже не должно остаться;

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

2.     Второй исход (считается «плохим»):

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

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

§4. Примеры на составление программ для машины Тьюринга

Для сокращения формулировки задач введем следующие обозначения:

1.     Буквой  будем обозначать входное слово;

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

Пример 1:

Перемещение автомата. Замена символов.

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

Решение:

Для решения данной задачи необходимо выполнить ряд действий:

1.     Перегнать автомат под последнюю цифру числа;

2.     Если это цифра от 0 до 8, то заменить ее цифрой на 1 больше и остановиться;

Рисунок 3.

3.     Если же это цифра 9, то заменить ее на 0 и сдвинуть автомат к предыдущей цифре, после чего таким же способом увеличить на 1 эту предпоследнюю цифру;

Рисунок 4.

4.     Особый случай составляет тот, когда в  имеются только девятки (например, 99). В данном случае автомат будет сдвигаться влево, заменяя девятки на нули, и в конце концов окажется под пустой клеткой. Тогда именно в эту пустую клетку необходимо записать 1 и остановиться (ответом будет 100):

Рисунок 5.

В виде программы для МТ эти действия описываются следующим образом:

Рисунок 6.

Пояснения: ˗ это состояние, в котором автомат переходит под последнюю цифру числа. Для этого он постоянно движется вправо, не меняя видимые цифры и оставаясь в том же состоянии. Однако, определить последнюю цифру автомат может, только попав на соседнюю пустую клетку. Поэтому, дойдя до пустой клетки, он возвращается под последнюю цифру и переходит в состояние . ˗ это состояние, в котором автомат прибавляет 1 к той цифре, которую в данный момент видит. Сначала это последняя цифра, если она находится в диапазоне от 0 до 8, то он прибавляет к ней 1 и останавливается, если нет, то возвращается и проверяет предпоследнюю цифру и т.д.

Пример 2:

Пусть . Необходимо перенести первый символ непустого слова  в его конец.

Например,

Рисунок 7.

Решение:

Для решения данной задачи необходимо выполнить ряд следующих действий:

1. На первом шаге необходимо запомнить первый символ слова , а затем стереть данный символ.

2. На втором шаге необходимо перегнать автомат вправо под первую пустую клетку за  и записать в неё символ, который был запомнен на первом шаге.

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

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

Таблица 2. Программа для задачи 2.

					комментарий
					Анализ 1-го символа, удаление его, разветвление
					Запись  справа
					Запись  справа
					Запись справа

Так же можно рассмотреть поведение данной программы на входных словах, которые содержат не более одного символа.

Если входное слово пусто (такое слово называется «плохим» для задачи), то в данном случае программа зациклится, то есть автомат, находясь в состоянии  и все время попадая на пустые клетки, будет двигаться бесконечно вправо.

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

Рисунок 8.

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

Пример 3:

Пусть . Необходимо удалить из слова  его второй символ, если такой есть.

Решение:

С первого взгляда на данную задачу, кажется, что решить ее довольно просто: для этого нужно сдвинуть автомат под клетку со вторым символом и затем, после проделанного, очистить данную клетку:

Рисунок 9.

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

Рисунок 10.

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

Таблица 3. Программа для задачи 3.

				комментарий
				Анализ и удаление первого символа
				Замена второго символа на
				Замена второго символа на .

Пример 4.

Пусть . Если  является непустым словом, то необходимо за его первым символом вставить символ .

Решение:

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

Рисунок 11.

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

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

Таблица 4. Программа для примера 4.

					комментарий
					Анализ первого символа для переноса его влево
					Приписать слева
					Приписать слева
					Приписать слева
					Заменить бывший первый символ  на

Пример 5:

Пусть алфавит состоит из следующего набора символов: . Необходимо удалить из слова  все вхождения символа , если такие имеются.

Решение:

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

Конкретно необходимо выполнить следующий ряд  действий:

1.     Выходное слово строится справа от входного. Чтобы разграничить эти слова, необходимо отделить их некоторым вспомогательным символом, например знаком  =, который отличен от всех символов алфавита . На ленте могут быть записаны не только символы из алфавита входного слова.

2.     После этого необходимо вернуться к началу входного слова:

Рисунок 12.

3.     На данном этапе нужно перенести в цикле все символы входного слова, кроме символа , вправо за знак равенства в формируемое выходное слово.

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

Рисунок 13.

Далее необходимо вернуться налево к тому символу, который стал первым во входном слове, и повторить те же самые действия, но уже по отношению к этому символу.

Рисунок 14.

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

Рисунок 15.

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

Таблица 5. Программа для примера 5.

				=		комментарий
						Записать справа знак =
						Влево к первому символу слова
						Анализ и удаление его, разветвление
						Запись  справа, возврат налево
						Запись  справа, возврат налево

 

 

§5. Примеры решения задач

Пример 1:

Заменить в двоичной записи числа все нули на единицы и все единицы на нули. Указатель стоит слева от числа.

Решение:

Рисунок 16.

Пример 2:

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

Решение:

Рисунок 17.

Пример 3:

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

Решение:

Рисунок 18.

Пример 4:

Пусть . Если первый и последний символы слова  совпадают, то данное слово не менять, а иначе заменить то слово пустым символом.

Решение:

Рисунок 19.

Пример 5:

Пусть . Необходимо удалить из слова  его второй символ, если такой есть.

Решение:

Рисунок 20.

 

Пример 6:

Пусть . Если ˗ непустое слово, то необходимо за его первым символом вставить символ .

Решение:

Рисунок 21.

Пример 7:

Пусть . Необходимо вставить в слово  символ  за первым символом , если такой есть.

Решение:

Рисунок 22.

Пример 8:

Пусть . Необходимо перенести первый символ непустого слова  в его конец.

Решение:

Рисунок 23.

Заключение

Машина Тьюринга ˗ это строгое математическое построение, математический аппарат, созданный для решения определенных задач.

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

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

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

Таким образом, в ходе работы были выполнены все поставленные задачи:

- найти материал по данной теме в учебных и научных источниках;

- проанализировать изученную литературу;

- изучить историю создания машины Тьюринга;

- рассмотреть структуру и такт работы машины Тьюринга;

- проанализировать программу для МТ и правила ее выполнения;

- рассмотреть различные примеры решения задач с помощью МТ;

- изложить материал в форме курсовой   работы.

А так же была достигнута цель курсовой работы.

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

1.     Бильгаева Н.Ц. Теория алгоритмов, формальных языков, грамматик и автоматов. Улан-Удэ.: ВСГТУ, 2000. 51 с.

2.     Брауэр В. Введение в теорию конечных автоматов. М.: Радио и связь, 1987. 357 с.

3.     Варпаховский Ф.Л.

4.     Гэри М. Вычислительные машины и труднорешаемые задачи. М.: ЦНИИ Электроника, 2016. 519 с.

5.     Игошин В.И. Математическая логика и теория алгоритмов. М.: Академия, 2008. 448 с.

6.     Ильиных А.П. Теория алгоритмов: учебное пособие. Екатеринбург.: Уральский государственный университет, 2006. 149 с.

7.     Карпов Ю.Г. Теория автоматов. СПб.: Питер, 2003. 208 с.

8.     Крупский В.Н. Теория алгоритмов. М.: Академия, 2009. 320 с.

9.     Крючкова Е.Н. Теория алгоритмов. М.: Статистика, 2000. 270 с.

10.  Петцольд Чарльз. Классика программирования. Путешествие по исторической статье Тьюринга о вычислимости и машинах Тьюринга. М.: Академия, 2014. 440 с.

11.  Рассел Джесси. Машина Тьюринга. М.: VSD, 2012. 137 с.

12.  Рощин А.Г., Половов Р.М. Теория автоматов. Тексты лекций. М.: МГТУ ГА, 2001. 76 с.

13.  Савельев А.Я. Основы информатики: Учебник для вузов. М.: Издательство МГТУ им. Баумана, 2001. 328 с

14.  Фалина И.Н. Машина Тьюринга. М.: Академия, 2005. 53 с.

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

16.  Шеннон, К.Э. Машина Тьюринга (часть 2). М.: Научное книгоиздательство, 2015. 520 с.

 

 

 

Скачано с www.znanio.ru