Theory of Computations,
Quiz 1 for the course
CS 5315, Spring 2013

Name: _____________________________________________________

1. Describe the function f = σ(PR(σ, π32)) in normal terms. For this function f, what is the value f(6, 4)?

11. Design a Turing machine that computes a function f(n) = 2n in binary code (the number n is written starting with its highest bit; e.g., 610 = 1102 is written as # 1 1 0 # # ...)