7.3. Тезис Тьюринга (основная гипотеза теории алгоритмов)

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

Каждая функция, для вычисления которой существует

139

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

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

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

7.4. Нормальные алгоритмы Маркова

Теория нормальных алгоритмов была разработана русским математиком А.А. Марковым в конце 1940-х – начале 1950-х гг. ХХ в. Эти алгоритмы представляют некоторые правила по переработке слов в каком-либо алфавите, так что исходные данные и результаты являются словами в некотором алфавите.

Марковские подстановки. Алфавитом называется любое непустое множество символов. Элементы этого множества называются буквами, а последовательности букв – словами в данном алфавите. Допускается наличие пустых слов, то есть слов, не содержащих ни одной буквы. Пустое слово обозначается символом . Если и два алфавита, причем, то алфавит называется расширением алфавита .

140

Слова обозначаются латинскими буквами: (или этими же буквами с индексами). Одно слово может быть составной частью другого слова. Тогда первое слово называется подсловом второго слова или вхождением во второе. Например, если - русский алфавит, то можно рассмотреть такие слова: = параграф, = граф, =ра. Слово является подсловом слова , а - подсловом и , причем в оно входит дважды. Особый интерес представляет первое вхождение.

Марковской подстановкой называется операция над словами, задаваемая с помощью упорядоченной пары слов (), состоящая в следующем. В заданном слове находят первое вхождение слова , (если таковое имеется) и, не изменяя остальных частей слова , заменяют в нем это вхождение словом . Полученное слово называется результатом применения марковской подстановки к

слову . Если же первого вхождения в слово нет (а, следовательно, вообще нет ни одного вхождения в ), то

считается, что марковская подстановка неприменима к слову .

Частными случаями марковских подстановок являются подстановки с пустыми словами: , , .

Примеры марковских подстановок

		Результат
логика	(ика, )	лог
138578926	(85789, 00)	130026
тарарам	(ара, )	трам
поляна	(пор, т)	Не применима

141

Для обозначения марковской подстановки используется запись . Заключительные подстановки обозначаются .

Упорядоченный конечный список формул подстановок

в алфавите называется схемой нормального алгоритма в .

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

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

142

говорят, что нормальный алгоритм применим к слову .

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

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

Рассмотрим примеры нормальных алгоритмов.

Пример 1. Пусть - алфавит. Рассмотрим следующую схему нормального алгоритма в :

Всякое слово в алфавите , содержащее хотя бы одно

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

, , , , .

Пример 2. Задана функция

где - число единиц в слове 11…1.

Рассмотрим схему нормального алгоритма в алфавите .

143

Пока число букв 1 в слове не меньше 3, алгоритм последовательно стирает по три буквы. Если число букв меньше 3, но больше 0, оставшиеся буквы 1 или 11 стираются заключительно; если слово пусто, то оно заключительно переводится в слово 1. Например:

111111111111,

1111111111111111111.

Пример 3. В алфавите , являющемся расширением алфавита , рассмотрим нормальный алгоритм, задаваемый схемой (читается по столбцам).

Применим этот алгоритм к слову 3000.

Алгоритм работает следующим образом. На первом шаге применяется самая последняя подстановка: 3000. Далее начинают работать подстановки из второго столбца, меняя местами букву с соседними справа цифрами данного числа до тех пор, пока не займет крайнее правое положение:

144

.

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

А.А. Марков выдвинул гипотезу, получившую название “Принцип нормализации Маркова”. Согласно этому принципу, для нахождения значений функции, заданной в некотором алфавите, тогда и только тогда существует какой-нибудь алгоритм, когда функция нормально вычислима.

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

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

145

Следующие классы функций (заданных на натуральных числах и принимающих натуральные значения) совпадают:

а) класс всех частично рекурсивных функций;

б) класс всех функций, вычислимых по Тьюрингу;

с) класс всех нормально вычислимых функций.

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

Контрольные вопросы и упражнения

Задание 1

Доказать, что следующие функции вычислимы

1. ;

2. Усеченная разность

3. ;

4. ;

146

5. ;

6. ;

7.;

8. ;

9. ;

10.

11.

12. ;

13. Полиномиальная функция , где ;

14. ;

15. - наименьшее общее кратное чисел и ;

15. - наибольший общий делитель чисел и ;

16. - число простых делителей числа ;

17. - число положительных целых чисел, меньших и взаимно простых с (функция Эйлера). Натуральные числа называются взаимно простыми, если .

18.;

19.

20. Докажите следующие свойства усеченной разности

147

20.1.;

20.2.;

20.3.;

20.4. .

Задание 2

Разработать тьюринговые функциональные схемы для решения следующих задач

1. Сложение двух чисел в бинарной системе счисления.

2. Перевод числа из двоичной системы счисления в унарную и наоборот.

3. Умножение двух чисел в унарной системе счисления.

4. Найти функцию если и если .

5. Проверить на четность число, записанное в двоичной системе счисления.

6. Перевод числа из пятеричной системы счисления в семеричную.

7. Дано число в унарной системе счисления. Определить, делится ли оно на 3?

8. Даны два числа. Определить, какое из них больше? Алфавит любой.

