Chapter 3
3.2
Suppose a Turing machine contains following program lines:
$$
\begin{align}
1:\; &\left\langle q_0,\Gamma_0,q_0,\Gamma_0,+1 \right\rangle\\
2:\; &\left\langle q_0,\Gamma_1,q_1,\Gamma_1,0 \right\rangle ,
\end{align}
$$
where $q_0 = q_s,$ and $q_1=q_H$.
We encode each program line $\left\langle q,x,q’,x’,s \right\rangle$ as follows:
- The state $q_i$ is encoded by the letter ‘$D$’ followed by the letter ‘$A$’ repeated $i$ times
- The alphabet of symbol $\Gamma_i$ is encoded by the letter ‘$D$’ followed by the letter ‘$C$’ repeated $i$ times
- The movements of tape-head (-1, +1, and 0) are encoded by the letter ‘$L$’, ‘$R$’, and ‘$N$’, respectively
Therefore, a program line $\left\langle q_0,\Gamma_0,q_0,\Gamma_0,+1 \right\rangle$ is encoded as
$$
\begin{equation}
DDDDR.
\end{equation}
$$
By separating program lines by semicolons we then can describe the program as
$$
\begin{equation}
DDDDR;DDCDADCN.
\end{equation}
$$
Then we replace each of the symbols as follows:
$$
\begin{align}
D\; \rightarrow\; 0 \\
A\; \rightarrow\; 1 \\
C\; \rightarrow\; 2 \\
L\; \rightarrow\; 3 \\
R\; \rightarrow\; 4 \\
N\; \rightarrow\; 5 \\
;\; \rightarrow\; 6
\end{align}
$$
The result is 0-0-0-0-4-6-0-0-2-0-1-0-2-5.
Since every positive integer has a unique prime factors
$$
\begin{equation}
p_1^{a_1}p_2^{a_2}\cdots p_k^{a_k},
\end{equation}
$$
where $p_i$ are distinct prime numbers, and
$$
\begin{equation}
a_1,a_2,\cdots ,a_k
\end{equation}
$$
are non-negative integers, we can use this product as a Turing number for this program. Thus the number is
$$
\begin{equation}
2^0\times 3^0\times 5^0\times 7^0\times 11^4\times 13^6\times 17^0\times 19^0\times 23^2\times 29^0\times 31^1\times 37^0\times 41^2\times 43^5
\end{equation}
$$
3.3
Suppose we have a two-tape Turing machine which takes as input binary numbers on the first tape and blanks on the remainder of both tapes, except the endpoint marker $\triangleright$. The machine contains following program lines can outputs the bits of $x$ in reverse order on the second tape.
$$
\begin{align}
1&: \left\langle q_s,\triangleright ,\triangleright ,q_1,\triangleright ,\triangleright , +1, +1 \right\rangle \\
2&: \left\langle q_1,0,b,q_1,0,b,+1,0 \right\rangle \\
3&: \left\langle q_1,1,b,q_1,1,b,+1,0 \right\rangle \\
4&: \left\langle q_1,b,b,q_2,b,b,-1,0 \right\rangle \\
5&: \left\langle q_2,0,b,q_2,b,0,-1,+1 \right\rangle \\
6&: \left\langle q_2,1,b,q_2,b,1,-1,+1 \right\rangle \\
7&: \left\langle q_2,\triangleright ,b,q_H,\triangleright ,b,0,0 \right\rangle
\end{align}
$$
3.4
Suppose we have a two-tape Turing machine which takes as input binary numbers on the first tape. The machine contains following program lines can output the bit string which is the answer of modulo-2 addition.
$$
\begin{align}
1&: \left\langle q_s,\triangleright ,\triangleright ,q_1,\triangleright ,\triangleright ,+1,+1 \right\rangle \\
2&: \left\langle q_1,0,b,q_1,0,0,+1,0 \right\rangle \\
3&: \left\langle q_1,0,0,q_1,0,0,+1,0 \right\rangle \\
4&: \left\langle q_1,0,1,q_1,0,0,+1,0 \right\rangle \\
5&: \left\langle q_1,1,b,q_1,1,1,+1,0 \right\rangle \\
6&: \left\langle q_1,1,0,q_1,1,1,+1,0 \right\rangle \\
7&: \left\langle q_1,1,1,q_1,1,1,+1,0 \right\rangle \\
8&: \left\langle q_1,b,0,q_2,b,0,+1,0 \right\rangle \\
9&: \left\langle q_1,b,1,q_2,b,1,+1,0 \right\rangle \\
10&: \left\langle q_2,0,0,q_2,0,0,+1,0 \right\rangle \\
11&: \left\langle q_2,0,1,q_2,0,1,+1,0 \right\rangle \\
12&: \left\langle q_2,1,0,q_2,1,0,+1,0 \right\rangle \\
13&: \left\langle q_2,1,1,q_2,1,1,+1,0 \right\rangle \\
14&: \left\langle q_2,b,0,q_3,b,0,-1,0 \right\rangle \\
15&: \left\langle q_2,b,1,q_3,b,1,-1,0 \right\rangle \\
16&: \left\langle q_3,0,0,q_H,0,0,0,0 \right\rangle \\
17&: \left\langle q_3,0,1,q_H,0,1,0,0 \right\rangle \\
18&: \left\langle q_3,1,0,q_H,0,1,0,0 \right\rangle \\
19&: \left\langle q_3,1,1,q_H,1,0,0,0 \right\rangle \\
\end{align}
$$
3.5
Define $A(x)$ as the program that outputs “YES” if an arbitrary program $M$ halts, and outputs “NO” if it doesn’t. That is,
$$
\begin{equation}
A(M) =
\begin{cases}
\mathrm{YES} & \mathrm{if\; program\;} M\; \mathrm{halts,} \\
\mathrm{NO} & \mathrm{otherwise.}
\end{cases}
\end{equation}
$$
Define $B(M)$ as the program that never halts if $A(M)=\mathrm{YES}$, and halts if $A(M)=\mathrm{NO}$. It follows from the definition of $B(M)$ that exactly one of the following two cases must be hold:
- $A(M)=\mathrm{YES}$ and so $B(M)$ never halts. In this case $B(B(M))$ halts.
- $A(M)=\mathrm{NO}$ and so $B(M)$ halts. In this case $B(B(M))$ never halts.
In either cases there is a conflict. Therefore, there is no algorithm to determine whether $M$ halts with no inputs.
3.8
NOT:
AND:
XOR:
(i)
$$
\begin{align}
\mathrm{XOR} &= \left(\bar{x}\land y\right) \lor \left( x\land\bar{y}\right) = \left(\bar{x}\land y\right) \lor \left( x\land\bar{y}\right) \lor \left( x\land\bar{x}\right) \lor \left( y\land\bar{y}\right) \\
&= \left( x\land\left(\bar{x}\lor\bar{y}\right)\right) \lor \left( y\land\left(\bar{x}\lor\bar{y}\right)\right) \\
&= \left( x\land\left(\overline{x\land y}\right)\right) \lor \left( y\land\left(\overline{x\land y}\right)\right) \\
&= \overline{\left(\overline{x\land\left(\overline{x\land y}\right)}\right) \land \left(\overline{y\land\left(\overline{x\land y}\right)}\right)}
\end{align}
$$
(ii)
$$
\begin{align}
\mathrm{XOR} = \left(\bar{x}\land y\right) \lor \left(x\land\bar{y}\right) = \overline{\overline{\bar{x}y} \land \overline{x\bar{y}}}
\end{align}
$$
3.9
If $g(n)$ is $\Omega(f(n))$,
$$
\begin{equation}
cf\left( n\right) \le g\left( n\right) \Leftrightarrow f\left( n\right) \le \frac{1}{c}g\left( n\right) \;\;\; (\mathrm{\;for\;positive}\;c)
\end{equation}
$$
This means $f(n)$ is $O(g(n))$.
If $f(n)$ is $O(g(n))$,
$$
\begin{equation}
f\left( n\right) \le c\left( g\left( n\right)\right) \Leftrightarrow \frac{1}{c} f\left( n\right) \le g\left( n\right) \;\;\; (\mathrm{\;for\;positive}\;c)
\end{equation}
$$
This means $g(n)$ is $\Omega (f(n))$. So, $f(n)$ is $O(g(n))$ if and only if $g(n)$ is $\Omega(f(n))$.
If $g(n)$ is $\Theta (f(n))$, $g(n)$ is both $O(f(n))$ and $\Omega (f(n))$. As we have done above, this implies that $f(n)$ is both $O(g(n))$ and $\Omega(g(n))$, that is, $f(n)$ is $\Theta (f(n))$.
If $f(n)$ is $\Theta (g(n))$, $f(n)$ is both $O(g(n))$ and $\Omega (g(n))$. As we have done above, this implies that $g(n)$ is both $O(f(n))$ and $\Omega(f(n))$, that is, $g(n)$ is $\Theta (g(n))$.
So, $f(n)$ is $\Theta(g(n))$ if and only if $g(n)$ is $\Theta(f(n))$.
3.10
Obviously, $g(n)$ is $O(n^k)$. So, $g(n)$ is $O(n^l)$ for any $l\le k$.
3.11
When n=1,
$$
\begin{equation}
\log n = 0,\;\;\; n^k = 1.
\end{equation}
$$
The first derivative of $\log n$ and $n^k$
$$
\begin{align}
\frac{\mathrm{d}}{\mathrm{d}n} \log n &= \frac{n^{-1}}{\ln 2},\\
\frac{\mathrm{d}}{\mathrm{d}n} n^k &= kn^{k-1}.
\end{align}
$$
So, there always exist a constant c that makes the first derivative of $cn^k$ larger than that of $\log n$. Therefore, $\log n$ is $O(n^k)$ for any $k\gt 0$.
3.12
$n^k$ intersects with $n^{n\log n}$ only at $n_0=2^k$. The slopes of $n^k$ and $n^{n\log n}$ at $n_0$ are
$$
\begin{align}
\left. \frac{\mathrm{d}}{\mathrm{d}n} n^k \right| _{n_0} &= k2^{k(k-1)},\\
\left. \frac{\mathrm{d}}{\mathrm{d}n} n^{n\log n} \right| _{n_0} &= 2k2^{k(k-1)}.
\end{align}
$$
Therefore, $n^k$ is $O(n^{n\log n})$.
3.15
Every time we perform compare-and-swap, 2 of the possible initial orderings will be sorted into the correct order. So, after $k$ of the operations, at most $2^k$ initial orderings will be sorted. The number of operations needed to sort all possible initial orderings into the correct order k_0 is,
$$
\begin{align}
2^{k_0} &= n! \\
\longrightarrow k_0 &\approx n\log n - n = O(n\log n).
\end{align}
$$