A08DPPMAT_UPS2006D00

ОПРЕДЕЛЕНИЕ 9.3 . Кодом конфигурации регистров r называется натуральное число r , задаваемое равенством

r1	3	r2	. . . p	rk	1.	(9.12)
r 2				k

При этом используется список простых чисел и учитывается, что лишь конечное число регистров не равно 0. Как кодирование (вычисление по r числа r ), так и декодирование (восстановление по данному числу r конфигурации регистров) являются алгоритмами и реализуются некоторым конечным набором инструкций.

Далее осуществляем кодирование состояний машины. Пусть дано состояние q r, j . Рассмотрим r — код конфигурации регистров и j — номер очередной команды.

ОПРЕДЕЛЕНИЕ 9.4. Кодом состояния q r, j называется число q , вычисляемое по правилу

q π r , j .

При этом функция π — функция кодирования пар натуральных чисел, определенная равенством (8.3) . Поэтому

q π r , j 2r 2j 1 1.

(9.13)

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

Правило декодирования состояния. Пусть мы знаем число q — код состояния конкретной машины и нужно восстановить q r, j — само состояние машины. Тогда 1) применяя π 1, восстановим числа r и j; 2) декодируя r , восстановим конфигурацию регистров r.

Шаг 3. Функция σ и ее вычислимость. Построим функцию

σ t, x1, . . . xn, m от n 2 переменных. Пусть даны n 2 натуральных числа t, x1, . . . xn, m. Выполним следующие действия.

1)Рассмотрим машину Mt с номером t.

2)Поместим в регистры машины Mt числа x1, . . . xn, 0, . . . .

3)Совершим m тактов работы машины Mt.

4)Пусть машина Mt совершила m тактов работы и находится в некотором состоянии q. Закодируем это состояние по правилу (9.13) в виде некоторого натурального числа q — кода состояния.

81

ОПРЕДЕЛЕНИЕ 9.5 . Значение функции σ t, x1, . . . xn, m равно q — коду состояния машины Mt после m тактов работы с начальными значениями регистров x1, . . . xn, 0, . . . .

Декодирование числа q σ t, x1, . . . , xn, m дает ответ на вопрос: какое состояние q r, j у произвольной машины Mt после m тактов работы. Так как конфигурация регистров r r1, . . . , rk, 0, . . . и номер следующей команды j однозначно задают m 1 такт работы Mt, то, имея такую вычислимую функцию σ, мы полностью обозреваем ход вычислений всех машин.

Вычислимость функции σ установим, построив ее из вычислимых

функций g и h посредством примитивной рекурсии.
1)	Укажем функцию g		и алгоритм для	ее вычисления. Име-
ем g t, x1, . . . , xn		σ t, x1, . . . , xn, 0 . Если		рассматривается число
σ t, x1, . . . , xn, m		при m	0, то машина Mt	еще не сделала ни од-
ного	такта работы. Ее регистры равны x1, . . . xn, 0, . . .				и имеют код
r	2x1 3x2 . . . pnxn	1. Номер следующей команды j			1. По правилу
(9.13) для вычисления числа q имеем

g t, x1, . . . , xn π r , 1 .

Из этой записи ясно, что функция g вычислима.

2) Укажем теперь функцию h с условием σ t, x1, . . . , xn, m 1

h t, x1, . . . , xn, m, a , где a σ t, x1, . . . xn, m . Построим алгоритм A вычисления числа b σ t, x1, . . . , xn, m 1 , т.е. укажем инструкции для по-

лучения числа b из заданных чисел t, x1, . . . , xn, m, a. Инструкции I1, I2, I3 алгоритма A описывают процесс вычисления функции h.

Нам задано число a σ t, x1, . . . , xn, m . Оно является кодом состояния машины Mt после совершения m тактов работы. Поэтому a π r , j , где r — код конфигурации регистров после m тактов, j — номер команды для исполнения в следующем m 1 такте работы машины.

I1. Применяя инструкции для π 1, восстанавливаем по числу a числа r и j, а затем по r восстанавливаем конфигурацию регистров r. Если j 0, то машина остановилась. Состояние после такта m 1 то же, что и после такта m (регистры не изменятся и номер следующей команды 0 не

изменится). Поэтому σ t, x1, . . . , xn, m 1 σ t, x1, . . . , xn, m .

