Программная вычислимость

Определить, какие из следующих строк являются синтаксически правильными структурированными программами:

Для следующей структурированной программы $\Pi$ найти $\Pi (\sigma )$, где $\sigma =\left\{ (x, 3) ;(y, 4) ;(z, 2)\right\}$ :

Для структурированной программы П на рис. 34 на следующей странице (слева) найти $П(\sigma )$, где $\sigma =\left\{ (x, 0) ;(y, 3) ;(z, 5) ;(u, 4); (v, 2)\right\}$.

Для структурированной программы П на рис. 34 на следующей странице (справа) найти $\Pi (\sigma )$, где $\sigma =\left\{ (x, 2) ;(y, 3) ;(z, 7) ;(u, 5); (v, 0)\right\}$.

Написать структурированную программу $\Pi_{+}$, которая имеет входные переменные $x$ и $y$ и вычисляет функцию $x+y$ в переменной $x$, не изменяя $y$.

Пусть $\Pi_{+}$- это программа, которая вычисляет функцию $x+y$ в переменной $x$, не изменяя $y$ и используя дополнительные переменные $z_{0}$ и $z_{1}$. Какие из структурированных программ на рис. 35 на следующей странице вычисляют в переменной $x$ произведение $x y? \quad \circledast$

Пусть $\Pi_{\times }$- это программа, которая вычисляет функцию $x y$ в переменной $x$, используя вспомогательные переменные $z_{i}, i=0,1, \ldots , m$, $x \leftarrow y ; x \leftarrow s(x) ; y \leftarrow u ;$ $x \leftarrow y ; x \leftarrow s(x) ; v \leftarrow u ;$ $y \leftarrow s(y) ; v \leftarrow z ; v \leftarrow s(v)$; $v \leftarrow s(v)$; $u \leftarrow (x<v) ; v \leftarrow (x<y)$; if $u$ then if $v$ then $z \leftarrow y ; z \leftarrow s(z) ;$ else $z \leftarrow x ;$ end; else $z \leftarrow s(x) ;$ end; $z \leftarrow (x<v) ;$ while $z$ do $z \leftarrow (y<x) ;$ if $z$ then $y \leftarrow s(y) ;$ else $x \leftarrow s(x) ; u \leftarrow s(u) ;$ end; $z \leftarrow (x<v) ;$ end;

Рис. 34: Программы из задач 540 и 541. $z_{1} \leftarrow y ;$

$z_{3} \leftarrow x$; $z_{2} \leftarrow 0 ; x \leftarrow 0 ;$ $z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$ while $z_{1}$ do $z_{1} \leftarrow 0 ; \Pi_{+}$ $z_{0} \leftarrow 0$; $z_{2} \leftarrow s\left(z_{2}\right) ;$ $z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$ end; if $y$ then while $z_{1}$ do $z_{0} \leftarrow 0 ;$ $z_{1} \leftarrow 0 ; \Pi_{+}$ $z_{2} \leftarrow s\left(z_{2}\right) ;$ $z_{1} \leftarrow \left(z_{2}<y\right) ;$ end; else end; end;

$u \leftarrow x ; x \leftarrow 0 ; \quad u \leftarrow x ;$ while $x$ do while $x$ do $\Pi_{z} \Pi_{\times }$ $y \leftarrow s(y)$ $x \leftarrow (x<u) ;$ end; $u \leftarrow (u<x) ; \quad$ end $;$ if $u$ then $\quad u \leftarrow (u<x)$; $x \leftarrow y_{1} ; \quad x \leftarrow y ;$ else if $u$ then $x \leftarrow y ; \quad x \leftarrow y_{1} ;$ end; end;

$u \leftarrow x ; u \leftarrow s(u) ;$ $u \leftarrow x ; u \leftarrow s(u) ;$ while $x$ do $y_{1} \leftarrow y ;$ $y \leftarrow s(y) ;$ $x \leftarrow y ;$ $\Pi_{z} \Pi_{\times }$ $x \leftarrow (x<u) ;$ end; $x \leftarrow y_{1} ;$

Рис. 36: Программы из задачи 544. $\Pi_{z}$ — программа, обнуляющая переменные $z_{i}: z_{0} \leftarrow 0 ; \ldots z_{m} \leftarrow 0$; . Какие из структурированных программ на рис. 36 вычисляют в переменной $x$ квадратный корень из $x$, то есть функцию $\operatorname {sqrt}(x)=\lfloor \sqrt{x}\rfloor ? \circledast$

Пусть $\Pi_{\times }$и $\Pi_{z}$ — программы из задачи 544 на стр. 165. Какие из структурированных программ на рис. 37 на следующей странице вычисляют в переменной $x$ целую часть частного: $\lfloor x / y\rfloor$? При $y=0$ результат тоже должен быть равен нулю.

Рис. 37: Программы из задачи 545.

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

Построить программу с метками, которая по натуральному числу $i$ вычисляет число Фибоначчи $F_{i}$.

Построить программы, вычисляющие в переменной $z$ следующие функции:

Для каждой из заданных ниже рекурсивными соотношениями функций $A(x, y), B(x, y), C(x, y), D(x, y), E(x, y), G(x, y)$ и $H(x, y)$ построить вычисляющую её структурированную программу:

Написать программу, которая будет реализовывать присваивание $a \leftarrow (b<c)$; , используя присваивания видов $x \leftarrow 0 ; x \leftarrow y$; $x \leftarrow s(y) ;$ и $x \leftarrow \operatorname {eq}(y, z) ;$. Последнее изменяет значение $x$ на 1, если значения $y$ и $z$ равны, или на 0 в противном случае.

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

Пусть программа П с одной входной переменной $x$ вычисляет в переменной $y$ некоторую всюду определённую взаимно однозначную функцию $f$, область значений которой совпадает с множеством всех натуральных чисел $\omega$. Пусть $\operatorname {Var}\left(\Pi \right)=\left\{ x, y, z_{1}, \ldots , z_{m}\right\}$. Построить программу, которая вычисляет обратную к $f$ функцию $f^{-1}$ : $f^{-1}(y)=x$, если $f(x)=y$.

Пусть $П$ — программа и $\left|\operatorname {Var}\left(\Pi \right)\right|=m$. Из определений следует, что при различном выборе входных переменных и выходных переменных программа может вычислять различные функции.

Определить, сколько всего существует попарно неэквивалентных программ с метками, имеющих не более $n$ операторов и только одну переменную, которая является одновременно входной и выходной.

Определить, какие всюду определённые функции могут вычисляться программами с метками, которые имеют только одну переменную, являющуюся одновременно входной и выходной, и используют только ветвления и присваивания видов $x \leftarrow s(x)$; и $x \leftarrow \operatorname {dec}(x)$;.

Пусть программа с метками содержит только пропозициональные переменные $x_{1}, \ldots , x_{n}$, ветвления и присваивания с булевыми связками: $x_{i} \leftarrow x_{j} \wedge x_{k} ; x_{i} \leftarrow x_{j} \vee x_{k} ; x_{i} \leftarrow x_{j} \rightarrow x_{k} ; x_{i} \leftarrow \neg x_{j}$;. Предложить способ, который позволяет определить, какую функцию вычисляет такая программа.

Доказать, что никакая из функций $x+y, x \div y, x y$ и $\lfloor x / y\rfloor$ не вычисляется никакой структурированной программой без циклов.