Материал: Красовская Т. Ф. Основы теории алгоритмов

c) Доказать, что функция частично-рекурсивная, используя оператор минимизации.

Дана функция

f(x, y) = x y = xy , если х кратно у, и не определена, если х делится

на у с остатком

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

Рассмотрим функцию g x, y, z x yz . Эта функция по доказанному в рассмотренном выше примере есть ПРФ.

Тогда f(x, y) = x y = µz(g) = xy , если х кратно у, и не определена, если

х делится на у с остатком.

Здесь µz(g) – оператор минимизации.

Действительно, если x кратно y, то = xy – наименьший корень уравнения g(x, y, z) = 0, так как:

. . . . . . . . . . . . . . . . . . . . .

доказали, что f(x, y) получена оператором минимизации из ПРФ, т. е. является частично-рекурсивной.

d)Доказать, что функция f(x) вычислима по Тьюрингу, построив МТ

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

f(x) = x + 3; алфавит {0, 1, 2, a0}, где а0 – символ пустой клетки. Очевидно, что данный алфавит определяет запись чисел в троичной

системе исчисления.

Для такой функции нужны следующие внутренние состояния, т. е. реакции машины на символы внешнего алфавита: q1 – прибавление 3; q2 – прибавление (запоминание) 1 и, наконец, q3 – сохранение данного символа и переход к следующему; q0 – как обычно, символ остановки машины.

21

Тогда тьюрингова схема для вычисления f(x) выглядит следующим образом:

Например, если начальная конфигурация {a0 1 0 2 2 a0}, то МТ рабо-

тает так:

{a0 1 0 2 2 a0} {a0 1 0 0 2 a0} {a0 1 1 0 2 a0}

{ 1 1 0 2 a0}

{ 1 1 0 2 a0}

МТ остановилась; заключительная конфигурация дает значение функции f(x) = x + 3.

e) Ввести необходимый алфавит и составить схему нормального алгоритма, перерабатывающего слово Р в слово Q: Р = карман; Q = барабан;

Введем алфавит А: {а, б, к, м, н, р}. Cхема нормального алгоритма U, переводящего Р в Q: к →б ; м →·аб; Алгоритм работает так: карман барман барабан

ИНДИВИДУАЛЬНЫЕ ЗАДАНИЯ ПО ТЕОРИИ АЛГОРИТМОВ

Взадании а) надо доказать, что заданная функция f – примитивнорекурсивная функция.

Взадании b) надо найти (n + 1)-местную функцию с помощью заданного оператора примитивной рекурсии.

Взадании c) надо доказать, что заданная функция f – частичнорекурсивная функция, используя оператор минимизации.

Взадании d) надо построить МТ, вычисляющую данную функцию

взаданном внешнем алфавите А, причем символ пустой клетки – а и стоп-

состояние – q0.

22

В задании e) надо ввести необходимый алфавит и составить схему нормального алгоритма U, переводящего слово Р в слово Q.

Вариант 1

а) f(x) = x + 3

b)n = 1; g(x) = x2; h(x, y, z) = xz

c)f(x) = 2x ÷ 3 = 2х , если x делится на 3 без остатка; и не определена

3

востальных случаях}

d)f(x) = 2x; алфавит А: {0, 1}

e)P = бабушка; Q = дедушка

Вариант 2

а) f(x) = x! (0! = 1)

b)n = 0; g = 2; h(x, y) = x·(y + 1)

c)f(x, y) = {2x – y, если 2x ≥ y, и не определена, если 2x < y}

d)f(x) = x + 2; алфавит А: {0, 1}

e)P = трава; Q = дрова

Вариант 3

а) f(x) = x o 3 = {x – 3, если x ≥ 3; и 0, если x < 3}

b)n = 1; g(x) = x ; h(x, y, z ) = x·(y + 1)·z

c)f(x, y) = x – 2y = { x – 2y, если x ≥ 2y; и не определена, если x < 2y}

d)f(x) = 2x; алфавит А: {0, 1, 2}

e)P = репка; Q = дедка

Вариант 4

a)f(x, y) = 2x o y = {2x – y, если 2x ≥ y; и 0 , если 2x < y}

