Лекции - Теория алгоритмов

Подождите немного. Документ загружается.

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

(Продолжение-6. Выполнение программы.)

► При этом числа x

, x

, ... , x

извлекаются из

хранилища R

+1

, … , R

+n

► число k - из R

t+2

► число f(x

, x

, ... , x

, k) - из R

t+3

► Новое число f(x

, x

, ... , x

, k+1) заменяет

старое число f(x

, x

, ... , x

, k) в регистре

t+3

. Поэтому при следующем исполнении

цикла в R

t+2

будет число k+1, в R

t+3

- число f(x

, ... , x

, k+1).

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

(Окончание.)

► Равенство r

t+2

и r

t+1

в команде I

сработает

лишь тогда, когда в регистре R

t+2

накопится

число y. В этот момент в регистре R

t+3

находится число f(x

, x

, ... , x

, y) .

► Выполнится переадресация к команде T(t+3,1),

которая перешлет f(x

, x

, ... , x

, y) в регистр

. После этого МНР остановится.

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

Оператор минимизации

► Теорема 3. Пусть функция f получена из

функции g с помощью оператора

минимизации. Если функция g является МНР

вычислимой, то и функция f также МНР

вычислима.

► Доказательство. Построим программу,

вычисляющую функцию f. Пусть G – программа,

вычисляющая функцию g. Будем считать, что

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

Алгоритм вычисления

► Искомая программа для функции f будет

проверять одно за другим следующие

равенства:

► g(x

,...,x

,0)=0,

► g(x

,...,x

,1)=0,

► ...........................

► g(x

,...,x

,y)=0,

► стремясь найти наименьшее k с условием

► g(x

,...,x

,k)=0.

Программа вычисления

► T(1,p+1)

► ..............

► T(n,p+n)

► I

G[p+1, p+2, ... , p+n+11]

► J(1, p+n+2, q)

► S(p+n+1)

► J(1, 1, p)

► I

T(p+n+1, 1)

► При этом команда I

является первой командой

подпрограммы G[p+1, p+2, ... , p+n+11].

Блок-схема программы

►

Работа программы

► Пусть p=max(n+1, p(G)). Распределим

память:

►Регистры R

, ... , R

предназначены для

работы подпрограммы G.

► В регистрах R

p+1

, ... , R

p+n

постоянно

хранятся аргументы x

, ... , x

►В регистр R

p+n+1

будет записываться

число k.

Работа программы

(продолжение-1)

► Командами T(1,p+1) ... T(n,p+n)

пересылаем аргументы x

, ..., x

на место

их постоянного хранения – в регистры

p+1

, ..., R

p+n

►Затем работает подпрограмма

►G[p+1, p+2, ..., p+n+11].

►Эта подпрограмма начинает цикл с

команды I

и заканчивает его командой

J(1,1,p).

Работа программы

(продолжение-2)

► При первом, втором и т.д. проходах в регистр R

последовательно заносятся числа g(x

, x

, ..., x

, 0),

g(x

, x

, ..., x

, 1) и т.д.

► Команда J(1, p+n+2,q) сравнивает содержимое

регистра R

с неизменяемым нулем в регистре R

p+n+2

. В

этот момент проверяется равенство g(x

, x

, ..., x

, k) =

0. Если равенство верное, то из регистра R

p+n+1

командой T(p+n+1,1) число k пересылается в R

машина останавливается. В противном случае

командой S(p+n+1) число k увеличивается на 1 и

происходит переход к проверке равенства g(x

, x

, ...,

, k+1) = 0.

Работа программы

(продолжение-3)

►В итоге получим искомое число k или

машина будет работать бесконечно, что

означает, что функция f(x

, x

, ..., x

) не

существует.

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