A08DPPMAT_UPS2006D00

ПРЕДЛОЖЕНИЕ 4.1 . Всякая частично рекурсивная функция f является вычислимой функцией.

Доказательство индукцией по шагу m, на котором получена функция f . Пусть m 0. Тогда f совпадает с одной из простейших функций, ко-

торые вычислимы.

Предположим, что для функций шага m утверждение верно. Пусть f — функция шага m 1. Тогда существует частично рекурсивные функции g1, g2, . . . , gk шага m, из которых получена функция f одним из трех действий: с помощью оператора суперпозиции, примитивной рекурсии или минимизации. По предположению индукции частично рекурсивные функции g1, g2, . . . , gk шага m вычислимы. Тогда и вычислима функция f . Действительно, как отмечалось при определении операторов, каждый из них, будучи применен к вычислимым функциям, вырабатывает только вычислимые функции. Поэтому f — вычислимая функция.

Предложение доказано.

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

A

f

B

Частично рекурсивные функции

Вычислимые функции

Рис. 1 Естественно, мы хотели бы продолжить расширение нашего запаса

рекурсивных функций. Для этого нам нужно в разности множеств A B взять некоторую функцию f . Она будет вычислимой, но не частично рекурсивной функцией из совокупности функций, которые используются в математике и признаются всеми как вычислимые функции.

31

Однако нас ждет неожиданное явление, которое было проверено в первой половине 20 в. на многочисленном количестве примеров. Мы не сможем найти ни одного примера вычислимой функции, не являющейся частично рекурсивной. Это наводит на мысль, что разность A B — пустое множество. Тогда A B и любая вычислимая функция частично рекурсивна.

В 1936 г. американский математик Алонзо Черч выдвинул следующее положение.

Тезис Черча. Каждая вычислимая функция частично рекурсивна.

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

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

Заметим, что Черч рассматривал лишь всюду определенные вычислимые функции. С.Клини ввел понятие частично рекурсивной функции и высказал гипотезу, что все частичные функции, вычислимые посредством алгоритма, являются частично рекурсивными. Мы не будем различать тезисы Черча и Клини и под тезисом Черча понимаем более общую формулировку.

32

Упражнения к лекции 4

ЗАДАЧА 1. Доказать, что следующие функции частично рекурсивны. Какие из этих функции примитивно рекурсивны, а какие частично рекурсивны, но не примитивно рекурсивны?

1 f x, y x y 2,			2 f x, y	x xy, 3 f x, y	xy 2,
4 f x, y x 2y,			5 f x, y xy 3,
6 f x			0, если x	0,
			не определено, если x 0,
7 f x, y		x y, если x y,
			0, не определено, если x y.
Указание. В пунктах		6	и 7 применить оператор минимизации
к функции f x, y	x y и к функции f x, y, z x				y z
соответственно.

ЗАДАЧА 2. Пусть функция f x не определена ни при одном значении x. Будет ли функция f x примитивно рекурсивной, частично рекурсивной?

ЗАДАЧА 3. Пусть f f x1, x2, . . . , xn частично рекурсивная функция от n аргументов и i1, i2, . . . , in — произвольная перестановка номеров аргументов. Рассмотрим функцию g x1, x2, . . . , xn

f xi1 , xi2 , . . . , xin (т.е. функция g получена из f перестановкой аргументов). Доказать, что функция g также частично рекурсивна.

ЗАДАЧА 4. Доказать, что функция f x	x! 1 2 3 . . . x при-
митивно рекурсивна ( по определению 0!	1).

ЗАДАЧА 5. Привести пример общерекурсивной функции, из которой с помощью оператора минимизации получается не общерекурсивная функция.

33

Пусть x, y N и y 0. Если для некоторых q, r Z выполнено равен-

ство, x

yq r, где 0 r y, то q — частное, r — остаток от деления a

на b.

Обозначим

x

q,

rest x, y

r.

y

Доопределим бинарную функцию x

при y

0 равенством x

x. Пусть

rest x, 0

x.

y

0

ЗАДАЧА 6. Проверить равенство

x

x

iy x .

sg

y

i

1

Доказать, что функция f x, y

x

примитивно рекурсивна.

y

ЗАДАЧА 7. Проверить равенство

rest x, y

x

y x .

y

Доказать, что функция rest x, y примитивно рекурсивна.

ЗАДАЧА 8. Пусть τ x — количество делителей числа x

0 и

