Computation Theory Supervision Work

Implement integer division, and (separately) pseudo-logarithm of base-2 (i.e. for any \(x\) the largest \(y\) such that \(2^y\leq x\)) in a register-machine program. [5 marks]

1. Explain how to code register machine programs \(P\) as numbers \(⌜P⌝ ∈ N\) so that each \(e ∈ N\) can be decoded to a unique register machine program \(\text{prog}(e)\). [10 marks]
2. Find a number \(e_1 ∈ N\) for which \(\text{prog}(e_1)\) is a register machine program for computing the function \(\text{one} ∈ N → N\) with \(\text{one}(x) = 1\) for all \(x ∈ N\). [2 marks]
3. Why is it important for the theory of computation that the functions involved in the coding and decoding given previously are themselves register machine computable? (You are not required to prove that they are computable.) [2 marks]

1. What does it mean for a register machine to be universal? [4 marks]
2. Define what it means for a partial function \(f ∈ N^n⇀N\) to be register machine computable. [3 marks]
3. Show that the following functions are register machine computable.
   1. The partial function \(f ∈ N⇀N\) that is everywhere undefined. [1 mark]
   2. \(k(x_1, x_2) = 1\) if the register machine program with index \(x_1\), when started with 0 in all registers, halts in at most \(x_2\) steps; and \(k(x_1, x_2) = 0\) otherwise. Note, you can use existing building blocks, and can outline it in words rather than giving the exact diagram. [4 marks]

1. Define what it means for a set of numbers \(S ⊆ N\) to be register machine decidable. Why are there only countably many such sets? Deduce the existence of a set of numbers that is not register machine decidable. (Any standard results that you use should be clearly stated.) [4 marks]
2. A set of numbers \(S ⊆ N\) is said to be computably enumerable if either it is empty or equal to \(\{f(x) | x ∈ N\}\) for some total function \(f : N → N\) that is register machine computable.
   1. Show that if \(S\) is register machine decidable, then it is computably enumerable. [Hint: consider separately the cases when \(S\) is, or is not empty.] [4 marks]
   2. Show that if both \(S\) and its complement \(\bar{S}=\{x ∈ N | x ∉ S\}\) are computably enumerable, then \(S\) is register machine decidable. [6 marks]
3. Let \(ϕ_e : N ⇀ N\) denote the partial function computed by the register machine with code \(e ∈ N\) and consider the set \(T = \{e ∈ N | ϕ_e\text{ is a total function}\}\).
   1. Suppose that \(f : N → N\) is a register machine computable total function such that \(f(x) ∈ T\) for all \(x ∈ N\). Define \(\hat{f}(x)\) to be \(ϕ_{f(x)}(x) + 1\). Show that \(\hat{f} = ϕ_e\) for some \(e ∈ T\). [3 marks]
   2. Deduce that T is not computably enumerable. [3 marks]

Consider a machine that has some byte-indexed memory, that is each memory cell contains a byte. Memory cells are numbered from zero. The operation of this machine is to read four consecutive 4-byte integers (big-endian), say Source, Destination, Size Next, and then copy the value at the memory cell indexed by Source until Source+Size (exclusive, i.e. Size=1 copies one cell) to Destination until Destination+Size (exclusive), then repeat but reading from location Next.

This machine always starts reading from location zero. The program for this machine is given by the contents of memory cells, with non-specified memory cells being zero, except memory locations specified as the input.

What would the following program do? Assume the input is at location 0xFC, and the output at 0xFD. Assume each memory cell holds one byte, and size is given in bytes. Blanks denote zero, they have been left out to increase legibility. Memory at 0x100 to 0x1FF holds increasing values. [3 marks]

Without proof (or perhaps only with a small sketch), do you think the above computation model (not just the program) is Turing complete? [2 marks]

While not a question as such, I feel that these belong to this course, if only for some amusement value. The first link has some liberal interpretations, e.g. overflow bugs in games.

