Т. А. Сливина математическая логика и теория алгоритмов

Основная гипотеза теории алгоритмов.
Машина Тьюринга дает один из путей уточнения понятия алгоритма. В связи с этим возникают вопросы: насколько общим является понятие машины Тьюринга? Можно ли считать, что способ задания алгоритмов с помощью машины Тьюринга является универсальным? Может ли всякий алгоритм задаваться таким образом?
На эти вопросы современная теория алгоритмов предлагает ответ в виде следующей гипотезы:
Всякий алгоритм может быть задан посредством тьюринговой функциональной схемы и реализован в соответствующей машине Тьюринга.
Эта гипотеза называется тезисом Тьюринга. Ее нельзя доказать, так как она связывает нестрогое определение понятия алгоритма со строгим определением понятия машины Тьюринга.
Эта гипотеза может быть опровергнута, если удастся привести пример алгоритма, который не может быть реализован с помощью тьюринговой функциональной схемы.
Однако все известные до сих пор алгоритмы могут быть заданы посредством тьюринговых функциональных схем.
Напомним также, что другие способы уточнения понятия алгоритма (понятие нормального алгоритма А. А. Маркова, понятие рекурсивного алгоритма (рекурсивной функции), введенного Чёрчем, Гёделем и Клини) оказались равносильными.
Этот факт является важным доводом в пользу сформулированной гипотезы.
Кроме того, следует сказать, что внутри самой теории алгоритмов эта гипотеза не применяется, то есть при доказательстве теорем теории алгоритмов никаких ссылок на гипотезу не делается.


§ 6. Нормальные алгоритмы Маркова
Как и ранее, будем называть алфавитом А всякое непустое конечное множество символов, а сами символы алфавита будем называть буквами.
Словом в алфавите А называется всякая конечная последовательность букв алфавита А. Пустая последовательность букв называется пустым словом и обозначается через .
Если Р обозначает слово и Q обозначает слово , то PQ обозначает объединение . В частности, Р = Р = Р. Кроме того, (P₁P₂)P₃ = P₁(P₂P₃).
Алфавит А называется расширением алфавита В, если В  А. Очевидно, что в этом случае всякое слово в алфа­вите В является словом в алфавите А.
Алгоритмом в алфавите А называется эффективно вычислимая функция, областью определения которой служит какое-нибудь подмножество множества всех слов в алфавите А и значениями которой являются также слова в алфавите А. Пусть Р есть слово в алфавите А; говорят, что алгоритм U применим к слову Р, если Р содержится в области определения U. Если алфавит В является расширением алфавита А, то всякий алгоритм в алфавите В называется алгоритмом над алфавитом А.
Большинство известных алгоритмов можно разбить на некоторые простейшие шаги. Следуя А. А. Маркову, в качестве элементарной операции, на базе которой строятся алгоритмы, выделим подстановку одного слова вместо другого. Если Р и Q - слова в алфавите А, то выражения Р  Q и Р  Q будем называть формулами подстановки в алфавите А. При этом предполагается, что символы стрелка  и точка  не являются буквами алфавита А, а каждое слово Р и Q может быть и пустым словом. Формула подстановки Р  Q называется простой, а формула подстановки Р  Q называется заключительной.
Пусть Р () Q обозначает одну из формул подстановки Р  Q или Р  Q. Конечный список формул подстановки в алфавите
Р₁ () Q₁
Р₂ () Q₂
…………
Р_r () Q_r
называется схемой алгоритма и порождает следующий алгоритм в алфавите А.
Принято говорить, что слово Т входит в слово Q, если существуют такие (возможно пустые) слова W, V, что Q = WTV.
Пусть Р – слово в алфавите А. Здесь может быть одно из двух:

1. 
   Ни одно из слов P₁,P₂,...,P_r не входит в слово Р (обозначается: U: P ).
   
2. 
   Среди слов Р₁,Р₂,...,Р_r существуют такие, которые входят в Р. Пусть m – наименьшее целое число такое, что 1  m  r, и Р_m входит в Р, и R - слово, которое получается, если самое левое вхождение слова Р_m в слово Р заменить словом Q_m. Тот факт, что Р и R находятся в описанном отношении, коротко запишем в виде
   

U:P├ R, (a)
если формула подстановки P_m () Q_m - простая, или в виде
U:P├ R (б)
если формула Р_т () Q_m заключительная.
В случае (а) говорят, что алгоритм U просто перево­дит слово Р в слово R; в случае (б) говорят, что алгоритм U заключительно переводит слово Р в слово R.
Пусть далее, U:P╞ R означает, что существует такая последовательность R₀, R₁, R_k слов в алфавите А, что Р = R₀, R = R_k, U:R_j├ R_j+1 для j = 0, 1, …, k-2 и либо U:R_k-1├ R_k , либо U:R_k-1├ R_k R_k (в этом последнем случае вместо U:P╞ R пишут U:P╞ R )
Положим теперь U(P) = R тогда и только тогда, когда либо U:P╞ R , либо U:P╞ R и U:R .
Алгоритм, определенный таким образом, называется нормальным алгоритмом или алгоритмом Маркова.
Работа алгоритма U может быть описана следующим образом. Пусть дано слово Р в алфавите А. Находим первую в схеме алгоритма U формулу подстановки Р_т ()Q_m такую, что Р_т входит в Р. Совершаем подстановку слова Q_m вместо самого левого вхождения слова Р_т в слово Р. Пусть R₁ – и результат такой подстановки. Если Р_т ()Q_m – заключительная формула подстановки, то работа алгоритма заканчивается, и его значением является R₁. Если формула подстановки Р_т ()Q_m – простая, то применим к R₁ тот же поиск, который был только что применен к Р и т.д. Если на конечном этапе будет получено такое слово R_i, что U:R_i , то есть ни одно из слов Р₁, ..., Р_r не входит в R_i, то работа алгоритма заканчивается, и R_t будет его значением.
Если описанный процесс на конечном этапе не заканчивается, то говорят, что алгоритм U не применим к слову Р.