Math Problems Vault

Problem 538

Determine which of the following strings are syntactically correct structured programs:

?

(a)

$x \leftarrow s(x) ; z \leftarrow y ; \quad u \leftarrow (s(x)<z)$ ; if $u$ then $y \leftarrow z$ ; else $y \leftarrow x$ ; end;

(b)

$x \leftarrow s(x) ; z \leftarrow y ; z \leftarrow s(z)$ ; if $x \leftarrow z$ then $y \leftarrow z$ ; else $y \leftarrow x$ ; end;

(c)

$x \leftarrow y ; \quad u \leftarrow z ; \quad u \leftarrow s(u) ; \quad x \leftarrow (u>z)$ ; while $x$ do $y \leftarrow z$ ; $u \leftarrow s(u)$ ; end;

(d)

$x \leftarrow s(z) ; z \leftarrow y ; x \leftarrow (x<x)$ ; if $x$ then $y \leftarrow z$ ; else $x \leftarrow y$ ; end;

(e)

$x \leftarrow x ; x \leftarrow x ; y \leftarrow y ; y \leftarrow y$ ;

(f)

$x \leftarrow y ; \quad u \leftarrow z ; \quad u \leftarrow s(u) ; \quad x \leftarrow (z<u)$ ; while $x$ do $y \leftarrow z$ ; $u \leftarrow s(u) ;$ end $; x \leftarrow y ;$

(g)

$x \leftarrow s(x) ; \quad z \leftarrow y ; \quad z \leftarrow s(z) ; \quad x \leftarrow (x \leftarrow z)$ ; if $x$ then $y \leftarrow z$ ; $z \leftarrow s(z)$ ; else $y \leftarrow x$ ; end; $\circledast$

Problem 539

For the following structured program $\Pi$ , find $\Pi (\sigma )$ , where $\sigma =\left\{ (x, 3) ;(y, 4) ;(z, 2)\right\}$ : $\circledast$

\begin{aligned} x \leftarrow y ; x \leftarrow s(x) ; y \leftarrow z ; y & \leftarrow s(y) ; z \leftarrow s(z) ; \\ y & \leftarrow s(x) ; z \leftarrow y ; z \leftarrow s(z) ; x \leftarrow s(x) ; \end{aligned}

?

Problem 540

For the structured program П in Fig. 34 (left) find $П(\sigma )$ , where $\sigma =\left\{ (x, 0) ;(y, 3) ;(z, 5) ;(u, 4); (v, 2)\right\}$ . $\circledast$

$x \leftarrow y ; x \leftarrow s(x) ; y \leftarrow u ;$
$y \leftarrow s(y) ; v \leftarrow z ; v \leftarrow s(v) ;$
$u \leftarrow (x<v) ; v \leftarrow (x<y) ;$
if $u$ then
$\quad$ if $v$ then
$\quad \quad z \leftarrow y ; z \leftarrow s(z) ;$
$\quad$ else
$\quad \quad z \leftarrow x ;$
$\quad$ end;
else
$\quad z \leftarrow s(x) ;$
end;
: Fig. 34 (left): Program from Problems 540 and 541.

?

Problem 541

For the structured program П in Fig. 34 (right) find $\Pi (\sigma )$ , where $\sigma =\left\{ (x, 2) ;(y, 3) ;(z, 7) ;(u, 5); (v, 0)\right\}$ . $\circledast$

$x \leftarrow y ; x \leftarrow s(x) ; v \leftarrow u ;$
$v \leftarrow s(v) ;$
$z \leftarrow (x<v) ;$
while $z$ do
$\quad z \leftarrow (y<x) ;$
$\quad$ if $z$ then
$\quad \quad y \leftarrow s(y) ;$
$\quad$ else
$\quad \quad x \leftarrow s(x) ; u \leftarrow s(u) ;$
$\quad$ end;
$\quad z \leftarrow (x<v) ;$
end;
: Fig. 34 (right): Program from Problems 540 and 541.

?

Problem 542