• http://beza1e1.tuxen.de/articles/accidentally_turing_complete.html
• http://www.cl.cam.ac.uk/~sd601/papers/mov.pdf
• https://www.usenix.org/system/files/conference/woot15/woot15-paper-rushanan.pdf

Let \(S(M)\) denote the number of steps a Turing machine \(M\) takes before halting, when started with the empty tape.

Let \(S(s, Σ)\) denote the maximum number of steps any Turing machine with \(s\) states and \(Σ\) symbols (excluding \(▹\) but including \(␣\)) takes

Try coming up with a Turing machine, which is, or close to \(S(2, 2)\). To clarify, you don't have to search the whole space, that would be tedious. Just try one to get the hang of Turing machines. Show the steps it takes when started with an empty tape.

How fast do you think \(S(s, Σ)\) grows when \(s\) is changed while keeping \(Σ\) constant at \(Σ=2\)?

This is just a warm-up exercise to get you thinking about something we will discuss in more detail during the supervision, you don't need to look it up, but do think a bit.

1. Give a precise definition of the collection of partial recursive functions. You should define any functions, or constructions on partial functions that you use in your definition. [9 marks]
2. Explain why every partial function computable by a register machine is a partial recursive function. You may assume without proof the existence of suitable primitive recursive functions for manipulating numerical codes of register machine configurations so long as you state their properties precisely. [10 marks]
3. Explain why every partial recursive function is computable by a register machine? [10 marks]

Show that the following are all primitive recursive

1. Exponentiation \(\mathit{exp} ∈ N^2→N\) with \(\mathit{exp}(x,y)≜x^y\);
2. Truncated subtraction \(\mathit{sub}∈N^2→N\) with \[\mathit{sub}(x,y)≜ \begin{cases} x-y&\text{ if $x≥y$}\\ 0 &\text{ otherwise} \end{cases};\]
3. Conditional branch on zero \(\mathit{ifzero}∈N^3→N\) \[\mathit{ifzero}(x,y,z)≜\begin{cases} y &\text{ if } x=0 \\ z & \text{ if } x>0 \end{cases}\]
4. Bounded summation: if \(f∈N^{n+1}\) is primitive recursive, then so is \(g∈N^{n+1}→N\), where \[g(\vec x, x) ≜ \begin{cases} 0 & \text{ if } x=0 \\ f(\vec x, 0) & \text{ if } x=1 \\ f(\vec x, 0)+⋯+f(\vec x, x-1) & \text{ if } x>1 \end{cases}\]

1. Define what is a Turing machine and a Turing machine computation. [7 marks]
2. What is meant by a partial function from \(N^n\) to \(N\)? Define what it means for such a partial function to be Turing computable. [4 marks]
3. Describe the Church-Turing Thesis and some evidence for its truth. [4 marks]
4. Assuming the existence of a universal register machine, give an example, with justification, of a partial function that is not Turing computable. [5 marks]

1. Consider the following two partial functions \(S : N ⇀ N\) and \(T : N ⇀ N\) on the natural numbers.

   \[S(⌜P⌝) = \begin{cases} n &\text{ if the program $P$ when started with} \\ &\text{ 0 in all registers halts after $n$ steps}; \\ 0 &\text{ otherwise}. \end{cases}\]

   \[T(⌜P⌝) = \begin{cases} n &\text{ if the program $P$ when started with} \\ &\text{ 0 in all registers halts after $n$ steps}; \\ \mathit{undefined} &\text{ otherwise}. \end{cases}\]

   1. Which, if any, of \(S\) and \(T\) is register-machine computable and which is uncomputable? [4 marks]
   2. Give full justification for your answers above. State carefully any standard results that you use. [11 marks]

1. Define the terms \(M\) of the λ-calculus and the relation \(M =_β M_0\) of β-conversion between them. [6 marks]
2. For n ∈ N, what is the nth Church numeral? [2 marks]

