Глава 19

Частично рекурсивные функции

[13/100%]
Показать
LaTeX
Задача 289

Показать, что следующие функции являются о. p. ф.:

?
(а)

fact⁡(x)=x!\operatorname {fact}(x)=x! — факториал;

(б)

min⁡(n)(x1,…,xn)\min^{(n)}\left(x_{1}, \ldots , x_{n}\right) — наименьший из аргументов, n>0n>0;

(в)

max⁡(n)(x1,…,xn)\max^{(n)}\left(x_{1}, \ldots , x_{n}\right) — наибольший из аргументов, n>0n>0;

(г)

diff =∣x−y∣=\left|x-y\right| — модуль разности;

Задача 290

Доказать, что если функция f(x1,…,xn)f\left(x_{1}, \ldots , x_{n}\right) является ч.р.ф., то и функция g(x1,…,xn)=f(xi1,…,xin)g\left(x_{1}, \ldots , x_{n}\right)=f\left(x_{i_{1}}, \ldots , x_{i_{n}}\right) является ч.р. ф. для каждой перестановки (i1,…,in)\left(i_{1}, \ldots , i_{n}\right) чисел 1,2,…,n1,2, \ldots , n.

?
Задача 291

Пусть g(x1,…,xn−1,xn)g\left(x_{1}, \ldots , x_{n-1}, x_{n}\right) — ч. р. ф., aa и b>0b>0 — натуральные числа. Доказать, что функция

