Computeability/5.org

Assignment 5

In order to pass this assignment you have to get at least four points.

(2p)

Let NN be the set containing all closed expressions $e$ that implement functions from $\mathbb{N}$ to $\mathbb{N}$, i.e. expressions $e$ that, for some function $f \in \mathbb{N} \rightarrow \mathbb{N}$, satisfy $\forall n \in \mathbb{N}. \llbracket e\ \ulcorner n \urcorner \rrbracket = \ulcorner f\ n \urcorner$.

Either prove that the following function is $\chi$ computable, or that it is not $\chi$ computable: \[ \text{has-fixpoint} \in \text{NN} \rightarrow \mathbb{B} \] \[ \text{has-fixpoint}\ e = \text{if}\ \exists n \in \mathbb{N}. \llbracket e\ \ulcorner n \urcorner \rrbracket = \ulcorner n \urcorner\ \text{then}\ true\ \text{else}\ false \]

Note that Rice’s theorem, as stated in a lecture, applies to (total) functions from CExp to Bool, whereas has-fixpoint is a function from NN to Bool.

Answer

Assume that $\text{has-fixpoint}$ is $\chi$ computable. Then there exists an expression $\underline{\text{has-fixpoint}}$ that implements this function, i.e. $\llbracket \underline{\text{has-fixpoint}}\ \ulcorner p \urcorner \rrbracket = \ulcorner \text{has-fixpoint}(p) \urcorner$. With this, lets reduce it to the halting problem. We do this by defining it as the following: \[ halts = \lambda e. \underline{\text{has-fixpoint}}\ \ulcorner \lambda n. ((\lambda \_. n) \llcorner e \lrcorner) \urcorner \]

Which means

\begin{align*} \llbracket halts\ \ulcorner p \urcorner \rrbracket &= \llbracket \underline{\text{has-fixpoint}}\ \ulcorner \lambda n. ((\lambda \_. n) \llcorner \ulcorner p \urcorner \lrcorner) \urcorner \rrbracket \\ &= \llbracket \underline{\text{has-fixpoint}}\ \ulcorner \lambda n. ((\lambda \_. n)\ p) \urcorner \rrbracket \\ &= \ulcorner \text{has-fixpoint}(\lambda n. ((\lambda \_. n)\ p)) \urcorner \\ &= \begin{cases} \ulcorner \text{true} \urcorner &\quad \text{if}\ \exists v \in Exp. \llbracket p \rrbracket = v\ \text{(due to strictness in application)},\\ \ulcorner \text{false} \urcorner &\quad otherwise \end{cases} \end{align*}

Since the halting problem could be reduced to $\text{has-fixpoint}$, then $\text{has-fixpoint}$ is not $\chi$ computable.

(1p)

When is a function $f \in \mathbb{N} \rightarrow \mathbb{N}$ Turing-computable?

Answer

Given that we have a way of representing elements of $\mathbb{N}$ as elements of $\text{List}\ \Sigma$, where $\Sigma$ is the input alphabet of the turing machine. This can be used with the alphabet $\{0,1\}$, and represent a natural number $n$ as $1^n0$ (n ones followed by a single zero).

Then, a function $f \in \mathbb{N} \rightarrow \mathbb{N}$ would be turing computable if there is a turing machine $tm$ that satisfies the following conditions:

• $\Sigma_{tm} = \Sigma$
• $\forall n \in \mathbb{N}. \llbracket tm \rrbracket \ulcorner a \urcorner = \ulcorner f\ a \urcorner$

This means that the alphabet is the same, and that for any $n$, then the turing machine applied to the representation of $n$ should be the same as the represention of the function $f$ on $n$.

(1p)

The following Turing machine implements a (total) function on the natural numbers. Which one? The natural number $n$ is represented by $1^n0$ (n ones followed by a single zero).

• Input alphabet: $\{0, 1\}$.
• Tape alphabet: $\{0, 1, \text{\textvisiblespace} \}$.
• States: $\{s_0, s_1, s_2\}$.
• Initial state: $s_0$.