Пусть j 0. Мы знаем регистры и знаем номер j следующей команды машины Mt. Нам нужно вычислить σ t, x1, . . . , xn, m 1 — код состояния

82

машины Mt после m 1-го такта работы. Для этого нам нужно найти состояние регистров и номер следующей команды.

I2. Декодируем с помощью γ 1 число t, т.е. восстанавливаем программу Pt (ее инструкции) по кодовому номеру t. При этом используем нумерацию программ γ из (8.19). Произвольной программе P сопоставляется ее номер γ P , и программа с номером t обозначается через Pt. Мы применили алгоритм декодирования γ 1.

I3. Среди инструкций программы Pt находим инструкцию с номером j. Если такой инструкции нет, то мы не сможем ее выполнить. После выполнения такта m 1 происходит остановка машины Mt. Регистры те же,

что и после такта m. Поэтому σ t, x1, . . . xn, m 1 π r , 0 .

Пусть среди инструкций программы Pt есть инструкция с номером j. Зная значения регистров и инструкцию с номером j, мы выполним один такт работы. Если мы представим, что инструкции всех программ Pt собраны в одну программу Q и мы исполняем одну из команд программы Q, то это неправильно. Действительно, Q состоит из бесконечного числа команд, что недопустимо. Любая программа — конечная последовательность команд. При этом команда — это предписание сделать какието действия над объектами. Такое понимание инструкций программы Pt мы сейчас утрачиваем. Инструкции программы Pt в данный момент — просто строки, и сами являются конструктивными объектами, с которыми манипулирует искомый алгоритм A. Поэтому Pt только набор слов в некотором алфавите и инструкцию с номером j будем считать словом A.

I2. Определите, к какому из следующих 4 видов принадлежит слово A

Z n , S n , T m, n , J m, n, q .

а) Если A вида Z n , то в конфигурации регистров замените rn на 0. Конфигурация регистров r r1, . . . , rk, 0, . . . получена у нас при декодировании числа r . Номер следующей команды равен номеру команды Z n , увеличенному на единицу.

б) Если A вида S n , то в конфигурации регистров замените rn на rn 1. Аналогично можно расписать действия в двух оставшихся случаях.

Итак, у нас описан алгоритм A для вычисления функции h. Поэтому функция h и функция σ вычислимы.

Шаг 4. Вычислимость функции U t, x1, . . . , xn . Проверим, что из вычислимости функции σ t, x1, . . . xn, m следует вычислимость универсальной функции U .

83

σ t, x1, . . . , xn, m , j t, x1, . . . , xn, m .

По определению (9.6) функции U имеем

U t, x1, . . . , xn φt x1, . . . , xn ,

т.е. число U t, x1, . . . , xn равно значению функции φt для набора аргу-

ментов x1, . . . , xn .

Поэтому имеем три равносильных утверждения:

1)число U t, x1, . . . , xn существует.

2)число φt x1, . . . , xn существует.

3)машина Mt, стартуя с набором регистров x1, . . . , xn , останавливается после некоторого m-го такта работы.

Пусть j t, x1, . . . xn, m — это номер j следующей команды для исполнения машины Mt после совершения m тактов работы. Функция

σ t, x1, . . . x1, m тесно связана с функцией j. Если q то, декодируя число q π r , j , мы получим число j

Из вычислимости функции σ получаем вычислимость всюду определенной функции j. Наличие такого m, что

j t, x1, . . . , xn, m 0,

(9.14)

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

U t, x1, . . . , xn φt x1, . . . , xn σ t, x1, . . . , xn, m .

Поэтому функция U t, x1, . . . , xn вычислима. Теорема доказана.

Диагональная функция и ее свойства. Пусть U t, x — универсальная функция для класса вычислимых функций от одной переменной. Зададим диагональную функцию d x правилом

d x	U x, x для всех x N.	(9.15)
Зададим еще одну дополнительную функцию d1 x равенством
d1 x	d x 1 для всех x N.	(9.16)

84

СВОЙСТВО 1. Диагональная функция d x и функция d1 x являются вычислимыми функциями.

Доказательство. Универсальная функция U t, x является вычислимой функцией. Значения диагональной функции d x равны U x, x , т.е. равны

U f x , f x ,

где f x x вычислимая функция. Поэтому диагональная функция d x вычислима.

