Тогда тьюрингова схема для вычисления f(x) выглядит следующим образом:
аi |
а0 |
0 |
1 |
2 |
qj |
|
|
|
|
q1 |
a0Lq1 |
0Lq2 |
1Lq2 |
2Lq2 |
q2 |
1Lq0 |
1Lq3 |
2Lq3 |
0Lq2 |
q3 |
a0Cq0 |
0Lq3 |
1Lq3 |
2Lq3 |
Например, если начальная конфигурация {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
|
х |
|
|
c) f(x) = x ÷ 5 = |
|
, , если x кратно 5; и не определена в противном |
|
5 |
|||
|
|
||
случае} |
|
|
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
Вариант 15
a)f(x, y) = (x o 1) + xy, где x o 1 = {x – 1, если х ≥ 1, и равно 0, если x = 0}
b)n = 1; g(x) = 1; h(x, y, z) = x + yz
c)f(x, y) = x – 3y ={x – 3y , если x ≥ 3y, и не определена, если x < 3y}
d)f(x) = x +5; алфавит А: {0, 1, 2, 3}
e)P = брюква; Q = тыква
Вариант 16
a)f(x, y) = max {x, 2y}
b)n = 2; g(x, y) = y; h(x, y, z, t) = x·(z + 1)·t
c)f(x) = 4x ÷ 3 = 4х , если х кратно 3, и не определена в противном
3
случае}
d)f(x) = x – 2 = {x – 2 , если х ≥ 2, и не определена, если x < 2}; алфавит
А: {0, 1}
e)P = патрон; Q = карман
Вариант 17
a)f(x, y) = min {x, 2y}
b)n = 1; g(x) = x + 1; h(x, y, z) = (y + 1)·z
c)f(x, y) = 3x – 4y = {3x – 4y, если 3х ≥ 4у, и не определена, если 3x < 4y}
d)f(x) = x + 4; алфавит А: {0, 1, 2, 3 }
e)P = секрет; Q = совет
Вариант 18
a)f(x, y) = 3xy + x2
b)n = 1; g(x) = 2x; h(x, y, z) = (x + 1)·(y + 1)·z
c) f(x, y) = (x + 1) ÷ y = х у 1 , если (х + 1) делится на у без остатка, и
не определена в противном случае}
d)f(x) = 2x ; алфавит А: {0, 1, 2, 3}
e)Р = косинус; Q = тангенс
Вариант 19
a)f(x, y) = 2y2 + (x +2)
b)n = 0; g = 3; h(x, y) = 2 +xy
c)f(x) = 3x – 4 = {3x – 4, если 3x ≥ 4 , и не определена, если 3x < 4}
d)f(x) = x + 2; алфавит А: {0, 1, 2, 3}
e)Р = портрет; Q = картина
26