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.