===========================================================================
CSC 363H                        Exercise 2                        Fall 2007
===========================================================================

A.  Show that TMs with "stay put" head movement are equivalent to regular
    TMs.  Give a formal answer, i.e., given an arbitrary stay-put TM M =
    (Q,S,T,q_0,q_A,q_R,d), describe a TM M' = (Q',S',T',q_0',q_A',q_R',d')
    that performs an equivalent computation (define precisely each
    component of M' in terms of components of M), and give an argument that
    both machines are equivalent.  Then do the same thing in reverse (given
    an arbitrary regular TM M, define an equivalent stay-put TM M').

B.  For some alphabet S, say that a function f : S* -> S* is "computable"
    if there exists a TM M such that for all strings w in S*, M accepts w
    with final configuration q_accept f(w).  In other words, when M is
    started with w on its tape, it eventually enters its accepting state
    with only f(w) on the tape and its head on the leftmost symbol of f(w).

    Show that a function f is computable in this sense iff the language
        L_f = { w#f(w) : w in S* }
    is decidable (where # is a symbol that does not belong to S).