CS 5315 Homework #7

Date Assigned: Tuesday, February 8, 2005

Due Date: Thursday, February 10, 2005

Give an example of how, based on the two Turing machines that compute two functions f(n) and g(n), we can design a new Turing machine that computes the composition f(g(n)) of these two functions. Trace your example step-by-step on some input.