3. Consider encoding a non-empty list of λ-terms \(M_1, M_2, . . . , M_n\) as the λ-term

   \[[M_1, M_2, …, M_n] ≜ λx, f . f M_1(f M_2 …(f M_n x)…)\]

   where the variables \(x\) and \(f\) do not occur free in \(M_1, M_2, …, M_n\). Give, with justification, λ-terms Iter, Cons, Append and Nil satisfying

   1. \(\mathit{Iter} M F [M_1, M_2, …, M_n] =_β F M_1 (F M_2 …(F M_n M))\) [2 marks]
   2. \(\mathit{Cons} M [M_1, M_2, …, M_n] =_β [M, M_1, M_2, …, M_n]\) [3 marks]
   3. \(\mathit{Append} [M_1, …, M_m] [N_1, …, N_n] =_β [M_1, …, M_m, N_1, …, N_n]\) [3 marks]
   4. \(\mathit{Cons} M Nil =_β [M], Iter M F Nil =_β M\) and \(\mathit{Append} Nil N =_β N\) [4 marks]

1. Give inductive definitions of the relations \(M → N\) and \(M ↠ N\) of single-step and many-step β-reduction between λ-terms \(M\) and \(N\). (You may assume the definition of α-conversion, \(M =_α N\).) [6 marks]
2. Turing’s fixed point combinator is the λ-term \(A A\) where \(A = λx.λy.y(x x y)\). Use it to show that given any λ-term \(M\), there is a λ-term \(X\) satisfying \(X ↠ M X\). [2 marks]
3. The sequence of λ-terms \(⌜0⌝, ⌜1⌝, ⌜2⌝, …\) is defined by \(⌜0⌝ = λx,f. x\) and \(⌜n+1⌝ = λx,f. f ⌜n⌝\). Say that a function \(f ∈ N^k→N\) is Scott definable if there is a λ-term \(F\) satisfying that \(F  ⌜n_1⌝ ⋯ ⌜n_k⌝ ↠ ⌜f(n_1,...,n_k)⌝\) for all \((n_1, …, n_k)∈N^k\).
   1. Show that the successor function , \(\text{succ}(n) = n + 1\), is Scott definable. [2 marks]

   2. Show that for any λ-terms \(M\) and \(N\), we have \(⌜0⌝ M N ↠ M\) and \(⌜n+1⌝ M N↠N ⌜n⌝\). Deduce that the predecessor function

      \[\text{pred}(n) = \begin{cases}0 &\text{ if } n = 0 \\ n − 1 &\text{ if }n > 0 \end{cases}\]

      is Scott definable. [2 marks]

   3. By considering the λ-terms \(P_m=A A (λf.λy. y ⌜m⌝ (λz. S (f z)))\) for a suitable choice of \(S\), or otherwise, prove that the addition function \(\text{plus}(m,n)=m+n\) is Scott definable. [8 marks]

1. 1. What does it mean for a λ-term to be a β-normal form? Defining the sets of canonical (\(C\)) and neutral (\(U\)) λ-terms by the grammar

      \begin{align*} C ::=& λx. C \ |\ U \\ U ::=& x \ |\ U C \end{align*}

      show that a λ-term is a β-normal form if and only if it is canonical. [5 marks]

   2. Carefully stating any standard properties of β-reduction, explain why a λ-term reduces to at most one β-normal form (up to α-equivalence). [4 marks]
   3. Give an example of a λ-term that does not reduce to any β-normal form. [2 marks]
2. 1. Define what it means for a closed λ-term \(F\) to represent a partial function \(f ∈ N⇀N\). [4 marks]

   2. The composition of partial functions \(f, g ∈ N⇀N\) is the partial function

      \[g ∘ f = \{(x, z) | ∃y. (x, y) ∈ f ∧ (y, z) ∈ g\} ∈ N⇀N.\]

      Suppose \(F\) represents \(f\), \(G\) represents \(g\), and \(f\) and \(g\) are totally defined. Show that \(λx. G (F x)\) represents \(g ◦ f\). [2 marks]

   3. Give an example to show that \(λx. G (F x)\) need not represent \(g∘f\) when \(f\) and \(g\) are not totally defined. [3 marks]

Give a definition of a function that is λ-definable but not primitive recursive. [2 marks]