Homework 2

Problem 1.

Remember from the class that we can create pairs of Church numerals using the following combinators:
\begin{align*} \mathrm{pair} & = \lambda xy f. fxy\\ \mathrm{first} & = \lambda p.pT\\ \mathrm{second} & = \lambda p.pF \end{align*}

Write a combinator for the predecessor function, that is

\[ \mathrm{pred} \; \overline{n} = \overline{n-1} \]
for \(n > 0\) (and \(\mathrm{pred} \;\overline{0} = \overline{0}\)).

Hint: Write a combinator \(\Phi\) that maps the pair \((i,j)\) to \((j, j+1)\). What happens when you appy \(\Phi\) \(n\) times to \((0,0)\)?

Problem 2.

Using the same idea as in the previous problem, write a \(\lambda\)-expression to compute \(n!\) without using the Y-combinator.

Problem 3.

Generalize the solution from the previous two problems to show the following: If \(f\) and \(g\) are \(\lambda\)-definable, so is the function \(h\) defined from them using primitive recursion.

Can you write a combinator \(\mathrm{primrec}\) that allows you to define \(h\) like this?

\[ h = \mathrm{primrec} \; f \; g \]

Problem 4.

Consider the combinator \(T = T_{1} T_{2}\), where
\begin{align*} T_{1} & = \lambda xy.xyx\\ T_{2} & = \lambda yx.y(xyx) \end{align*}
Show that \(T\) is a fixed-point combinator: For any combinator \(R\), show that \(T R = R (T R)\).

Problem 5.

Consider the following automaton: It has a finite set \(S\) of states, and access to \(k\) stacks. At each step, it can update its internal state, and push or pop a symbol on each stack. It chooses its actions based on its state, and on the symbol on top of each stack, and whether or not the stack is empty.

The input is given by pushing a string on one stack. The output is read by reading it from another stack when the machine halts.

Show that if \(k \geq 2\), such an automaton can simulate a Turing machine, and is therefore computationally universal.

Problem 6.

Design a counter machine with two different HALT states, called YES and NO. The input is given in counter \(x\). If \(x\) is a power of 2, then the machine must halt in the YES state, and another counter \(y\) must have the value \(\log_{2}\). If \(x\) is not a power of 2, then the machine must halt in the NO state.

Problem 7.

Write a FRACTRAN program that, given the initial value \(n = 2^{k}\), halts if \(k\) is a power of two (so in this case \(n = 2^k = 2^{2^{t}}\)), and falls into an infinite loop otherwise.

Hint: You can arrange an infinite loop by putting a pair of fractions \(p/q\), \(q/p\) at the head of the program.