Банк задач по математике

Пример 4.39

(a)(b)

Покажите, что если множество $A$ можно представить в виде $A=\left\{ n \mid (\exists m) R(n, m)\right\}$ для некоторого рекурсивного предиката $R$ , то $A$ является р.п. Как следствие,

?

(a)

$F=\left\{ n \mid n \geq 2,(\exists a, b, c \geq 1) a^{n}+b^{n}=c^{n}\right\}$ является р.п. ¹

Знаменитая Великая теорема Ферма утверждает, что $F=\left\{ 2\right\}$ , и, значит, $F$ на самом деле рекурсивно. ↩

(b)

Для любой рекурсивной функции $f$ множество $J_{f}=\left\{ n \mid n \geq 1,(\exists m) f^{(m)}(n)=1\right\}$ является р.п. ¹

Пусть $f(n)=3 n+1$ , если $n$ нечётно, и $f(n)=n / 2$ , если $n$ чётно. Гипотеза $(3n+1)$ утверждает, что $J_{f}$ состоит из всех положительных целых чисел. ↩

Пример 4.41

(a)(b)

Пусть

?

(a)

$\Sigma =\left\{ 1,2, \ldots , 8,9, X\right\}$ с порядком $1 \prec 2 \prec \cdots \prec 8 \prec 9 \prec X$ .

(b)

$\Sigma =\left\{ 0,1\right\}$ и $0 \prec 1$ .

Исследуйте $\iota (n)$ .

Пример 4.42

Пусть $\Sigma =\left\{ s_{1}, s_{2}, \ldots , s_{k}\right\}$ и $s_{1} \prec s_{2} \prec \cdots \prec s_{k}$ . Покажите, что следующие функции примитивно рекурсивны:

?

(a)

$\operatorname {leng}_{\Sigma }(x)=\left|x\right|$ .

(b)

$\operatorname {concat}_{\Sigma }^{k}\left(x_{1}, x_{2}, \ldots , x_{k}\right)=x_{1} x_{2} \cdots x_{k}, k \geq 1$ .

(c)

$\operatorname {substr}_{\Sigma }(x, i, \ell )=$ подстрока $y$ строки $x$ , начинающаяся с $i$ -го символа и имеющая длину $\ell$ , если $1 \leq i \leq \left|x\right|$ и $1 \leq \ell \leq \left|x\right|-i+1$ ; и 0 в противном случае.

(d)

$\operatorname {sub}_{\Sigma }(x, y)=[x$ является подстрокой $y]$ .

(e)

head ${ }_{\Sigma }(x, y)=[x$ является префиксом $y]$ .

(f)

tail $_{\Sigma }(x, y)=[x$ является суффиксом $y]$ .

Задача 4.8.1

Разработайте многоленточную машину Тьюринга, которая «складывает» две строки над $\Sigma = \left\{ 1,2, \ldots , X\right\}$ , то есть на входах $x, y \in \Sigma^{*}$ вычисляет $z \in \Sigma^{*}$ такое, что $\iota_{\Sigma }^{-1}(z)=\iota_{\Sigma }^{-1}(x)+\iota_{\Sigma }^{-1}(y)$ .

?

Задача 4.8.2

Завершите доказательство части теоремы 4.47, касающейся примитивной рекурсии. А именно, для данных многоленточных ДМТ $M_{g}$ и $M_{h}$ , вычисляющих функции $g$ и $h$ , разработайте многоленточную ДМТ $M$ , вычисляющую функцию $f$ , которая определена из функций $g$ и $h$ с помощью примитивной рекурсии.

?

Задача 4.8.3

Докажите, что каждая частично рекурсивная функция может быть получена из начальных функций конечным числом применений операций суперпозиции и примитивной рекурсии и одним применением операции неограниченной минимизации.

?

Задача 4.8.4

(a)(b)(c)(d)

Покажите, что следующие функции, определённые на $\left\{ a, b\right\}^{*}$ , примитивно рекурсивны:

?

(a)

$f_{1}(x, y)=[x$ является подпоследовательностью $y]$ , где $x=x_{1} x_{2} \cdots x_{k}$ является подпоследовательностью $y=y_{1} y_{2} \cdots y_{m}$ , если существует последовательность целых чисел $1 \leq n_{1}<n_{2}<\cdots <n_{k} \leq m$ такая, что $y_{n_{t}}=x_{i}$ для $i=1, \ldots , k$ .

(b)

$f_{2}(x, y)=$ число вхождений $x$ в качестве подстроки в $y$ .

(c)

$f_{3}(x)=$ строка, полученная из $x$ заменой каждого вхождения $b a$ в $x$ на $a b$ . Например, $f_{3}(b a b a b)=a b a b b$ .

(d)

$f_{4}(x)=$ длина самой длинной строки $w$ такой, что и $w$ , и $w^{R}$ встречаются в качестве подстрок в $x$ .

Задача 4.8.5

Покажите, что каждый контекстно-свободный язык примитивно рекурсивен.

?

Задача 4.8.6

Пусть $f(k, 0)=\left\lfloor e^{k}\right\rfloor$ , а $f(k, n)=$ $n$ -я цифра справа от десятичной точки в десятичном разложении $e^{k}$ , где $e=\sum_{n=0}^{\infty } 1 / n!$ . Покажите, что $f$ является рекурсивной функцией. Является ли $f$ примитивно рекурсивной функцией?

?

Задача 4.8.7

(a)(b)(c)(d)

Пусть $G$ — грамматика над алфавитом $\Sigma$ . Покажите, что следующие функции $g_{1}, g_{2}, g_{3}$ частично рекурсивны:

?

(a)

$g_{1}(x)=$ минимальное число шагов в выводе $x$ , если $x \in L(G)$ , и $g_{1}(x) \uparrow$ в противном случае.

(b)

$g_{2}(x)=$ минимальная длина (число символов) вывода $x$ , если $x \in L(G)$ , и $g_{2}(x) \uparrow$ в противном случае.

(c)

$g_{3}(x, y)=1$ , если существует вывод $x$ , более короткий, чем любой вывод $y$ , при условии, что оба $x$ и $y$ принадлежат $L(G)$ , и $g_{3}(x, y) \uparrow$ в противном случае.

(d)

Пусть $g_{4}(x, y)=\begin{cases} 1 & \text{ если } g_{3}(x, y) \downarrow , \\ 0 & \text{ иначе. }\end{cases}$ Является ли $g_{4}$ рекурсивной функцией?

Задача 4.8.8

(a)(b)(c)(d)

(Функция Аккермана) Определим функцию $A: \mathbf{N}^{2} \rightarrow \mathbf{N}$ следующим образом:

\begin{aligned} A(0, n) & =\begin{cases} n+1 \quad \text{ если } n \leq 1 \\ n+2 \quad \text{ иначе } \end{cases} \\ A(m+1,0) & =1, \\ A(m+1, n+1) & =A(m, A(m+1, n)) \end{aligned}

?

(a)

Пусть $A_{m}(n)=A(m, n)$ . Чему равно $A_{2}(n)$ ? $A_{3}(n)$ ? Покажите, что каждая $A_{m}$ примитивно рекурсивна.

(b)

Покажите, что $A$ является рекурсивной функцией.

(c)

Покажите, что для каждой примитивно рекурсивной функции $f: \mathbf{N} \rightarrow \mathbf{N}$ существует целое число $k \geq 0$ такое, что $f(n) \leq A_{k}(n)$ для почти всех $n \geq 0$ (т.е. для всех, кроме конечного числа, $n \geq 0$ ).

(d)

Покажите, что $A$ не является примитивно рекурсивной.

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

Footnotes

Footnotes