Problem Set 02

1. The Predecessor Function

We've already shown the successor function f(n) = n + 1 Turing Machine computable in class. Now consider the following function:

f(n) = n - 1, for all natural numbers n > 1.

Show that f is Turing Machine Computable by constructing a Turing Machine that computes it--i.e., give a flow graph of the instruction set to solve the function for any such n. (10)

2. The Easy Doubler

Show that the following function is Turing Machine Computable by constructing a Turing Machine that computes it--i.e., give a flow graph of the instruction set to solve the function for non-zero natural numbers n. (10)

f(n) = n + n

[Hint: Recall the flow graph we gave to show binary addition--f(n,m) = n + m, n,m > 0--in class Turing Machine computable.]

3. Meat Machines

In a long essay, explain to someone not in the class i) the concept of the Universal Turing Machine, ii) the Church-Turing Thesis, and iii) Dretske's Dictum in such a way as to explain just how (i) and (ii) combine to lend credence to the view that we might one day be able to meet (iii).

4. The Ugly Doubler (Extra Credit)

Turing's Theorem--that there exists a Turing Machine that can compute any function computable by any Turing Machine--demonstrates that for any given Turing Machine computable function there are at least two Turing Machine's that compute it. Indeed, we can prove that there are countably infinitely many Turing Machines that compute any Turing Machine computable function.

Of any two Turing Machines TM-1 and TM-2 that compute the same function, let us say that TM-1 is more elegant than TM-2 iff TM-1 requires fewer states in its flow-graph than TM-2. We might add that TM-2 is uglier than TM-1 if it requires more states to do the same thing.

The Ugly Doubler (pdf) is ugly indeed. It requires a total of 17 states to compute the function f(n)=2n, x>0. Write the flow graph of a less ugly Turing Machine that computes the same function. Note that some of the states are obviously eliminable, while more dramatic cuts might be made by reconsidering the basic strategy. The most elegant solution (a mere 6 states!) of the problem I've yet seen is the Ariel McCree Solution:

Whatever your solution, be sure to run your Turing Machine on limiting input (n=1) as well as other test cases (n=3, say) to check whether it works in general! (20)