1.3. Алгоритмы

Основные понятия.

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

Если задан алгоритм, то считаются определёнными следующие объекты:

• K - счётное множество конфигураций некоторой машины;
• I - множество начальных конфигураций, I Í K;
• T - отношение перехода на K, т.е. T Í KґK; это отношение часто обозначают ®_T или просто ®.

Если k ® k', то k' называется преемником k. Множество преемников любой конфигурации должно быть конечным. Если конфигурация не имеет преемников, она называется заключительной. Если у любой конфигурации не более одного преемника, алгоритм называется детерминированным. В таком случае отношение T можно считать функцией на K, которую называют функцией перехода. Недетерминированные алгоритмы называют ещё исчислениями.

Последовательность конфигураций k₀, k₁, ..., k_n, n ³ 0, вычислением длины n, или за n шагов (по заданному алгоритму), если k₀О I и k_i ® k_i+1 для всех 0 Ј i < n. Если k_n - заключительная конфигурация, то вычисление называется завершённым, а k_n - результатом вычисления с входом k₀.

Частичная функция f : A ® B называется вычислимой, если существует такой детерминированный алгоритм, что A = I, B Í K и f(a) = b тогда и только тогда, когда b является результатом вычисления по этому алгоритму с входом a (этот алгоритм должен зацикливаться на таком входе a, на котором не определено значение f(a)).

Кроме задачи вычисления функции рассматривается задача распознавания элементов множества. В этом случае распознаваемое множество считается подмножеством некоторого базового множества B (множества чисел, матриц, строк и т.п.). Множество A Í B называется разрешимым, или рекурсивным, если вычислима его характеристическая функция c_A: B ® {0,1}

 Множество A Í B называется полуразрешимым, если вычислима его "полухарактеристическая" функция h_A: B ® {1}

Известно, что всякое разрешимое множество полуразрешимо, но не наоборот. Существуют и неполуразрешимые счётные множества. 

Множество A Í B называется рекурсивно перечислимым, если оно является множеством значений некоторой вычислимой функции f, определённой на всём множестве натуральных чисел N, т.е. f(N) = A. Перебирая натуральные числа, с помощью этой функции можно получить любой элемент множества A (и ничего другого). Известно, что всякое рекурсивно перечислимое множество полуразрешимо и наоборот.

В данном определении разрешимости и перечислимости множеств использовались только детерминированные алгоритмы. Не увеличивает ли недетерминированность способность алгоритмов к распознаванию? 

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

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

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

Хотя общее формальное определение алгоритма дать невозможно, можно формально определить тот или иной класс алгоритмов. Например, определяя язык программирования, мы определяем класс алгоритмов, которые можно представить в виде программ на этом языке. Разрешимый класс алгоритмов, которые могут вычислить любую вычислимую функцию, называется рекурсивно полным. Ещё в 1930-х годах американский логик А. Чёрч высказал утверждение, что существует рекурсивно полный класс алгоритмов, и попытался сформулировать такой класс (l-исчисление Чёрча). Это утверждение называется тезисом Чёрча. Хотя его нельзя доказать формально, не имея общего определения понятия алгоритма, но он подтверждается тем, что формально определено огромное количество классов алгоритмов, в каждом из которых можно вычислить любую функцию, вычислимую в любом другом классе. Принимая тезис Чёрча, такие классы также называют рекурсивно полными.

Машины Тьюринга.

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

• ленты - конечной последовательности ячеек, в каждой из которых записано по одному символу некоторого конечного алфавита S, 
• головки - устройства, которое в каждый момент обозревает некоторую ячейку, может находиться в одном из конечного множества состояний Q, читать и писать символ в обозреваемой ячейке, перемещаться вдоль ленты и добавлять при необходимости к её концам новые ячейки,
• программы - конечного множества правил P, управляющих поведением головки.

Машина Тьюринга