9. Перевод числа из унарной системы счисления в десятичную систему счисления.

10. Вычисление модуля разности двух чисел, записанных в унарной системе счисления.

11. Произведение двух чисел в унарной системе счисления.

12. Перевод десятичного числа в унарную систему счисления.

13. Перевод числа из унарной системы счисления в бинарную.

14. Найти остаток от деления унарного числа на 2.

148

15. Извлечение целой части квадратного корня в унарной системе счисления.

16. Произведение двух чисел в бинарной системе счисления.

17. Распознать язык Дика – скобочные скелеты арифметических выражений. Примеры цепочек такого языка “(( ))”; “(( )) ((( ) ( )))”.

18. Распознать язык . Примеры цепочек этого языка “”, “” (воспользоваться соотношением или тем, квадрат натурального числа представим как сумма последовательных нечетных чисел).

19. Распознать язык, цепочки которого содержат одинаковые количества вхождений символов . Пример цепочки такого языка ””.

20. Увеличить на один двоичные числа и уменьшающие на один двоичные числа.

21. Удвоить натуральные числа, записанные в унарной системе счисления.

22. Перевести число из унарной системы в троичную.

23. Распознать четность натурального числа.

24. Найти остаток от деления натурального числа на .

25. Вычислить следующие функции, заданные на

25.1. ;

25.2. ;

25.3. ;

25.4. .

26. Вычислить следующие функции, определенные на .

26.1. ;

26.2. ;

149

27. Найти остаток от деления десятичного числа на 3.

28. Найти разность двух чисел, записанных в троичной системе счисления.

29. Дано два числа в унарной системе счисления. Разработать алгоритм, который бы обеспечивал бесконечный процесс прибавления левого числа к правому, затем левого числа к полученной сумме и так далее.

30. Реализовать алгоритм Евклида для нахождения НОД двух чисел, представленных в унарной системе счисления.

31. На ленте записаны два унарных числа, разделенных между собой звездочкой. Сохранить большее из заданных чисел, а меньшее стереть.

32. На ленте напечатан массив символов, состоящий из элементов. Составить программу для машины Тьюринга,

которая строит массив, равный данному и отстоящий от него вправо на две неотмеченные ячейки.

33. Дан массив, длина которого выражается нечетным числом. Найти середину массива, то есть стереть метку в секции, которая делит массив на две равные части.

34. Пусть на ленте машины Тьюринга помещена последовательность чередующихся между собой символов “” и “”. Необходимо составить программу, работая по которой, машина уничтожит символы “”, а “” расположить рядом

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

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

150

37. На ленте записано слово в алфавите . Верно ли, что все буквы слова одинаковы?

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

39. Дано два числа в унарной системе счисления. Представить их наибольший делитель в десятичной системе счисления.

40. Реализовать функцию .

41. Реализовать функцию .

42. Найти сумму двух чисел, заданных в бинарной системе счисления.

43. Реализовать целочисленное деление десятичного числа на 3.

44. Перевести число из пятеричной системы счисления в семеричную.

Задание 3

1. Пусть для слов в алфавите заданы следующие марковские подстановки:

; ; ; ;

; ; ; ;

; ; .

Применить каждую из них к слову .

2. Применить марковские подстановки примера 1 к слову .

3. Применить марковские подстановки из примера 1 к слову .

4. Пусть для слов в алфавите заданы следующие марковские перестановки:

151

; ; ; ;

; ; ; ;

; ; .

Применить каждую из них к слову максимально возможное число раз.

5. Каждую из марковских подстановок задачи 4 применить к слову максимально возможное число раз.

6. Каждую из марковских подстановок задачи 4 применить к слову максимально возможное число раз.

7. Каждую из марковских подстановок задачи 4 применить к словам из задач 1-3 максимально возможное число раз.

8. Нормальный алгоритм в алфавите задается схемой: , . Применить его к словам:

; ; ; ; ; ; ; ; ; .

Выявить закономерность в работе алгоритма.

9. Сконструировать нормальный алгоритм в алфавите , вычисляющий функцию ;

10. Сконструируйте нормальный алгоритм, вычисляющий словарную функцию , заданную на словах в алфавите , которая к каждому слову в алфавите и приставляет справа фиксированное слово (возможно, также в алфавите ).

11. Сконструировать нормальные алгоритмы, вычисляющие следующие функции: ; ; ; . Пользуйтесь при этом трехэлементным расширением

152

основного (цифрового) алфавита .

12. Сконструировать нормальный алгоритм, вычисляющий функцию .

13. Составить нормальный алгоритм в трехэлементном расширении основного алфавита , вычисляющий функцию .

14. Сконструировать нормальный алгоритм в четырехэлементном расширении основного алфавита , вычисляющий функцию .

15. В алфавите , являющемся расширением алфавита , рассмотрим нормальный алгоритм, задаваемый схемой:

.

Применить его к следующим словам и показать, что он вычисляет функцию :

; ; ; .

16. В алфавите , являющемся расширением алфавита , рассмотрим нормальный алгоритм, задаваемый схемой:

153

.

Применить его к следующим словам и показать, что он вычисляет функцию : ; ; ; .