Computers and Reality - Cognitive Science 110 - Spring 2007

1. Suppose a Turing machine uses the symbol "1" only. Why do we represent the number n by a block of n+1 consecutive 1's instead of using just n 1's? (Hint: think about functions with more than one input, e.g., f(x,y) = x + y.)
2. Show that the function f(x) = x - 2 is Turing-computable. Pay attention to when the function is undefined and when the Turing machine doesn't stop. Use the convention in Problem 1 above.
3. Show that the predicate "x is divisible by 3" is Turing-decidable. Use the convention in Problem 1 above.