Write a structured program $\Pi_{+}$ that has input variables $x$ and $y$ and computes the function $x+y$ in the variable $x$ , without changing $y$ . $\circledast$

?

Problem 543

Let $\Pi_{+}$ be a program that computes the function $x+y$ in the variable $x$ , without changing $y$ and using additional variables $z_{0}$ and $z_{1}$ . Which of the structured programs in Fig. 35 compute the product $x y$ in the variable $x$ ? $\circledast$

$z_{3} \leftarrow x$ ;	$z_{3} \leftarrow y ; y \leftarrow x ;$
$z_{2} \leftarrow 0 ; x \leftarrow 0 ;$	$x \leftarrow 0 ;$
$z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$	$z_{0} \leftarrow \left(z_{2}<z_{3}\right) ;$
while $z_{1}$ do	while $z_{0}$ do
$\quad z_{1} \leftarrow 0 ; \Pi _{+}$	$\quad z_{0} \leftarrow 0 ; z_{1} \leftarrow 0 ;$
$\quad z_{0} \leftarrow 0$ ;	$\quad \Pi _{+} z_{2} \leftarrow s\left(z_{2}\right) ;$
$\quad z_{2} \leftarrow s\left(z_{2}\right) ;$	$\quad z_{0} \leftarrow \left(z_{2}<z_{3}\right) ;$
$\quad z_{1} \leftarrow \left(z_{2}<z_{3}\right) ;$	end;
end;
: Fig. 35: Programs from Problem 543.

?

Problem 544

Let $\Pi_{\times }$ be a program that computes the function $x y$ in the variable $x$ , using auxiliary variables $z_{i}, i=0,1, \ldots , m$ , as constructed in Problem 543. $\Pi_{z}$ is the program that zeros out the variables $z_{i}: z_{0} \leftarrow 0 ; \ldots z_{m} \leftarrow 0$ ;. Which of the structured programs in Fig. 36 compute in the variable $x$ the square root of $x$ , that is, the function $\operatorname {sqrt}(x)=\lfloor \sqrt{x}\rfloor$ ? $\circledast$

$u \leftarrow x ; x \leftarrow 0 ;$	$u \leftarrow x ;$	$u \leftarrow x ; u \leftarrow s(u) ;$
while $x$ do	while $x$ do	while $x$ do
$\quad \Pi _{z} \Pi _{\times }$	$\quad y_{1} \leftarrow y ;$	$\quad y_{1} \leftarrow y ;$
$\quad y_{1} \leftarrow y ;$	$\quad y \leftarrow s(y) ;$	$\quad y \leftarrow s(y) ;$
$\quad y \leftarrow s(y) ;$	$\quad x \leftarrow y ;$	$\quad x \leftarrow y ;$
$\quad x \leftarrow (x<u) ;$	$\quad \Pi _{z} \Pi _{\times }$	$\quad \Pi _{z} \Pi _{\times }$
end;	$\quad x \leftarrow (x<u) ;$	$\quad x \leftarrow (x<u) ;$
$u \leftarrow (u<x) ;$	end;	end;
if $u$ then	$u \leftarrow (u<x) ;$	$x \leftarrow y_{1} ;$
$\quad x \leftarrow y_{1} ;$	$x \leftarrow y ;$
else	if $u$ then
$\quad x \leftarrow y ;$	$\quad x \leftarrow y_{1} ;$
end;	end;
: Fig. 36: Programs from Problem 544.

?

Problem 545

Let $\Pi_{\times }$ and $\Pi_{z}$ be the programs from Problem 544. Which of the structured programs in Fig. 37 compute in the variable $x$ the integer part of the quotient: $\lfloor x / y\rfloor$ ? For $y=0$ the result should also equal zero. $\circledast$

