Turing Computable Functions
Exercise 1 (Turing Computable Functions) Construct a single-tape deterministic TM TM1 such that computes the function
even(e) = 1, if e is even;
0, otherwise.
1. Explain the operation of TM1 in natural language.
2. Provide a state diagram for TM1.
3. State and justify the worst-case complexity of TM1.
Exercise 2 (Composition of Functions)
Let f, g be functions over N. Provide a state diagram for a k-tape Turing Machine that computes
the functions:
1. f(n) = 3n + 2
2. f(n1, n2, . . . , nk) = n1 + n2 + . . . + nk
3. Let f(n) = 3n, g(n) = n + 2. Provide the state diagram for f ◦ g(n).
Exercise 3 (Sequential Operation of TMs)
1. Draw the start and stop configuration for the CPYk macro.
2. Draw the start and stop configuration for the CPYk,i macro.
3. Using the macros defined in the script, implement the projection function pi(k). That is, for a k arguments n1 . . . nk, output exactly ni.
4. Using the macros defined in the script implement the Turing Machine constructed in Exercise 2.2.
Exercise 4 (Uncomputable Functions)
Let F be the set consisting of all total unary number-theoretic functions that satisfy f(i) = i, where i = 2k, k ∈ N. Prove that there are functions in F that are not Turing computable.