Машина Тьюринга и невычислимые функции

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

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

Московский государственный открытый университет

Кафедра промышленного строительства

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

По курсу: «Математическая логика»

по теме:

Машина Тьюринга и невычислимые функции

Выполнила: Акулаева Мария

студентка группы ИВТ-21

Руководитель: Балабан Е.И.

г. Коломна, 2014 г.

СОДЕРЖАНИЕ

ВВЕДЕНИЕ

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

2. Основные свойства машины Тьюринга

3. Продуктивность

4. Тезис Черча

5. Вычислимая функция

6. Машина Тьюринга и алгоритмически неразрешимые функции. Проблема остановки машины Тьюринга

ЗАКЛЮЧЕНИЕ

СПИСОК ИСПОЛЬЗУЕМЫХ МАТЕРИАЛОВ

ВВЕДЕНИЕ

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

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

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

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

Машина Тьюринга - это совокупность следующих объектов

1) внешний алфавит A={a₀, a₁, …, a_n};

2) внутренний алфавит Q={q₁, q₂,…, q_m} - множество состояний;

3) множество управляющих символов {П, Л, С}

4) бесконечная в обе стороны лента, разделённая на ячейки, в каждую из которых в любой дискретный момент времени может быть записан только один символ из алфавита А;

5) управляющее устройство, способное находиться в одном из множества состояний

Символом пустой ячейки является буква внешнего алфавита а₀.

Среди состояний выделяются начальное q₁, находясь в котором машина начинает работать, и заключительное (или состояние остановки) q₀, попав в которое машина останавливается.

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

q_i a_j > a_p X q_k

Запись означает следующее: если управляющее устройство находится в состоянии q_i, а в обозреваемой ячейке записана буква a_j, то (1) в ячейку вместо a_j записывается a_p, (2) машина переходит к обозрению следующей правой ячейки от той, которая обозревалась только что, если Х= П, или к обозрению следующей левой ячейки, если Х= Л, или же продолжает обозревать ту же ячейку ленты, если Х= С, (3) управляющее устройство переходит в состояние q_k.

Поскольку работа машины, по условию, полностью определяется ее состоянием q, в данный момент и содержимым а обозреваемой в этот момент ячейки, то для каждой возможной конфигурации q_i a_j имеется ровно одно правило. Правил нет только для заключительного состояния, попав в которое машина останавливается. Поэтому программа машины Тьюринга с внешним алфавитом A={a0, a1, …, an} и внутренним Q={q1, q2,…, qm} содержит не более m (n+ 1) команд.

Словом в алфавите А или в алфавите Q, или в алфавите A Q называется любая последовательность букв соответствующего алфавита. Под k-ой конфигурацией будем понимать изображение ленты машины с информацией, сложившейся на ней к началу k-того шага (или слово в алфавите А, записанное на ленту к началу k-того шага), с указанием того, какая ячейка обозревается в этот шаг и в каком состоянии находится машина. Имеют смысл лишь конечные конфигурации, т.е. такие, в которых все ячейки ленты, за исключением, быть может, конечного числа, пусты. Конфигурация называется заключительной, если состояние, в котором при этом находится машина, заключительное.

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

Будем говорить, что непустое слово б в алфавите А\ {а₀} = {a₁, …, a_n} воспринимается машиной в стандартном положении, если оно записано в последовательных ячейках ленты, все другие ячейки пусты, и машина обозревает крайнюю слева или крайнюю справа ячейку из тех, в которых записано слово б. Стандартное положение называется начальным (заключительным), если машина, воспринимающая слово в стандартном положении, находится в начальном состоянии q₁ (соответственно в состоянии остановки q₀).

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

Рассмотрим пример:

Дана машина Тьюринга с внешним алфавитом А = {0, 1} (здесь 0 - символ пустой ячейки), алфавитом внутренних состояний Q = {q₀, q₁, q₂} и со следующей функциональной схемой (программой):

q₁ 0 > 1 Л q₂;

q₁ 1 > 0 С q₂;

q₂ 0 > 0 П q₀;

q₂ 1 > 1 С q₁;

Данную программу можно записать с помощью таблицы

Посмотрим, в какое слово переработает эта машина слово 110, исходя из начального положения:

q₁

На первом шаге действует команда: q₁ 0 > 1 Л q₂ (управляющее устройство находится в состоянии q1, а в обозреваемой ячейке записана буква 0, в ячейку вместо 0 записывается 1, головка сдвигается влево, управляющее устройство переходит в состояние q2), в результате на машине создается следующая конфигурация:

