Quiz 1 for the course

CS 5315, Spring 2013

Name: _____________________________________________________

1. Describe the function f = σ(PR(σ,
π^{3}_{2})) 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., 6_{10} = 110_{2} is written
as # 1 1 0 # # ...)