===========================================================================
CSC 363                     Homework Exercise 2                   Fall 2008
===========================================================================

Due: by 2pm on Wed 24 Sep
Worth: 1.5%

For each question, please write up detailed answers carefully: make sure
that you use notation and terminology correctly, and that you explain and
justify what you are doing.  Marks *will* be deducted for incorrect or
ambiguous use of notation and terminology, and for making incorrect,
unjustified, ambiguous, or vague claims in your solutions.


An "Implicit Turing Machine" (ITM) is similar to a TM except that
 -  there are no halting states (q_A,q_R),
 -  the initial configuration for any input string w is always "q_0 _w"
    (where q_0 is the initial state),
 -  the transition function \delta(q,a) may be undefined for some values of
    q (- Q and a (- \Gamma.
The computation of an ITM on input sring w proceeds similarly to the
computation of a TM, except that:
 -  the ITM rejects if it ever moves left while on the leftmost square,
 -  the ITM accepts if it ever reaches a configuration where the transition
    function is undefined
(this is why an ITM does not need explicit accept/reject states: those
conditions are defined implicitly, based on certain behaviours).

Formally, an ITM consists of:
 -  a fixed, finite, non-empty set of states Q
 -  an initial state q_0 (- Q
 -  a fixed, finite, non-empty set of input symbols \Sigma,
    with _ !(- \Sigma
 -  a fixed, finite, non-empty set of tape symbols \Gamma,
    with _ (- \Gamma, \Sigma (_ \Gamma
 -  a transition fuction \delta : Q x \Gamma -> Q x \Gamma x {L,R}.

On input w (- \Sigma*, an ITM computes as follows: starting from initial
configuration C_0 = "q_0 _w", go from configuration to configuration
following the transition function (i.e., C_0 yields C_1 yields C_2 yields
...).  More precisely, for all states q_i,q_j (- Q, symbols a,b,c (-
\Gamma, and strings u,v (- \Gamma*:
 -  if \delta(q_i,a) = (q_j,b,R), then configuration "u q_i av" yields
    configuration "ub q_j v" in one step of computation;
 -  if \delta(q_i,a) = (q_j,b,L), then configuration "uc q_i av" yields
    "u q_j cbv" in one step of computation, and configuration "q_i av"
    makes the ITM reject w;
 -  if \delta(q_i,a) is undefined, then configuratin "u q_i av" makes
    the ITM accept w.


1.  Prove that ITMs are equivalent to TMs.  Give formal-level descriptions,
    including comments to explain the purpose of each part of your
    transition functions.  Also, briefly explain why your simulators have
    the same behaviour as the machine they are simulating.
    (See the "example of TM equivalence" posted on the course website for a
    detailed example of the type of argument expected.)