b)n = 1; g(x) = x; h(x, y, z) = x2·z

d)f(x) = x + 1; алфавит А: {0, 1, 2}

e)P = бабка; Q = внучка

Вариант 5

a)f(x, y) = max (x, y)

b)n = 0; g = 2; h(x, y) = x + 2y

c)f(x, y) = 3x – 2y = {3x – 2y, если 3х ≥ 2у, и не определена, если

3х < 2y}

23

d)f(x) = 2x + 1; алфавит А: {0, 1, 2}

e)Р = полено; Q = колесо

Вариант 6

a)f(x, y) = x + 3y

b)n = 0; g = 1; h(x, y) = x + 3y

c)f(x, y) = 2x ÷ y = 2ух , если 2х делится на у без остатка, и не опреде-

лена в противном случае}

d)f(x) = 2x o 1 = {2x – 1, если х > 0, и = 0, если х = 0}; алфавит A: {0, 1}

e)P = город; Q = парад

Вариант 7

а) f(x, y) = min (x , y)

b)n = 1; g(x) = 1; h(x, y, z) = x·(y + 1)·z

c)f(x, y) = x – 3y = {x – 3y, если х ≥ 3у, и не определена, если x < 3y}

d)f(x) = x + 5; алфавит А: {0, 1, 2, 3}

e)P = листок; Q = цветок

Вариант 8

a)f(x, y) = х у

b)n = 1; g(x) = 2x; h(x, y, z) = x·z

c)f(x, y) = x ÷ 2y = 2ху, если х делится на 2у без остатка, и не опреде-

лена в противном случае}

d)f(x) = 3x; алфавит А: {0, 1}

e)P = весна; Q = осень

Вариант 9

а) f(x, y) = 3x + y

b)n = 0; g = 3; h(x, y) = x + 4y

c)f(x) = 2x – 3 = {2x – 3, если x ≥ 2, и не определена, если x < 2}

d)f(x) = 2x + 3; алфавит А: {0, 1, 2}

e)P = кролик; Q = зайчик

Вариант 10

a)f(x, y) = (x + 1)·(y + 2)

b)n = 1; g(x) = 2x; h(x, y, z) = x + 2y + z

24

c) f(x) = 3x ÷4 = 3х , если х кратно 4, и не определена в противном

4

случае}

d)f(x) = 3x + 1; алфавит А: {0, 1, 2}

e)P = волк; Q = овца

Вариант 11

a)f(x, y) = x·(y + 1) +2

b)n = 2; g(x, y) = xy; h(x, y, z, t) = (x + 1)·y·(z + 1)·t

c)f(x, y) = x – 3y = {x – 3y, если х ≥ 3у, и не определена, если х < 3y}

d)f(x) = 2x + 2; алфавит А: {0, 1}

e)P = дорога ; Q = тропка

Вариант 12

a)f(x, y) = max{2x, y}

b)n = 2; g(x, y) = 1; h(x, y, z, t) = (x + y)·z·t

c)f(x) = 2x ÷ 5 = 2х , если х кратно 5, и не определена в противном

5

случае}

d)f(x) = 2x o 1 = {2x – 1, если х > 0, и равно 0, если х = 0 }; алфавит А: {0, 1, 2}

e)P = рубин; Q = алмаз

Вариант 13

a)f(x, y) = min {2x, y}

b)n = 0; g = 2; h(x, y) = x·(y + 1)

c)f(x, y) = 3x – 2y = {3x – 2y, если 3x ≥ 2y, не определена, если 3x < 2y}

d)f(x) = x o 2 = {x – 2, если х ≥ 2, и равно 0, если x < 2}; алфавит А: {0, 1}

e)P = секунда; Q = минута

Вариант 14

a)f(x, y) = x·(y o 2), где y o 2 = { y – 2, если y ≥ 2 и равно 0, если у < 2}

b)n = 2; g(x, y) = y + 1; h(x, y, z, t) =xy + zt

c)f(x) = 3x ÷ 4 = 3х , если х кратно 4, и не определена в противном

4

случае}

d)f(x) = x + 4 ; алфавит А: {0, 1, 2, 3}

e)P = стена; Q = дверь

25