Лекции по теории алгоритмов. Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов

• Название: Лекция Интуитивное представление об алгоритме Интуитивное определение алгоритма. Примеры алгоритмов
• Анкор: Лекции по теории алгоритмов
• Дата: 05.05.2022
• Размер: 2.84 Mb.
• Имя файла: Лекции по теории алгоритмов.doc
• Тип: Лекция; #513398
• страница: 3 из 7



Определим, в какое слово переработает это слово машина.

Так машина находится в состоянии q_1, обозревая ячейку в которой находится 1, то первой должна быть выполнена команда, стоящая на пересечении столбца q₁ и строки 1 функциональной схемы. Это команда q₂a₀Л. После ее выполнения машина перейдет в следующее состояние:

1

1

*

a0

q2



После выполнения следующей команды q₂*Л (записанной на пересечении столбца q₂ и строки 1) машина перейдет в следующее состояние:

1

1

*

a0

q2



На пересечении столбца q₂ и строки 1 в функциональной схеме машины Тьюринга записана команда q₂1Л, выполнение которой приведет к состоянию:

1

1

*

a0

q2



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

q₂1→q₂1Л

1

1

*

a0

q2



q₂a₀→q₃1П

1

1

1

*

a0

q3



q₃1→q₃1П

1

1

1

*

a0

q3



q₃1→q₃1П

1

1

1

*

a0

q3



q₃*→q₃*П

1

1

1

*

a0

q3



q₃a₀→q₁a₀Л

1

1

1

*

a0

q1



_q1*→q0a0

1

1

1

q1



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

Определение 3.1.1. Пусть на некотором множестве слов алфавита {a₁, a₂, … a_l} заданафункцияkпеременных, значениями которой являются слова в том же алфавите. Предположим, что имеется машина Тьюринга с алфавитом A={a₀, a₁, a₂, … a_l} (nl), которая любой набор из k слов, входящий в область определения функции, записанный последовательно с промежутком в одну ячейку между словами, перерабатывает в слово, являющееся значением функции на этом наборе. А на любом наборе из kслов, не входящих в область определения функции, машина работает бесконечно. Тогда про такую машину Тьюринга говорят, что она вычисляет данную функцию, а сама функция называется вычислимой по Тьюрингу.
2. Не распознаваемость самоприменимости машины Тьюринга
Приведем доказательство о не распознаваемости самоприменимости машины Тьюринга.

Для этого нам понадобятся следующие теоремы и определения.

Теорема 3.2.1. (о композиции машин Тьюринга). Каковы бы ни были машины Тьюринга Т₁ и Т₂ в алфавите А, можно построить работающую в том же алфавите такую машину Т, что для всех слов  над алфавитом А будет выполнено равенство Т()=Т₂(Т₁()).

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

Теорема 3.2.2. (о двоичном моделировании машины Тьюринга) Какова бы ни была машина Т₁ в алфавите А, может быть построена такая машина Т в алфавите В={a₀, 0, 1}, что для любых слов ₁, ₂ над алфавитом А и их кодов ₁, ₂ над алфавитом В Т(₁)= Т(₂) тогда и только тогда, когда Т₁(₁)= ₂.

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

При этом с помощью побуквенного обратимого (конструктивного) двоичного кодирования кодируются в общем случае:

– символы внешнего алфавита и алфавита внутренних состояний,

– символы, используемые при записи команд машины Тьюринга (Л, П, →, «оставаться на месте»),

– символ, фиксирующий начало и конец программы,

– символ, служащий разделителем между командами.

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

Заметим также, что двоичная запись машины Тьюринга однозначно определяет натуральное число. Натуральные числа, являющиеся записями машины Тьюринга называют геделевскими – по имени австрийского математика Курта Геделя, впервые в 30 годы XX века использовавшего номера объектов вместо них самих для формальных рассуждений об этих объектах.

К.Гедель

Рассматривая далее множество машин Тьюринга {T} будем считать, что каждая из них задана своей двоичной записью Т. Широко известная в теории алгоритмов массовая проблема остановки в этих терминах формулируется следующим образом.

Применима ли машина Тьюринга Т, заданная своей записью Т, к двоичному слову p или нет?

Еще одна известная массовая проблема теории алгоритмов – проблема самоприменимости – звучит так.

Применима ли машина Тьюринга Т, заданная своей записью Т, к своей записи Т или нет?

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

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

Теорема 3.2.3. (о нераспознаваемости самоприменимости). Не существует машины Тьюринга S, которая по записи Топределяла бы, самоприменима машина Т или нет.

Доказательство. Предположим противное и допустим, что существует машина Тьюринга S, распознающая самоприменимость. Без ограничения общности можно считать, что S(C)=1, а S(Н)=0, где C – произвольная самоприменимая машина Тьюринга, а Н – произвольная несамоприменимая машина Тьюринга.

Введем в рассмотрение машину Т₁ с алфавитом внутренних состояний Q={q₀, q₁, q₂ }, работающую в алфавите A={a₀, 0, 1} в соответствие со следующей функциональной схемой.

Q A	q1	q2
a0	q11Л	q21Л
0	q00	q21Л
1	q21Л	q21Л

Как видно из приведенной схемы, если первая буква исходного слова  есть 0, то Т₁()=. Если же исходное слово  пусто или начинается с 1, то Т₁ неприменима к слову , Т₁()=1111…

Определим теперь новую машину Тьюринга S₁ как композицию машины S и машины Т₁, полагая S₁()=Т₁(S()).

Предположим далее, что машина S₁ самоприменима. Это означает, что S₁ – запись самоприменимой машины и по определению машины S S(S₁)=1. В то же время,

S₁(S₁)=Т₁(S(S₁))=Т₁(1)=111….,

что означает несамоприменимость машины S₁. Противоречие налицо.

Предположение о том, что машина S₁ несамоприменима, влечет за собой (по определению машины S) соотношение S(S₁)=0. Но по определению машины S₁ S₁(S₁)=Т₁(S(S₁))=Т₁(0)=0, что означает самоприменимость машины S₁.

Вновь получаем противоречие.

Иными словами, предположение о существовании машины S, распознающей самоприменимость приводит к противоречию.

Теорема доказана.

Следствие. Проблема остановки алгоритмически неразрешима.

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