q₂

На втором шаге действует команда: q₂ 1 > 1С q₁ и на машине создается конфигурация:

q₁

Третий шаг обусловлен командой: q₁ 1 > 0 С q₂. В результате нее создается конфигурация:

q₂

Наконец, после выполнения команды q₂ 0 > 0 П q₀ создается конфигурация

q₀

Эта конфигурация является заключительной, потому что машина оказалась в состоянии остановки q₀.

Таким образом, исходное слово 110 переработано машиной в слово 101.

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

11q₁0 => 1 q₂11 => 1q₁11 => 1q₂01 => 10q₀1

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

2. Основные свойства машины Тьюринга

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

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

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

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

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

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

3. Продуктивность

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

тьюринг алгоритм функция черч

4. Тезис Черча

Тезис Черча - фундаментальное утверждение для многих областей науки, таких, как теория вычислимости, информатика, теоретическая кибернетика и др. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

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

Физический тезис Чёрча -- Тьюринга гласит: Любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга.

Тезис Чёрча -- Тьюринга невозможно строго доказать или опровергнуть, поскольку он устанавливает «равенство» между строго формализованным понятием частично вычислимой функции и неформальным понятием «интуитивно вычислимой функции».

5. Вычислимые функции

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

«Вычислимые по Тьюрингу» функции - это функции, вычисляющимся на машинах Тьюринга.

6. Машина Тьюринга и алгоритмически неразрешимые функции

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

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

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

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

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

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

Теорема.

Не существует машины Тьюринга М, решающей проблему самоприменимости, то есть проблема самоприменимости алгоритмически неразрешима.

Доказательство.

Предположим противное, то есть. пусть существует машина Тьюринга Т, решающая проблему самоприменимости в указанном выше смысле. Построим новую машину Т₀, добавив новое состояние q₀* и объявив его заключительным, а также добавив новые команды для состояния q₀, которое было заключительным в Т:

q₀ a₁> a₁ С q₀ (1)

q₀ a₂> a₂ С q₀ (2)

…q₀ a_n> a_n С q₀* (n)

Рассмотрим теперь работу машины T₀.

Пусть M - произвольная машина. Если M - самоприменима, то начальная конфигурация q₁a_i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q₀a₁, далее применяется команда (1), и машина T₀ никогда не остановится. Если M - несамоприменима, то начальная конфигурация q₁a_i перейдет с помощью команд машины T через конечное число шагов в конфигурацию q₀a_n, далее применяется команда (n), и машина T₀ остановится.

Таким образом, машина T₀ применима к кодам несамоприменимых машин Т и неприменима к кодам самоприменимых машин Т.

Теперь применим машину T₀ к начальной конфигурации q₁a_i. Сама машина T₀ является либо самоприменимой, либо несамоприменимой. Если T₀ самоприменима, то по доказанному она никогда не остановится, начав с q₁a_i, и потому она несамоприменима. Если T₀ несамоприменима, то по доказанному, она останавливается через конечное число шагов, начав с q₁a_j, и потому она самоприменима. Получили противоречие, следовательно проблема самоприменимости алгоритмически неразрешима, что и требовалось доказать.

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

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

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

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

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

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

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

в) Логическая неразрешимость (в смысле теоремы Гёделя о неполноте)

ЗАКЛЮЧЕНИЕ

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

Его Машина до сих пор используется во множестве теоретических и практических исследований. А в честь него установлена премия Тьюринга, одна из самых престижных премий в информатике, ежегодно вручаемая Ассоциацией вычислительной техники за выдающийся научно-технический вклад в этой области. Премия спонсируется корпорациями Intel и Google и в настоящий момент сопровождается наградой в 250 000 долларов США. Впервые Премия Тьюринга была присуждена в 1966 году Алану Перлису за развитие технологии создания компиляторов.

СПИСОК ИСПОЛЬЗУЕМЫХ МАТЕРИАЛОВ

1. Дж. Булос, Джеффри Р. Вычислимость и логика, 1994 с. 18-25

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

3. Н.К. Верещагин, А. Шень. Лекции по математической логике и теории алгоритмов. Часть 3.Вычислимые функции, М.: МЦНМО, 1999, 176 с.

1. http://ru.wikipedia.org/

2. http://bookzie.com/

3. http://dic.academic.ru/dic.nsf/enc_mathematics

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