• Transition function:

  • $\delta (s_0, 1) = (s_0, 1, R)$
  • $\delta (s_0, 0) = (s_1, 1, R)$
  • $\delta (s_1, \text{\textvisiblespace}) = (s_2, 0, R)$

Answer

It describes the successor function on natural numbers.

(2p)

Implement a Turing machine (with accepting states) that checks if two natural numbers are equal. The machine should use $\{0, 1\}$ as the input alphabet; you may use more symbols in the tape alphabet. The machine should accept input of the form $1^n01^n0$ (for any $n \in \mathbb{N}$). Input of the form $1^m01^n0$ where $m \ne n$ should be rejected.

Explain how your Turing machine works.

Make sure that you specify the Turing machine completely (the set of states, the alphabets, and so on). In addition to this specification you can also optionally submit your Turing machine in the format used by Anthony Morphett's Turing machine simulator. (If you go to “Advanced options”, then you can choose to use semi-infinite tapes.)

Answer

We define the following as our turing machine.

\[ S = \{\text{DelR}, \text{Move1}, \text{Head2}, \text{Move2}, \text{Move2'}, \text{Find0}, \text{Accept} \} \] \[ s_0 = \text{DelR} \] \[ A = \{\text{Accept}\} \] \[ \Sigma = \{ 0, 1\} \] \[ \Gamma = \{ 0 , 1, \text{\textvisiblespace} \}\]

and the following as our transition function.

\begin{alignat*}{2} &δ (\text{DelR}, 0) &&= (\text{Find0}, \text{\textvisiblespace}, R)
&δ (\text{DelR}, 1) &&= (\text{Move1}, \text{\textvisiblespace}, R)
&δ (\text{Move1}, 0) &&= (\text{Head2}, 0, R)
&δ (\text{Move1}, 1) &&= (\text{Move1}, 1, R)
&δ (\text{Head2}, 1) &&= (\text{Move2}, \text{\textvisiblespace}, L)
&δ (\text{Head2}, \text{\textvisiblespace}) &&= (\text{Head2}, \text{\textvisiblespace}, R)
&δ (\text{Move2}, 0) &&= (\text{Move2'}, 0, L)
&δ (\text{Move2}, \text{\textvisiblespace}) &&= (\text{Move2}, \text{\textvisiblespace}, l)
&δ (\text{Move2'}, 1) &&= (\text{Move2'}, 1, L)
&δ (\text{Move2'}, \text{\textvisiblespace}) &&= (\text{DelR}, \text{\textvisiblespace}, R)
&δ (\text{Find0}, \text{\textvisiblespace}) &&= (\text{Find0}, \text{\textvisiblespace}, R)
&δ (\text{Find0}, 0) &&= (\text{Accept}, \text{\textvisiblespace}, L) \\

\end{alignat*}

With these definitions, we have a turing machine that will find if two natural numbers are equal for the given representation. I made the program for this below for easy testing on Anthony Morphett's Turing machine simulator.

DelR 0 _ r Find0
DelR 1 _ r Move1

Move1 0 0 r Head2
Move1 1 1 r Move1

Head2 1 _ l Move2
Head2 _ _ r Head2

Move2 0 0 l Move2'
Move2 _ _ l Move2

Move2' 1 1 l Move2'
Move2' _ _ r DelR

Find0 _ _ r Find0
Find0 0 _ l Accept

Accept _ _ l halt-accept
Accept 0 _ l halt-accept
Accept 1 _ l halt-accept

(2p)

Give a formal definition of (a reasonable variant of) two-tape Turing machines. Explain how such a Turing machine is defined. Also explain what its semantics is: what partial function from strings to strings does it compute?

Answer

Let a two-tape Turing machine be defined by the following:

• $S$: A finite set of states
• $s_0 \in S$: An initial state
• $\Sigma$: The input alphabet, which is a finite set of symbols with $\text{\textvisiblespace} \notin \Sigma$
• $\Gamma$: The tape alphabet, which is a finite set of symbols such that $\Sigma \cup \{\text{\textvisiblespace}\} \subseteq \Gamma$
• $\delta \in S \times \Gamma \times \Gamma \rightharpoonup S \times (\Gamma \times \{L,R\}) \times (\Gamma \times \{L,R\})$: The transition "function", which has the pair of tapes used.

\begin{prooftree} \alwaysNoLine \AxiomC{$S$ is a finite set} \UnaryInfC{$s_0 \in S$} \AxiomC{$\Sigma$ is a finite set} \UnaryInfC{$\text{\textvisiblespace} \notin \Sigma$} \AxiomC{$\Gamma$ is a finite set} \UnaryInfC{$\Sigma \cup \{\text{\textvisiblespace}\} \subseteq \Gamma$} \AxiomC{$\delta \in S \times \Gamma \times \Gamma \rightharpoonup$} \UnaryInfC{$S \times (\Gamma \times \{L,R\}) \times (\Gamma \times \{L,R\})$} \alwaysSingleLine \QuaternaryInfC{$(S,s_0, \Sigma, \Gamma, \delta) \in \text{TM2}$} \end{prooftree}

With all of these, one has a two tape turing machine. Utilizing the functions on Tapes from the lectures, one can define the small step operational semantics as follows:

\begin{prooftree} \AxiomC{$\delta (s, \text{head}_T\ t, \text{head}_T\ t') = (s', a, a')$} \UnaryInfC{$(s,t,t') \rightarrow (s', \text{act}\ a\ t, \text{act}\ a'\ t') $} \end{prooftree}

And the result of running the turing machine, with the two inputs $xs$ and $ys$, would be defined by (using remove as defined from the lectures):

\begin{prooftree} \AxiomC{$(s_0, ([], xs), ([],ys)) \rightarrow^{*} (s,t,t')$} \AxiomC{$\nexists c. (s, t, t') \rightarrow c$} \BinaryInfC{$(xs,ys) \Downarrow (\text{remove}\ (\text{list}\ t), \text{remove}\ (\text{list}\ t'))$} \end{prooftree}

The semantics would be given as a partial function by:

\begin{align*} &\llbracket \_ \rrbracket \in \forall tm \in \text{TM2}.\ \text{List}\ \Sigma_{tm} \times \text{List}\ \Sigma_{tm }\rightharpoonup \text{List}\ \Gamma_{tm} \times \text{List}\ \Gamma_{tm} \\ &\llbracket tm \rrbracket\ (xs,ys) = (us,ws)\ \text{if}\ (xs,ys) \Downarrow_{tm} (us,ws) \end{align*}

(2p)

Consider the following variant of the basic Turing machines (without accepting states) presented in the lectures:

• There are three possible directions: $\{L, R, S\}$. $S$ means "stay" (do not move the head).
• The meaning of S is specified formally by extending move with another clause: \[ \text{move}\ S\ t\ = t \]

Give a translation remove-stay that takes Turing machines of this kind to Turing machines of the basic kind. The translation should satisfy the following property for every Turing machine tm of the extended kind:

• For every input $xs$ and output $ys$, the result of running $tm$ on $xs$ is $ys$ if and only if the result of running remove-stay tm on $xs$ is $ys$.

You do not have to prove formally that this property holds.

Hint: You can handle the non-moving actions by first moving the head to the right, and then back to the left, using extra states to program this movement.

Answer

The semantics of remove-stay should be implemented by the following: For all states $m \in S$, and forall $x \in \Gamma$, add the following to the transition function: \[ \delta (\text{Stay}_m, x) = (m, x, L) \] In transition function, where a definition has the output direction as $S$, i.e. \[ \delta(n, x) = (m, y, S) \] replace that by the following: \[ \delta(n, x) = (\text{Stay}_m, y, R) \]