τ 0 0. Проверить равенство

x

τ x

rest x, i .

i 1

sg

Доказать, что функция τ x примитивно рекурсивна.

ЗАДАЧА 9. Пусть σ x — сумма делителей числа x 0 и σ 0

0.

Проверить равенство

x

σ x

i sg rest x, i .

i 1

Доказать, что функция σ x примитивно рекурсивна.

ЗАДАЧА 10. К функции f x, y, z x 1 y z применен оператор минимизации. Найти полученную функцию f x, y .

34

Лекция 5. Машины Тьюринга

Другой способ для обоснования понятия алгоритма предложили независимо друг от друга и почти одновременно с Черчем и Клини английский математик А. Тьюринг и американский математик Э. Пост.

Основная идея Поста и Тьюринга заключалась в том, что алгоритмические процессы — это процессы, которые может совершать некоторая «машина». Машины, введенные Постом и Тьюрингом, имеют не очень существенное различие и обычно называются машинами Тьюринга.

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

каретка

10 1 . . . 0 0 . . . лента

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

Если каретка, расположена над некоторой ячейкой с символом 0 (с символом 1), то говорим, что каретка обозревает символ 0 (обозревает символ 1).

Машина Тьюринга имеет программу. Это конечная последовательность инструкций q0, q1, . . . , qn, каждая из которых является строкой из 5 компонент.

Пример программы.

0, 0, 0, L, 10, 1, 0, R, 11, 0, 0, L, 12, 0, 0, L, 1

35

Строка программы машины Тьюринга имеет вид i, a, x, y, z . Первая компонента в строке i — номер инструкции. Поэтому преды-

дущая программа имеет инструкции с номерами 0, 1 и 2.

Вторая компонента a равна 0 или 1. Выполняя инструкцию с номером i, машина смотрит обозреваемый кареткой символ. Если он равен 0, то исполняется команда i, 0, x, y, z ; если обозреваемый символ равен 1, то исполняется команда i, 1, x, y, z . Если команды с таким началом нет, то машина останавливается. Это единственное условие остановки машины Тьюринга. Символы x, y, z в исполняемой строке i, a, x, y, z предписывают соответственно осуществление следующих трех действий.

• Запись в обозреваемую ячейку x. При этом x 0 или x 1. Поэтому содержимое обозреваемой ячейки останется прежним или сменится на противоположное, например, 0 заменится на 1.

• Сдвиг каретки вправо или влево. Компонента y равна R или L. При y R нужно сдвинуть каретку на одну ячейку вправо, при y L сдвинуть влево.

• Переход к инструкции с номером z.

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

ПРИМЕР 5.1. Пусть дана машина Тьюринга с программой из одной инструкции

0, 0, 1, R, 0 .

(5.1)

Описать работу машины со следующими входными данными: на ленте во всех ячейках расположен символ 0.

Вначале выполняется инструкцию с номером 0. Мы имеем инструкцию (5.1), т.е. инструкцию i, a, x, y, z , где

i 0, a 0, x 1, y R, z 0.

36

Обозреваемый кареткой символ равен 0.

00 0 . . .

Поэтому нужно выполнить следующие действия: 1) заменить этот символ на 1; 2) сдвинуть каретку вправо; 3) следующей инструкцией выполнить инструкциию с номером 0. Получим следующую конфигурацию

10 0 . . .

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

Опишем вычисление значений n-арной функции машиной Тьюринга. Рассмотрим произвольное натуральное число x. Изобразим число x на ленте в виде группы из x 1 единиц. Слева и справа от этой группы расположено число 0.

0	1	1	. . .	1	0

x 1

Данную группу из x 1 единиц обозначаем знаком x . Например, группа из 3 единиц 111 изображает число 2, а группа 1 изображает число 0. Для изображения последовательности x1, x2, . . . , xn используем последовательность символов, равную 0 x1 0 x2 0 . . . 0 xn 0, где группы единиц разделены символом 0. Например, (1,2) изображаем в виде 01101110.

Пусть дана n-арная функция f x1, x2, . . . , xn . Будем говорить, что машина Тьюринга M вычисляет функцию f , если выполняются следующие условия.

1.Пусть строка x1, x2, . . . , xn содержится в области определения функции f . Тогда машина M , начиная работать и обозревая левую

единицу строки x1, x2, . . . , xn (остальная часть ленты пуста), на некотором шаге останавливается, обозревая левую единицу строки f x1, x2, . . . , xn (часть ленты справа от строки пуста).