$u \leftarrow s(x) ; x \leftarrow 0 ;$	$u \leftarrow s(x) ; x \leftarrow 0 ; i \leftarrow y$ ;	$u \leftarrow x ; i \leftarrow y ;$
$i \leftarrow (x<u) ;$	while $i$ do	while $i$ do
while $i$ do	$\quad x \leftarrow j ;$	$\quad j_{1} \leftarrow j ;$
$\quad j_{1} \leftarrow j ;$	$\quad \Pi _{z} \Pi _{\times }$	$\quad j \leftarrow s(j) ;$
$\quad j \leftarrow s(j) ;$	$\quad i \leftarrow (x<u) ;$	$\quad x \leftarrow j ;$
$\quad \Pi _{z} \Pi _{\times }$	if $i$ then	$\quad \Pi _{z} \Pi _{\times }$
$\quad i \leftarrow (x<u) ;$	$\quad j_{1} \leftarrow j ;$	$\quad i \leftarrow (x<u) ;$
end;	end;	end;
$x \leftarrow j_{1} ;$	$j \leftarrow s(j) ;$	$i \leftarrow (u<x) ;$
	$i \leftarrow (j<u) ;$	$x \leftarrow j ;$
	end;	if $i$ then
		$\quad x \leftarrow j_{1} ;$
		end;
: Fig. 37: Programs from Problem 545.

?

Problem 546

Construct programs that compute the following functions in the variable $x$ , and prove their correctness. For two-place functions, the value of the variable $y$ must remain unchanged.

?

(a)

$\operatorname {mult}(x, y)=x y$ ;

(b)

$\operatorname {dec}(x)=x \div 1$ , where $0 \div 1=0$ and $(x+1) \div 1=x$ ;

(c)

$\operatorname {sub}(x, y)=x \div y$ , where $x \div y=x-y$ if $x \geqslant y$ , and $x \div y=0$ otherwise;

(d)

$\operatorname {fact}(x)=x!$ — factorial;

(e)

$\operatorname {div}(x, y)=\lfloor x / y\rfloor$ — integer quotient;

(f)

$\operatorname {sqrt}(x)=\lfloor \sqrt{x}\rfloor$ ;

(g)

$\operatorname {pow}(x, y)=x^{y}$ — exponentiation;

(h)

$\log (y, x)=\left\lfloor \log_{y} x\right\rfloor$ ;

(i)

$\bmod (x, y)$ — the remainder of dividing $x$ by $y$ ;

(j)

$\tau (x)$ — the number of distinct divisors of $x$ , $\tau (0)=0$ . $\circledast$

Problem 547

Construct a program with labels that computes the Fibonacci number $F_{i}$ from a natural number $i$ . $\circledast$

?

Problem 548

Construct programs that compute the following functions in the variable $z$ :

?

(a)

$f_{1}(x, y)= \begin{cases} \lfloor (x+y) / 2\rfloor & \text{ when } x<y, \\ x^{2} y^{3} & \text{ otherwise; }\end{cases}$

(b)

$f_{2}(x, y)= \begin{cases} 3^{y} & \text{ when } \log_{2}(x+1) \geqslant y, \\ \left|x-y\right| & \text{ otherwise; }\end{cases}$

(c)

$f_{3}(x, y)= \begin{cases} \lfloor x y / 2\rfloor & \text{ when } \log_{2} x \leqslant y+2, \\ \left\lfloor x^{\lfloor y / 2\rfloor }\right\rfloor & \text{ otherwise; }\end{cases}$

(d)

$f_{4}(x, y)= \begin{cases} \left\lfloor \log_{3}(x+y+1)\right\rfloor & \text{ when } 2 x \leqslant y^{3}+y, \\ \lfloor \sqrt{x+y}\rfloor & \text{ otherwise; }\end{cases}$

(e)

$f_{5}(x, y)= \begin{cases} 1, & \text{ if } x \text{ is a prime number, } \\ 0 & \text{ otherwise. }\end{cases}$ $\circledast$

Problem 549

For each of the functions $A(x, y), B(x, y), C(x, y), D(x, y), E(x, y), G(x, y)$ , and $H(x, y)$ given below by recursive relations, construct a structured program computing it:

?

(a)

