COSC 418/CPMA 584: Formal Languages and Automata
Homework #6
Due: 11/29/18
Points: 80(100)
- Give a RAM program (in shorthand form) that computes exp(x,y).
- Write a primitive recursive definition (not a mu-recursive definition) of the Fibonacci function, fib, where fib(0) = 1, fib(1) = 1, fib(2) = 2, fib(3) = 5, and so on. You may use primitive recursive, definition by cases, and the primitive recursive functions and predicates from class in your answer.
- Show that bounded quantification, that is, a function of the form ∃i < n P(i), where P is a primitive recursive predicate, is primitive recursive. That is, it does not require unbounded quantification, i.e.,
mu-recursion.
- Give a grammar that generates the language {ww | w ∈ {a,b}*}.
- Can the Universal Turing machine simulate the Universal Turing machine? Justify your answer.
- Create a standard Turing machine that always halts and that takes at least 2n steps before it halts, given an input of size n.
- Why is the Church-Turing Thesis a thesis, and not a theorem?
- (CPMA 584) (20 points) Suppose that f is a mu-recursive bijection from N to N. Show that its inverse f-1 is also mu-recursive.
Last modified: Oct. 22, 2018
Dr. Donald L. Simon, simon@mathcs.duq.edu