Автор работы: Пользователь скрыл имя, 21 Сентября 2015 в 11:45, курсовая работа
Тьюринг высказал гипотезу (известную также как тезис Тьюринга) о том, что для всякой вычислимой функции может быть построена машина Тьюринга. Этот тезис также не может быть доказан, так как включает нестрогое понятие вычислимой функции.
Для всякой рекурсивной функции может быть построена машина Тьюринга и, обратно, всякая машина Тьюринга вычисляет рекурсивную функцию.
Целю данной курсовой работы, является рассмотрение достаточных условий разрешимости, проблемы остановки машин Тьюринга. Проанализировать алгоритмическую неразрешимость ряда задач.
Введение …………………………………………………….………….…… 3
Определение машины Тьюринга ……………………………….. …..…. 5
Работа машины Тьюринга …………………………………………..... 8
Способы задания машин Тьюринга, операции над ними ……….. …… 9
3.1. Формулировка проблемы остановки машины Тьюринга……..…. 11
. Проблема вычислимости машины Тьюринга ……….……..…….. 15
Множество граничных конфигураций. Достаточные условия
разрешимости проблемы остановки…………………………..……...... 16
Машины Тьюринга с двумя символами и
не более чем тремя состояниями …………………....……………..….. 19
Заключение …………………………………..…………………..………. .. 23
Список литературы ………………………………………………………... 24
За. Множество – слов 1– 1– 0 – регулярно.
36. Множество – выметаний – регулярно.
Будем рассматривать только машины с входным алфавитом из двух символов –0 и 1, причем в качестве пустого символа используется 0. Машинами (2, s) назовем машины с числом внутренних состояний головки, равным s.
Теорема. Для любой из машин (2, 2) или (2, 3) проблема остановки разрешима.[7]
Лемма 1. Любая из машин (2, 5), программа которой содержит только одну левую команду, является О -машиной, для которой выполнены условия следствия 2.[7]
Доказательство. Если в программе машины имеется только одна левая команда , то след любого L – выметания есть при некотором п, а выполнение его заканчивается в состоянии .Отсюда следует, что почти все продолжения L – выметаний на символе х одного типа, а множество выметаний 1–1– – регулярно. Поэтому любая из рассматриваемых машин является О-машиной. Если , то одностороннее продолжение любого L –выметания отлично от правого. Когда , одностороннее продолжение любого –выметания отлично от левого. Следовательно, для такой машины выполнены условия следствия 2. Лемма 1 доказана.
Таким образом, проблема остановки разрешима для любой из машин (2, 5), программа которой содержит только одну левую или только одну правую команду.
Это означает, в частности, что для машин (2, 2) п.о. разрешима
Рассмотрим теперь машины с программами, содержащими две левые команды. Если для таких машин проблема остановки разрешима, то она будет разрешима и в случае, когда число правых команд в программе равно двум. Отсюда будет вытекать разрешимость проблемы остановки для машин (2, 3). Занумеруем команды любой из рассматриваемых программ так, чтобы левыми командами были . Для удобства просмотра машин (2, 3) введем понятие графа машины, строящегося по ее программе. Каждой команде поставим в соответствие вершину графа. В каждый граф введем вершину «стоп». Вершины графа будем изображать точками, около которых напишем названия соответствующих вершин. От каждой вершиныпроведем стрелку к каждой вершине такой, что Если после этого окажется, что из вершины выходит менее двух стрелок, то из проводим стрелку также к вершине «стоп». Граф любой из машин (2, 3) при подходящей нумерации команд содержит какой-либо подграф, изображенный на рис. 5 или полученный из него заменой одной или нескольких правых вершин вершиной «стоп». Для машин, графы которых содержат подграф вида VII, п. о. разрешима ввиду конечности числа –выметаний. Далее мы рассмотрим последовательно машины типа I-VI и докажем разрешимость п. о. в каждом из этих случаев. Под машиной типа I, или I-машиной, будем понимать машину, граф которой содержит подграф вида I или полученный из I заменой некоторых правых вершин вершиной «стоп». Так же определим I I , . . ., VI машины.
Лемма 2. I-машина есть О-машина, удовлетворяющая условиям или теоремы 7, или следствия 2.[7]
Доказательство. Из структуры подграфа I (рис. 5) видно, что выполнение любого L – выметания дальности, не меньшей 2, заканчивается головкой всегда в состоянии , а след такого выметания есть слово при некотором п. Отсюда, во-первых, следует что если продолжение –выметания С, , на символе х левое, то и для любого –выметания продолжение на х также левое. Во-вторых, множество всех правых продолжений – выметаний на одном и том же символе есть некоторое 1–1– – регулярное множество. Из первого получаем, что множество – выметаний бесконечно только в случае, когда почти все продолжения L – выметаний на одном из символов левые, а на другом –правые. Поэтому множество – выметаний 1–1– – регулярно. Таким образом, любая I-машина есть О-машина. Пусть почти все продолжения L –выметаний на –левые (тогда в графе существует переход ), а на –правые. Если , то выполнены условия следствия 2. Если для некоторого – выметания С С содержит , то множество –выметаний, а значит, и –слов 0 –1 – –регулярно. Пусть ни при каком –выметании & Сх4 не содержит . Тогда Сх4 может содержать, только если в графе существуют где C – L –выметание, , т. e. множество – слов 0 – 1– 0 – регулярно. Для машин с 0 – 1– р –регулярным множеством – слов выполнены условия теоремы 7. При продолжения почти всех – выметаний бесконечны, а при продолжения почти всех – выметаний бесконечны, т.е. выполняются условия следствия 2. Лемма 2 доказана.
Заключение
В настоящей работе получены достаточные условия разрешимости проблемы остановки (п.о.) машин Тьюринга. Эти условия сформулированы в терминах свойств машинных программ. С их помощью доказывается разрешимость п.о. для машин Тьюринга с двумя символами и не более чем тремя состояниями.
Мы показали, что для установления разрешимости п. о. на всем множестве начальных конфигураций достаточно исследовать лишь подмножество «граничных» конфигураций. С использованием этого факта были доказаны достаточные условия разрешимости п. о.
Возникает естественный вопрос: каким образом следует определять, остановится какая-то определенная машина Тьюринга ( в которую введены конкретные начальные данные) или нет. Для многих машин Тьюринга ответить на этот вопрос нетрудно, но, как мы видели выше, иногда для ответа может потребоваться решение какой-нибудь до сих пор не решенной математической задачи.
Список литературы
– с.12-15.
– с. 732-741.