Функция d1 x выражается через функцию d x следующим равенством:

d1 x d x 1 S d x .

Поэтому функция d1 x вычислима. Свойство доказано.

СВОЙСТВО 2. Пусть f x — произвольная вычислимая функция. Тогда функция f x и диагональная функция d x совпадают хотя бы при одном значении аргумента. В качестве такого значения аргумента можно взять номер a функции f x при нумерации унарных функций.

Доказательство. По условию функция f x вычислима. Поэтому она получена из универсальной функции U t, x при некотором значении пе-

ременной t a N, т.е.
f x U a, x для всех x N.	(9.17)

По заданию универсальной функции U a, x в (8.22) имеем U a, x φa x . Поэтому функция f x есть функция φa и имеет номер a при нумерации унарных функций.

Подставим значение x a в правила для задания функций f x и d x в равенствах (9.17) и (9.15). Получим

f a U a, a и d a U a, a .

Итак, функция f x и диагональная функция d x совпадают при значении аргумента x a, причем a — это номер функции f x при нумерации унарных функций.

Свойство доказано.

85

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

ТЕОРЕМА 9.2. Не существует вычислимой, всюду определенной функции от двух переменных, универсальной для класса вычислимых, всюду определенных функций от одной переменной.

Доказательство. Предположим противное, т.е. существует всюду определенная вычислимая функция U t, x от двух переменных, являющаяся универсальной для класса вычислимых, всюду определенных функций от одной переменной.

В классе частичных вычислимых функций рассматривалась диагональная функция d x и функция d1 x . Рассмотрим аналогичную диагональную функцию d x и функцию d1 x в классе всюду определенных вычислимых функций. Пусть

d x U x, x ,

d1 x d x 1 для всех x N.

(9.18)

Поскольку универсальная функция U t, x всюду определена, то и функции d x и d1 x являются всюду определенными, вычислимыми функциями. Для функции d x имеем аналогичное свойство 2. Так как функция d1 x вычислима и всюду определена, то она должна совпадать с диагональной функцией d x хотя бы при одном значении аргумента. Однако равенство d1 x d x 1 запрещает такое совпадение, противоречие. Значит, допущение о существовании универсальной функция U t, x неверно.

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

Пусть даны две частичные функции f x и g x из N в N . Функция g x называется продолжением функции f x , если для любого a N из существования f a следует существование g a и равенство f a g a . При этом возможно, что значение f a не существует, а функция g x при

xa имеет некоторое значение.

Естественно возникает вопрос: можно ли продолжить произвольную вычислимую функцию f x до всюду определенной вычислимой функции g x ? Тем самым должно выполняться равенство f a g a , если значение старой функции f a существует, и мы должны как-то определить значение новой функции g a , если f a не существует.

86

ТЕОРЕМА 9.3 . Существует вычислимая функция f x , которую нельзя продолжить до всюду определенной вычислимой функции g x .

Доказательство. Проверим, что в качестве искомой вычислимой функции f x , которую нельзя продолжить до всюду определенной вычислимой функции, можно взять функцию d1 x из (9.16).

Предположим противное, существует всюду определенная вычислимая функция g x , которая является продолжением функции d1 x . По-

кажем, что для произвольного значения x	a имеем g a d a .
Возможны два случая: 1) d a существует или 2) d a не существует.
Случай 1), d a существует. Тогда d1 a	d a 1 определена при

xa и d1 a d a . Функция g x является продолжением функции

d1 x . Поэтому g a d1 a d a .

Случай 2), d a не существует. В этом случае d a не определена при x a, а функция g a определена при x a, поскольку она всюду определена. Снова получаем g a d a . Итак, функция g x ни при каком значении аргумента не совпадает со значением функции d x .

По свойству 2) значения произвольной вычислимой функции хотя бы один раз должны совпадать со значением функции d x . Для вычислимой функции g x это не выполнено, противоречие. Поэтому продолжение g x вычислимой функции d1 x не существует.

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

87

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

ЗАДАЧА 1. Найти номера следующих команд при нумерации β:

S 3 и T 2, 1 .

ЗАДАЧА 2. Найти номера следующих команд при нумерации β:

Z 3 и J 3, 2, 1 .

