А.А. Вороненко, В.С. Федорова - Дискретная математика. Задачи и упражнения с решениями (1060726), страница 11
Текст из файла (страница 11)
Для вычисления x+22 МТ приписывает две единицы к x и с помощью двух«бегающих» нулей ищет середину слова, после чего удаляет вторую половину.q1 1q1 1R,q1 0q2 0R,q2 1q3 1R,q3 0q4 0L, тогда y = 0q3 1q5 1R,q5 0q6 0L, тогда y = 1q5 1q5 1R, цикл, y > 1q10 1q10 1R,q10 0q11 1L,q11 1q12 0L,Двигаем левыйq12 0q15 0R,q12 1q13 1L,q13 1q13 1L,q13 0q14 1R,q14 1q9 0R,y = 1, реализуем x + 2q6 1q6 0L, стёрли yq6 0q7 1R,q7 0q8 1L,q8 1q8 1L,q8 0q0 0R,y = 0, реализуемq4 1q4 1L,q4 0q9 1R,нольвправоУдаляем массив справа q15 0q15 0R,q15 1q16 0R,q16 1q16 0R,q16 0q17 0L,x+22Сдвигаем головку под левую единицу q17 0q17 0L,q17 1q18 1L,q18 1q18 1L,q18 0q0 0R.Двигаем правый ноль влевоq9 0q15 0R,q9 1q10 1R,IЗанятие № 2.11Примитивно рекурсивные функции94V.2.1(9, 10, 12).
Используя в качестве исходных функций толькоконстанты и простейшие функции, построить примитивно рекурсивныесхемы, описывающие нижеследующие функции:29) x2 + 2y ;1,если x = 0,10) x! =1 · 2 · . . . · x, если x > 1;0, если x + y чётное,12) x ⊕ y =1, если x + y нечётное.J9. Для начала реализуем схему f (x, y) = x + y:f (x, 0) = x,f (x, y + 1) = f (x, y) + 1.Затем схему g(x, y) = x · y:g(x, 0) = 0,g(x, y + 1) = g(x, y) + x.Искомая функция легко получается их суперпозицией.10.
Функция f (x) = x! получается применением операции примитивной рекурсии к функциям 1 и g(x, y) = (x + 1) · y:f (0) = 1,f (x + 1) = (x + 1) · f (x).12. Функция sg(x) реализуется схемой: sg(0) = 1, sg(x + 1) = 0. Построим схему, реализующую функцию g(x) = x (mod 2) — счетчик чётности:g(0) = 0,g(x + 1) = sg(g(x)).Тогда сумму по модулю 2 можно представить следующей схемой:f (x, 0) = g(x),f (x, t + 1) = sg(f (x, t)).IV.2.2(1, 3). Применяя операцию примитивной рекурсии к функциямg(x) и h(x, y, z) по переменной y, построить функцию f (x, y) = R(g, h),записав её в «аналитической» форме:1) g(x) = x, h(x, y, z) = x + z;3) g(x) = 2x , h(x, y, z) = 2x · z.95J1. По определению операции примитивной рекурсии:f (x, 0) = g(x) = x,f (x, t + 1) = h(x, t, f (x, t)) = x + f (x, t).Тогда:f (x, 0) = x,f (x, 1) = x + f (x, 0) = x + x = 2x,f (x, 2) = x + f (x, 1) = x + 2x = 3x,............f (x, t + 1) = x + f (x, t) = x + tx = x(t + 1).Cледовательно, f (x, y) = x(y + 1).3.
По определению операции примитивной рекурсии:f (x, 0) = g(x) = 2x ,f (x, t + 1) = h(x, t, f (x, t)) = 2x · f (x, t).Тогда:f (x, 0) = 2x ,f (x, 1) = 2x · f (x, 0) = 2x · 2x = 22x ,f (x, 2) = 2x · f (x, 1) = 2x · 22x = 23x ,............f (x, t + 1) = 2x · f (x, t) = 2x · 2tx = 2x(t+1) .Следовательно, f (x, y) = 2x(y+1) .IV.2.3 (1– 3, 5, 8, 11).
Доказать примитивную рекурсивность следующих функций, используя простейшие функции и функции sg(x), sg(x),· y, x · y, x ⊕ y:x + y, x −1) |x − y|;2) min (x, y);3) max (x,y);x,если y = 0,x5)=целая часть от деления х на у, если y > 1;yai , если x = i, i = 0, 1, . . . , m,8) f (x) =cв ином случае;здесьa,a,...,am , c — произвольные натуральные числа;01√11) [ x].96J Для доказательства представим функции в виде суперпозиции данных примитивно рекурсивных функций.· y) + (y −· x).1.
|x − y| = (x −· y) + y · sg(x −· y).2. min (x, y) = x · sg(x −· y) + y.3. max (x, y) = (x −5. Искомую функцию можно представить в видеxxXx X· yt).=(yt 6 x) =sg((x + 1) −yt=1t=1Функция g(x, y, z) =zP· yt) описывается схемой:sg(x −t=1g(x, y, 0) = 0,· y(z + 1)) + g(x, y, z).g(x, y, z + 1) = sg(x −Отождествив переменные x и z функции g(x, y, z), получим искомую функцию.mmQP8. f (x) = ai · sg|x − i| + c · sg|x − i|.i=011.
Функция g(x, y) =yPi=0· t2 ) описывается следующей схемой:sg(x −t=1g(x, 0) = 0,· (y + 1)2 ) + g(x, y).g(x, y + 1) = sg(x −√Так как функцию f (x) = [ x] можно представить в видеf (x) =xX2(t 6 x) =t=1xX· t2 ),sg((x + 1) −t=1то она является примитивно рекурсивной.IV.2.4(1, 2, 5).1. Доказать, что если функция g(x) примитивно рекурсивна, то всюду определённая функция f (x), отличающаяся от g(x) только вконечном числе точек, является примитивно рекурсивной.2. Пусть g1 (x) и g2 (x) — примитивно рекурсивные функции.
Доказать, что функцияg1 (x), если a 6 x 6 b,f (x) =g2 (x), в ином случае,где 0 6 a 6 b (a ∈ N, b ∈ N), примитивно рекурсивна.975. Пусть функция g(x1 , . . . , xn−1 , xn ), n > 1, примитивно рекурсивна.Доказать, что следующие функции примитивно рекурсивны:xnXnа) f1 (ex )=g(x1 , . . . , xn−1 , i);i=0xnYnб) f2 (ex )=g(x1 , . . .
, xn−1 , i).i=0J1. Пусть a1 , . . . am — все точки, в которых значения f и g различаются. Тогда функцию f (x) можно выразить через g(x) с помощьюсуперпозиции примитивно рекурсивных функций:mmYXsg|x − ai |,f (x) =ci · sg|x − ai | + g(x) ·i=1i=1где ci = f (ai ) — значения функции f в точках ai , i = 1, m.Следовательно, f (x) — примитивно рекурсивна.2. Функцию f (x) можно выразить через g1 (x) и g2 (x) с помощьюсуперпозиции примитивно рекурсивных функций:· x)((x+1) −· a)]+g2 (x)·sg[((b+1) −· x)((x+1) −· a)].f (x) = g1 (x)·sg[((b+1) −5. a) Функцию f1 (exn ) можно получить как результат примененияоперации примитивной рекурсии к функциям g(x1 , .
. . , xn−1 , 0) иh(x, y) = x + y:f1 (x1 , x2 , . . . , xn−1 , 0) = g(x1 , x2 , . . . , xn−1 , 0),f1 (x1 , x2 , . . . , xn−1 , t + 1) = h(g(x1 , x2 , . . . , xn−1 , t + 1), f1 (x1 , x2 , . . . , xn )).б) Функцию f2 (exn ) можно получить как результат примененияоперации примитивной рекурсии к функциям g(x1 , . . .
, xn−1 , 0) иh(x, y) = x · y:f1 (x1 , x2 , . . . , xn−1 , 0) = g(x1 , x2 , . . . , xn−1 , 0),f1 (x1 , x2 , . . . , xn−1 , t + 1) = h(g(x1 , x2 , . . . , xn−1 , t + 1), f1 (x1 , x2 , . . . , xn )).IЗанятие № 2.12Частично рекурсивные функцииV.2.5 (1– 3, 7, 11, 12). Применить операцию минимизации к функции f по переменной xi . Результирующую функцию g(x) представить в«аналитической» форме:981)2)3)7)11)12)Jf (x1 ) = 3, i = 1;f (x1 ) = x1 + 2, i = 1;· 2, i = 1;f (x1 ) = x1 −x1f (x1 ) = [ 2 ], i = 1;· x2 , i = 1, 2;f (x1 , x2 ) = x1 −· 2x2 ), i = 1.f (x1 , x2 ) = sg(x1 −1. Так как множество значений функции f (x) Ef = {3}, то g(x)не определена при x 6= 3. Применим операцию минимизации кf (x1 ) : f (0) = 3, следовательно, g(3) = 0.
В качестве «аналитической» записи функции g(x) можно выбрать формулу −|x − 3|.2. Ef = {2, 3, . . . }. Применим операцию минимизации к f (x1 ) :f (0) = 2,f (1) = 3,......f (x1 ) = x1 + 2,тогдаg(2) = 0,g(3) = 1,......g(x + 2) = x.Следовательно, g(x) = x − 2.3. Ef = {0, 1, . . .
}. Применим операцию минимизации к f (x1 ) :f (0) = 0,f (1) = 0,f (2) = 0,тогдаf (3) = 1,......f (x1 ) = x1 − 2 (x1 > 2),g(0) = 0,−−g(1) = 3,......g(x − 2) = x.Следовательно, g(x) = (x + 2) · sg(x).7. Ef = {0, 1, . . . }. Применим операцию минимизации к f (x1 ) :f (0) = 0,f (1) = 0,f (2) = 1,f (3) = 1,......f (2x1 ) = x1 ,f (2x1 + 1) = x1 .Следовательно, g(x) = 2x.9911.
Минимизация по x1 :· x2 = 0,0−......· x2 = 0,x2 −· x2 = 1,(x2 + 1) −......· x2 = t.(x2 + t) −· x2 ) = (x1 + x2 ) · sg(x1 ).Отсюда µx1 (x1 −Минимизация по x2 :· 0 = x1 ,x1 −· 1 = x1 −· 1,x1 −......· x1 = 0,x1 −......· (x1 + t) = 0.x1 −· x2 ) = x1 − x2 .Отсюда µx2 (x1 −· 2x2 ) всюду определена и принимает два значе12. Функция sg(x1 −ния: 0 и 1.· 2x2 ) = 0,sg(0 −......· 2x2 ) = 0,sg(2x2 −· 2x2 ) = 1,sg((2x2 + 1) −......· 2x2 ) = 1.sg((2x2 + t) −Поэтому· 2x2 ))= 0,µx1 (sg(x1 −x1 =0· 2x2 ))µx (sg(x1 −= 2x2 + 1.x1 =11Функция определена в двух точках x1 = 0, x1 = 1.
Во всех остальных точках значение функции не определено. Выразим искомуюфункцию аналитически:· 2x2 )) = (1 − x1 ) · 0 + sg(x1 )(2x2 + 1). Iµx1 (sg(x1 −100V.2.7(1, 6). Доказать, что следующие функции примитивно рекурсивны: · 1x−1) µx;2√ · [ x]2 .6) µx x −J Для доказательства достаточно представить функцию в виде суперпозиции примитивно рекурсивных функций.h · i1. Пусть f (x) = µx x−1. Множество значений функции Ef =2{0, 1, . . .
}. При α1 > 0 минимальным решением уравнения f (y) =α1 является y = 2α1 + 1. При α1 = 0 наименьшим решением является y = 0. Определим g(x):(0,при x = 0,g(x) =2x + 1, при x > 0.Тогда g(x) = sg(x) · (2x + 1). Функции sg(x), x + y и x · y являютсяпримитивно рекурсивными, следовательно, их суперпозиция тожепримитивно рекурсивна.√ · [ x]2 . Ef = {0, 1, .
. . }. При x = n2 , n ∈6. Пусть f (x) = µx x −{0, 1, . . . }, функция f (x) = 0. На интервале In = (n2 , (n + 1)2 )функция возрастает и принимает значения Efn = {0, 1, . . . , (n +1)2 −n2 } = {0, 1, . . . , 2n+1}. На каждом интервале In добавляетсядва новых значения f (x) : x = 2n, x = 2n + 1. Минимальнымрешением уравнения f (y) = α1 при любых α1 является y = [(α1 +1)/2]2 + α1 . Следовательно,g(x) = [(x + 1)/2]2 + xявляется суперпозицией примитивно рекурсивных функций, следовательно, примитивно рекурсивна.IV.2.8(1, 2).1. Доказать, что однократное применение операции минимизации квсюду определённой числовой функции приводит к функции, определённой хотя бы в одной точке.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