Правило имеет вид (q,a) ® (q',a',S), где q и q' - состояния, a и a' - символы алфавита, S - сдвиг головки, принимающий значение L (сдвиг влево на одну ячейку), R (сдвиг вправо на одну ячейку) или N (отсутствие сдвига). Правило может применяться, когда головка находится в состоянии q и обозревает ячейку с символом a. Если оно применяется, то головка переходит в состояние q', в обозреваемую ячейку записывается символ a', а затем выполняется сдвиг S. Если сдвиг невозможен из-за выхода за границу ленты, то к ней с соответствующей стороны добавляется ячейка с записанным в неё специальным символом LОS . Множество состояний обязательно содержит одно начальное состояние q₀ и одно заключительное состояние q_f. При этом предполагается, что для каждой пары (q,a), где q № q_f, в P есть хоть одно правило, а для q_f нет ни одного правила. Таким образом, машина Тьюринга останавливается тогда и только тогда, когда она попадает в заключительное состояние.

Конфигурацией машины Тьюринга называется цепочка вида aqab, где aab - содержимое ленты, q - текущее состояние головки, а её позиция указывает обозреваемую ячейку между a и b (см. рисунок). Предполагается, что начальная конфигурация всегда имеет вид q₀ab, т.е. головка в этих конфигурациях всегда сдвинута к левому концу ленты.

Формально, машина Тьюринга определяется набором M = (S,Q,P,q₀,q_f), где
S = {L,a₁,...,a_n} - конечный ленточный алфавит, n ³ 1,
Q = {q₀,...,q_f} - конечное множество состояний,
P Í QґSґQґSґS, где S = {L,R,N}, - множество правил, записываемых в виде (q,a) ® (q',a',S), где (q,a) принимает все значения из (Q \ {q_f})ґS  и только такие значения,
q₀, q_f - начальное и заключительное состояния, соответственно,
K = {aqb | qОQ, aОS ^*, bОS ⁺} - множество конфигураций (обозначения S ^* и S ⁺ см. в п. 2.1),
I = {q₀a | aОS ⁺} - множество начальных конфигураций.
Отношение перехода T Í KґK формально определяется следующим образом:
если q,q'ОQ, a,a',bОS, a,bОS ^*, то
правилу (q,a) ® (q',a',N) соответствует переход aqab ®_T aq'a'b ,
правилу (q,a) ® (q',a',L) соответствуют переходы abqab ®_T aq'ba'b  (для всех b) и qab ®_T q'La'b,
правилу (q,a) ® (q',a',R) соответствуют переходы aqabb ®_T aa'q'bb  (для всех b) и aqa ®_T aa'q'L.

На самом деле, рекурсивно полным будет класс всех машин Тьюринга с произвольным фиксированным алфавитом S, например, с S = {L,1}. Разные алфавиты мы используем только для удобства программирования.

Назовём L-выходом (выходом с пустым входом) машины Тьюринга любую цепочку a = bg, не начинающуюся и не кончающуюся символом L, если есть вычисление q₀L ®_T^* L^mb q_f g Lⁿ (m, n ³ 0). С помощью тезиса Чёрча-Тьюринга можно доказать следующее утверждение (доказательство опускаем).

У т в е р ж д е н и е  1.9. Пусть задан произвольный конечный алфавит A. Произвольное множество цепочек B в алфавите A рекурсивно перечислимо тогда и только тогда, когда оно совпадает с множеством L-выходов некоторой машины Тьюринга.

Очевидно, что при |B|>1 машина должна быть недетерминированной.

Пример 1.4. Пусть A = {a, b}. Множество A^* всех цепочек в алфавите A рекурсивно перечислимо, т. к. совпадает с множеством L-выходов машины Тьюринга с правилами

(q₀,L) ® (q₀,a,R),
(q₀,L) ® (q₀,b,R),
(q₀,L) ® (q_f ,L,N).

Вычисление для такой машины имеет вид q₀L ® aq₀L ® abq₀L ® abbq₀L ® abbq_f L.
Ђ

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