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.