1. The Successor Function
Show that the successor function f(n) = n + 1 is Turing Machine computable. (Hint: This is super easy. Two states are all you require. 10pts)
2. The Predecessor Function
You've shown the successor function f(n) = n + 1 Turing Machine computable, above. 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. (10pts)
3. 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. Notice that input for this function will be given by two strings of n-x's separated by a single blank. (10)
f(n) = n + n
4. Meat Computers
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) jointly lend credence to the view that we might one day be able to meet (iii). (20pts)
5. The Ugly Doubler (Extra Credit)
As we suggested in class, it can be shown that if a function is TM-computable, then that there are countably infinitely many Turing Machines that compute it. To see this, start with the flow-graphs for the two TM's we gave in class to compute binary addition. Now add in however many superfluous states you see fit to see how the previous claim might be true.
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, n>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! (10)