f(x1,…,xn−1,xn)={a, если xn<b,g(x1,…,xn−1,xn−b), если xn⩾b f\left(x_{1}, \ldots , x_{n-1}, x_{n}\right)= \begin{cases} a, & \text{ если } x_{n}<b, \\ g\left(x_{1}, \ldots , x_{n-1}, x_{n}-b\right), & \text{ если } x_{n} \geqslant b \end{cases}

тоже является ч. р. ф.

?
Задача 292

Показать, что следующие функции являются ч.р.ф.:

?
(а)

rt⁡(n,x)=⌊xn⌋\operatorname {rt}(n, x)=\lfloor \sqrt[n]{x}\rfloor — целая часть корня nn-й степени из xx;

(б)

log⁡(i,x)=⌊log⁡ix⌋\log (i, x)=\left\lfloor \log_{i} x\right\rfloor;

(в)

τ(x)\tau (x) — количество различных делителей числа x,τ(0)=0x, \tau (0)=0;

(г)

p(x)=1p(x)=1, если xx — простое число, и p(x)=0p(x)=0 в противном случае;

(д)

pn⁡(k)\operatorname {pn}(k) — kk-е простое число в порядке возрастания, pn⁡(0)=2\operatorname {pn}(0)=2;

(е)

σ(x)\sigma (x) — сумма делителей числа xx, считать, что σ(0)=0\sigma (0)=0;

(ж)

digit⁡(n,m,i)\operatorname {digit}(n, m, i) — ii-я цифра в mm-ичном представлении числа nn: то есть если n=∑i=0∞aimin=\sum_{i=0}^{\infty } a_{i} m^{i}, где 0⩽ai<m0 \leqslant a_{i}<m, то digit⁡(n,m,i)=ai;\operatorname {digit}(n, m, i)=a_{i} ;

(з)

НОД (x,y)(x, y) — наибольший общий делитель чисел xx и yy.

Задача 293

О.р. ф., которая может быть построена без использования минимизации, называется примитивно рекурсивной. Пусть функции gg и ff примитивно рекурсивны, h=μgh=\mu g, hh — о.р.ф., и hh мажорируется функцией f:h(xˉ)<f(xˉ)f: h(\bar{x})<f(\bar{x}) для всех xˉ\bar{x}. Доказать, что hh тоже является примитивно рекурсивной.

?
Задача 294

Доказать, что если значения о. р. ф. f(x)f(x) изменить на конечном множестве, то получившаяся функция f′(x)f^{\prime }(x) также будет о. р. ф.

?
Задача 295

Доказать, что из константы 0 и функций id⁡mn\operatorname {id}_{m}^{n} с помощью суперпозиции и примитивной рекурсии нельзя получить функцию s(x)=x+1s(x)=x+1 и функцию d(x)=2xd(x)=2 x. Указание. Индукцией по построению функции доказать, что для всех таким образом построенных функций выполнено неравенство f(x1,…,xn)<2f\left(x_{1}, \ldots , x_{n}\right)<2 для произвольных x1,…,xn<2x_{1}, \ldots , x_{n}<2.

?
Задача 296

Пусть ff — взаимно однозначная на ω\omega о. р. ф. Доказать, что обратная функция f−1f^{-1} тоже является о. р. ф., явно её построив.

?
Задача 297

Пусть g(x1,…,xn,y)g\left(x_{1}, \ldots , x_{n}, y\right) — о. р. ф. Доказать, что функция

f(x1,…,xn,y,z)={∑i=0zg(x1,…,xn,y+i), при y⩽z,0, при y>z f\left(x_{1}, \ldots , x_{n}, y, z\right)= \begin{cases} \sum _{i=0}^{z} g\left(x_{1}, \ldots , x_{n}, y+i\right), & \text{ при } y \leqslant z, \\ 0, & \text{ при } y>z \end{cases}

общерекурсивна.

?
Задача 298

Доказать, что если функции f(x1,…,xn,y),g(x1,…,xn,y)f\left(x_{1}, \ldots , x_{n}, y\right), g\left(x_{1}, \ldots , x_{n}, y\right) и h(x1,…,xn,y)h\left(x_{1}, \ldots , x_{n}, y\right) общерекурсивны, то функция F(x1,…,xn)=min⁡{y:f(x1,…,xn,y)=0 или g(x1,…,xn,y)>h(x1,…,xn,y)}F\left(x_{1}, \ldots , x_{n}\right)=\min \left\{ y: f\left(x_{1}, \ldots , x_{n}, y\right)=0 \text{ или } g\left(x_{1}, \ldots , x_{n}, y\right)>h\left(x_{1}, \ldots , x_{n}, y\right)\right\} является ч. р. ф.

?
Задача 299

Допустим, что все пары (x,y)(x, y) натуральных чисел упорядочены по возрастанию суммы x+yx+y, а пары с одинаковой суммой — по возрастанию координаты xx. Этот порядок выглядит так:

(0,0),(0,1),(1,0),(0,2),(1,1),(2,0),……,(0,x+y),(1,x+y−1),…,(x,y),…,(x+y,0),… \begin{aligned} (0,0),(0,1),(1,0),(0,2) & ,(1,1),(2,0), \ldots \\ & \ldots ,(0, x+y),(1, x+y-1), \ldots ,(x, y), \ldots ,(x+y, 0), \ldots \end{aligned}

Пусть ⟨x,y⟩\langle x, y\rangle — это номер пары (x,y)(x, y) в этом порядке (будем считать, что пара (0,0)(0,0) имеет номер 0). Тогда функция ⟨⋅,⋅⟩\langle \cdot ,\cdot \rangle взаимно однозначно нумерует все пары натуральных чисел.

?
(а)

Доказать, что ⟨x,y⟩=(x+y)(x+y+1)2+x\langle x, y\rangle =\frac{(x+y)(x+y+1)}{2}+x.

(б)

Найти обратные функции ⟩1\left\rangle_{1}\right. и ⟩2\left\rangle_{2}\right. такие, что будут выполнены равенства ⟨⟨x,y⟩⟩1=x,⟨⟨x,y⟩⟩2=y\langle \langle x, y\rangle \rangle_{1}=x,\langle \langle x, y\rangle \rangle_{2}=y и, следовательно, ⟨⟨z⟩1,⟨z⟩2⟩=z\left\langle \langle z\rangle_{1},\langle z\rangle_{2}\right\rangle =z.

(в)

Показать, что все эти функции общерекурсивны.

Задача 300

Показать, что функция F(x)F(x) из задачи 281 на стр. 381 является о. р. ф. Указание. Показать сначала, что функция g(x)=⟨F(x),F(x+1)⟩g(x)=\langle F(x), F(x+1)\rangle является o. p. ф.

?
Задача 301

Для функции Аккермана

?
(а)

найти A(1,y)A(1, y) и A(2,y)A(2, y) для всех натуральных yy;

(б)

доказать, что A(3,y)=2y+3−3A(3, y)=2^{y+3}-3.