ЗАДАЧА 3. Найти кодовый номер программы P при нумерации γ, где P — программа, состоящая из следующих команд: S 2 , T 2, 1 .

ЗАДАЧА 4. Составить программу P для вычисления функции f x x 2, и найти кодовый номер программы P .

ЗАДАЧА 5. Выписать команды программы P100.

ЗАДАЧА 6. Выписать команды программы P4127.

ЗАДАЧА 7. Найти область определения и область значений

функций φ14127 и φ24127.

ЗАДАЧА 8. Дана МНР со следующей программой:

I1 S 1

I2 T 1, 2

В регистр R1 перед первым тактом работы машины занесено число 1, остальные регистры заполнены нулями.

Найти конфигурацию регистров после 1,2 и 3 тактов работы машины и указать номер j следующей исполняемой команды. Вычислить коды конфигурации регистров и коды состояния машины после данных тактов работы.

ЗАДАЧА 9. Дана МНР со следующей программой:

I1 J 2, 3, 5

I2 S 1

I3 S 3

I4 J 1, 1, 1

88

В регистры R1 и R2 перед первым тактом работы машины занесено число 1, остальные регистры заполнены нулями.

Найти конфигурацию регистров после 1,2,4,5 тактов работы машины, и указать номер j следующей исполняемой команды. Вычислить коды конфигурации регистров и коды состояния машины после данных тактов работы.

ЗАДАЧА 10. Приведем заведомо неверное доказательство того, что всякую вычислимую функцию f x можно продолжить до всюду определенной вычислимой функции g x .

Пусть D — область определения функции f x . Рассмотрим произвольное x N. Если x D (т.е. число f x определено), то считаем, что g x f x . Если x D (т.е. число f x не определено), то считаем, что g x 0. В обоих случаях имеются инструкции для вычисления числа g x . Поэтому функция g x вычислима. Очевидно, что g x всюду определена и является продолжением функции f x . Итак, произвольная вычислимая функция f x продолжена до всюду определенной вычислимой функции g x . Однако по теореме 9.3 существует вычислимая функция, которую нельзя продолжить до всюду определенной вычислимой функции. Где ошибка в рассуждениях?

89

Лекция 10. Нормальные алгорифмы

В данный момент мы располагаем двумя вариантами строгого определения понятия алгоритма. Первый вариант (тезис Черча) выражает понятие алгоритма на языке функций. Вторая формулировка определяет понятие алгоритма с помощью абстрактной вычислительной машины (машины Тьюринга или МНР).

Третий вариант формализации понятия алгоритма предложен российским математиком А.А.Марковым [17]. В этом определении считается, что алгоритмический процесс — это процесс переработки слов некоторого алфавита. Действительно, многие алгоритмические процессы можно рассматривать как процессы переработки слов.

Проанализируем, например, сложение натуральных чисел. На входе алгоритма поступают два натуральных числа x и y. Пусть числа x и y записаны в десятичной системе счисления, например, x 1253 и y 2754. Мы рассматриваем цифры 0, 1, 2, . . . , 9 и знак сложения ,, ” как буквы. Получаем алфавит A 0, 1, 2, . . . , 9, из 11 букв. При операции сложения на вход алгоритма поступает слово 1253 2754 длины 9. На выходе алгоритма имеем слово 4007 в алфавите A . Поэтому сложение натуральных чисел — это процесс переработки слов в алфавите A .

Следуя А.А.Маркову, наряду со словом «алгоритм» будем употреблять также слово «алгорифм». Алгоритмы, которые являются процессами переработки слов, назовем вербальными алгорифмами. Поскольку речь идет о произвольных, а не строго заданных правилах действий со словами, то понятие вербального алгорифма является интуитивным понятием. Среди вербальных алгорифмов выделим некоторые алгорифмы — нормальные алгорифмы со строго заданными правилами переработки слов. Поэтому понятие нормального алгорифма является строгим математическим понятием. Введем это понятие.

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

A задается двумя компонентами: 1) алфавитом алгорифма, 2) схемой алгорифма.

1) Алфавит нормального алгорифма A — это некоторая конечная совокупность символов A a1, . . . , am . Элементы из A мы будем называть буквами. Из букв алфавита A составляются слова — конструктивные объекты, которые поступают на вход и перерабатываются в алгорифме A. При этом говорят, что A — алгорифм в алфавите A .

90