37

2.Пусть строка x1, x2, . . . , xn не содержится в области определения функции f . Тогда машина M работает бесконечно.

ПРИМЕР 5.2 . Указать машину Тьюринга, вычисляющую функцию f x, y x y.

Рассмотрим машину M со следующей программой ( рядом с каждой инструкцией — комментарий).

0, 1,	1, R, 0	прохождение через x,
0, 0,	1, R, 1	заполнение промежутка,
1, 1,	1, R, 1	прохождение через y,
1, 0,	0, L, 2	конец y,
2, 1,	0, L, 3	стирание одного символа 1,
3, 1,	0, L, 4	стирание другого символа 1,
4, 1,	1, L, 4	движение назад,
4, 0,	0, R, 5	остановка.

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

Тезис Тьюринга. Если функция f является вычислимой, то существует машина Тьюринга вычисляющая функцию f .

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

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

38

Другие варианты определения машины Тьюринга. В качестве

«механического устройства», осуществляющего алгоритмический процесс, мы выбрали машину Тьюринга, имеющую одну ленту, в ячейки которой заносятся два символа 0 и 1. Возможно другое определение, где в ячейки ленты заносятся элементы множества A a0, a1, . . . , an . При этом помечен один из элементов a0. Он называется пустым символом и предназначен отображать факт, что ячейка пуста, т.е. не содержит символов a1, . . . , an. Лента представляется конечной, но дополняемой в любой момент пустыми ячейками слева и справа для записи новых символов. Эта ситуация может возникнуть при сдвиге каретки влево или вправо за край ленты. Тогда каретка окажется над новой пустой клеткой.

В любой момент работы машина M находится в одном из состояний q0, q1, . . . , qm. При этом q1 — начальное состояние, с которого машина начинает работать; q0 — заключительное состояние, попав в которое, машина останавливается. Итак, мы имеем два конечных, непересекающихся множества A и B, для которых используем следующую терминологию:

A a0, a1, . . . , an — символы в ячейках (внешний алфавит),

Q q0 , q1 , . . . , qm — состояния машины (внутренний алфавит).

стоп старт

Программа машины состоит из m n 1 команд. Команды имеют один из трех видов

1 qiaj qkal, 2 qiaj qkalL, 3 qiaj qkalR,

где 1 i m и 0 j n. Команда с началом qiaj срабатывает, если машина M находится в состоянии qi и каретка обозревает символ aj . Поэтому в программе должна быть ровно одна команда с началом qiaj . Действия при исполнении данных команд следующие:

•qiaj qkal — машина M переходит в состоянии qk, и одновременно содержимое aj обозреваемой ячейки сменяется на al.

•qiaj qk alL — машина M переходит в состоянии qk, содержимое aj обозреваемой ячейки сменяется на al, и каретка смещается на одну ячейку влево.

•qiaj qkalR — машина M переходит в состоянии qk, содержимое aj обозреваемой ячейки сменяется на al, и каретка смещается на одну ячейку вправо.

39

Машинным словом, или конфигурацией машины M , называется слово вида Aqk alB, где A и B слова в алфавите A . Так изображается содержимое ленты и обозреваемая ячейка. При этом считаем, что машина находится в состоянии qk, а каретка обозревает на ленте символ al. Слова A и B отражают содержимое ленты до и после символа al. Группу из x символов a на ленте будем обозначать через ax.

Считаем, что машина M вычисляет функцию f x1, x2, . . . , xn , если выполнены следующие два условия.

1. Если f x1, x2, . . . , xn существует, то машина, начиная работу с конфигурации

q101x1 . . . 01xn0,

останавливается и при этом имеет конфигурацию

q001f x1,...,xn 0 . . . 0.

2. Если f x1, x2, . . . , xn не существует, то машина работает бесконечно.

ПРИМЕР. Рассмотрим данный второй вариант определения машины Тьюринга и программу

q10 q20R, q11 q01,

q20	q31L,
q21	q21R,
q31	q31L,
q30	q00.

Нетрудно проверить, что машина вычисляет функцию f x x 1. Подробное описание данного варианта машины Тьюринга в [16], [4] и

[3]. Возможен еще вариант, когда машина имеет несколько лент. Однако, кроме технических деталей, ничего нового не возникнет. Эти машины вычисляют тот же самый класс частично рекурсивных функций.

40