- •Раздел 1. Формальная теория вычислимости
- •1. Интуитивное определение алгоритма. Примеры алгоритмов
- •2. Способы записи алгоритмов
- •1. Машина Поста
- •2. Нормальные алгорифмы Маркова
- •010 1
- •10 → 00
- •1 → 0
- •2. Не распознаваемость самоприменимости машины Тьюринга
- •1. Примитивно-рекурсивные функции
- •2. Частично-рекурсивные и общерекурсивные функции
- •1. Перечислимые и разрешимые множества
- •2. Перечислимость и вычислимость
- •1. Универсальные функции и множества
- •2. Главные универсальные функции и множества
- •1. Нумерации
- •2. Теорема о неподвижной точке
- •Раздел 2. Формальные языки и грамматики
- •1. Понятие формального языка
- •2. Операции над языками
- •4. Иерархия языков по Хомскому
- •1. Конечные автоматы
- •2. Характеризация праволинейных языков
2. Не распознаваемость самоприменимости машины Тьюринга
Приведем доказательство о не распознаваемости самоприменимости машины Тьюринга.
Для этого нам понадобятся следующие теоремы и определения.
Теорема 3.2.1. (о композиции машин Тьюринга). Каковы бы ни были машины Тьюринга Т1 и Т2 в алфавите А, можно построить работающую в том же алфавите такую машину Т, что для всех слов над алфавитом А будет выполнено равенство Т()=Т2(Т1()).
Доказательство этой теоремы осуществляется просто. Внутренние состояния машин Т1 и Т2 (включая начальные состояния) переименовываются, причем в функциональной схеме машины Т1 переход в заключительное состояние заменяется переходом в начальное состояние машины Т2. При этом функциональные схемы объединяются в одну.
Теорема 3.2.2. (о двоичном моделировании машины Тьюринга) Какова бы ни была машина Т1 в алфавите А, может быть построена такая машина Т в алфавите В={a0, 0, 1}, что для любых слов 1, 2 над алфавитом А и их кодов 1, 2 над алфавитом В Т(1)= Т(2) тогда и только тогда, когда Т1(1)= 2.
Из этой теоремы следует, что в теории машин Тьюринга вполне можно рассматривать только те машины, которые работают в двоичном алфавите. Более того, кроме двух способов задания машины Тьюринга (в виде функциональной схемы и списка команд) возможен третий способ ее записи – в виде двоичного слова.
При этом с помощью побуквенного обратимого (конструктивного) двоичного кодирования кодируются в общем случае:
– символы внешнего алфавита и алфавита внутренних состояний,
– символы, используемые при записи команд машины Тьюринга (Л, П, →, «оставаться на месте»),
– символ, фиксирующий начало и конец программы,
– символ, служащий разделителем между командами.
Подчеркнем, что сама двоичная кодировка указанных символов может осуществляться разными способами (один из способов можно найти в []). Важно лишь то, что кодирование обязательно должно быть обратимым. В этом случае двоичная запись машины Тьюринга (Т), которую далее будем обозначать, следуя [] Т ( условная запись двоичного кода символа, фиксирующего начало и конец программы), будет однозначно задавать функциональную схему машины Т.
Заметим также, что двоичная запись машины Тьюринга однозначно определяет натуральное число. Натуральные числа, являющиеся записями машины Тьюринга называют геделевскими – по имени австрийского математика Курта Геделя, впервые в 30 годы XX века использовавшего номера объектов вместо них самих для формальных рассуждений об этих объектах. |
К.Гедель |
Рассматривая далее множество машин Тьюринга {T} будем считать, что каждая из них задана своей двоичной записью Т. Широко известная в теории алгоритмов массовая проблема остановки в этих терминах формулируется следующим образом.
Применима ли машина Тьюринга Т, заданная своей записью Т, к двоичному слову p или нет?
Еще одна известная массовая проблема теории алгоритмов – проблема самоприменимости – звучит так.
Применима ли машина Тьюринга Т, заданная своей записью Т, к своей записи Т или нет?
Очевидно, что проблема самоприменимости является частным случаем проблемы остановки. И если проблема самоприменимости алгоритмически неразрешима, то и проблема остановки относится к числу алгоритмически неразрешимых проблем.
Тот факт, что проблема самоприменимости алгоритмически неразрешима, фиксирует следующая теорема.
Теорема 3.2.3. (о нераспознаваемости самоприменимости). Не существует машины Тьюринга S, которая по записи Т определяла бы, самоприменима машина Т или нет.
Доказательство. Предположим противное и допустим, что существует машина Тьюринга S, распознающая самоприменимость. Без ограничения общности можно считать, что S(C)=1, а S(Н)=0, где C – произвольная самоприменимая машина Тьюринга, а Н – произвольная несамоприменимая машина Тьюринга.
Введем в рассмотрение машину Т1 с алфавитом внутренних состояний Q={q0, q1, q2 }, работающую в алфавите A={a0, 0, 1} в соответствие со следующей функциональной схемой.
Q A |
q1 |
q2 |
a0 |
q11Л |
q21Л |
0 |
q00 |
q21Л |
1 |
q21Л |
q21Л |
Как видно из приведенной схемы, если первая буква исходного слова есть 0, то Т1()=. Если же исходное слово пусто или начинается с 1, то Т1 неприменима к слову , Т1()=1111…
Определим теперь новую машину Тьюринга S1 как композицию машины S и машины Т1, полагая S1()=Т1(S()).
Предположим далее, что машина S1 самоприменима. Это означает, что S1 – запись самоприменимой машины и по определению машины S S(S1)=1. В то же время,
S1(S1)=Т1(S(S1))=Т1(1)=111….,
что означает несамоприменимость машины S1. Противоречие налицо.
Предположение о том, что машина S1 несамоприменима, влечет за собой (по определению машины S) соотношение S(S1)=0. Но по определению машины S1 S1(S1)=Т1(S(S1))=Т1(0)=0, что означает самоприменимость машины S1.
Вновь получаем противоречие.
Иными словами, предположение о существовании машины S, распознающей самоприменимость приводит к противоречию.
Теорема доказана.
Следствие. Проблема остановки алгоритмически неразрешима.
Проблема самоприменимости в теории алгоритмов явилась первой алгоритмически неразрешимой проблемой, от которой отталкивались в дальнейших исследованиях.
Лекция № 4. Рекурсивные функции
1. Примитивно-рекурсивные функции
2. Частично-рекурсивные и общерекурсивные функции