$A(0, y)=y+1$ ,

\begin{aligned} & A(x+1,0)=2 A(x, 1) \\ & A(x+1, y+1)=A(x, y)+x y \end{aligned}

(b)

$B(0, y)=2 y$ ,

\begin{aligned} & B(x+1,0)=B(x, 1)+1 \\ & B(x+1, y+1)=x+B(x+1, y) \end{aligned}

(c)

$C(0, y)=y+2$ ,

\begin{aligned} & C(x+1,0)=C(x, 1)+1 \\ & C(x+1, y+1)=C(x+1, y)-x \end{aligned}

(d)

$D(x, 0)=x, D(0, y)=y$ ,

D(x+1, y+1)=D(x, y+1)+x^{y} ;

(e)

$E(0, y)=y+1$ , $E(x+1,0)=E(x, 1)$ , $E(x+1, y+1)=x E(x+1, y) ;$

(f)

$G(0, y)=3$ , $G(x+1,0)=G(x, 0)+\left\lfloor \log_{2}(x+1)\right\rfloor$ , $G(x+1, y+1)=G(x+1, y)+x^{2} y ;$

(g)

$H(0, y)=y$ , $H(x+1,0)=H(x, 1)+2$ , $H(x+1,1)=H(x, 0)+1$ , $H(x+1, y+2)=y+H(x+1, y)$ . $\circledast$

Problem 550

Write a program that implements the assignment $a \leftarrow (b<c)$ ;, using assignments of the forms $x \leftarrow 0 ; x \leftarrow y$ ; $x \leftarrow s(y) ;$ and $x \leftarrow \operatorname {eq}(y, z) ;$ . The latter changes the value of $x$ to 1 if the values of $y$ and $z$ are equal, or to 0 otherwise. $\circledast$

?

Problem 551

Prove that for computing any computable function one can write a structured program without branching. Hint. First show that one can write a program without complete branches. $\circledast$

?

Problem 552

Let a program П with one input variable $x$ compute in the variable $y$ some everywhere-defined one-to-one function $f$ whose range coincides with the set of all natural numbers $\omega$ . Let $\operatorname {Var}\left[\Pi \right]=\left\{ x, y, z_{1}, \ldots , z_{m}\right\}$ . Construct a program that computes the inverse function to $f$ : $f^{-1}(y)=x$ , if $f(x)=y$ . $\circledast$

?

Problem 553

(a)(b)(c)

Let П be a program with $\left|\operatorname {Var}\left[\Pi \right]\right|=m$ . From the definitions it follows that, for different choices of input variables and output variables, the program can compute different functions.

?

(a)

What is the maximum number of functions of $n \leqslant m$ variables that П can compute? How many different functions in total can П compute? Functions with different numbers of arguments are considered different a priori.

(b)

Construct a program $\Pi_{m, n}$ that computes the maximum number of distinct functions of $n \leqslant m$ variables.

(c)

Construct a program $\Pi_{m},\left|\operatorname {Var}\left[\Pi_{m}\right]\right|=m$ , that for every $n \leqslant m$ computes the maximum number of distinct functions of $n$ variables. $\circledast$

Problem 554

Determine how many pairwise nonequivalent programs with labels there are in total, having at most $n$ statements and only one variable that is simultaneously an input and an output variable. $\circledast$

?

Problem 555

Determine which everywhere-defined functions can be computed by programs with labels that have only one variable, which is simultaneously an input and an output variable, and use only branches and assignments of the forms $x \leftarrow s(x)$ ; and $x \leftarrow \operatorname {dec}(x)$ ;. $\circledast$

?

Problem 556

Let a program with labels contain only propositional variables $x_{1}, \ldots , x_{n}$ , branches, and assignments with Boolean connectives: $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}$ ;. Propose a way to determine which function such a program computes. $\circledast$

?

Problem 557

Prove that none of the functions $x+y, x \div y, x y$ , and $\lfloor x / y\rfloor$ can be computed by any structured program without loops. $\circledast$

?