• Site Map

• Lectures

• Homework

• Tests/Exam

• Main Webpage

Homework Exercise 2

Due: by 2pm on Web 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₀ _w" (where q₀ is the initial state),
• the transition function δ(q,a) may be undefined for some values of q ∈ Q and a ∈ Γ.

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₀ ∈ Q
• a fixed, finite, non-empty set of input symbols Σ, with _ ∉ Σ
• a fixed, finite, non-empty set of tape symbols Γ, with _ ∈ Γ, Σ ⊆ Γ
• a transition fuction δ : Q × Γ → Q × Γ × {L,R}.

On input w ∈ Σ*, an ITM computes as follows: starting from initial configuration C₀ = "q₀ _w", go from configuration to configuration following the transition function (i.e., C₀ yields C₁ yields C₂ yields ...). More precisely, for all states q_i,q_j ∈ Q, symbols a,b,c ∈ Γ, and strings u,v ∈ Γ*:

• if δ(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 δ(q_i,a) = (q_j,b,L), then configuration "uc q_i av" yields configuration "u q_j cbv" in one step of computation, and configuration "q_i av" makes the ITM reject w;
• if δ(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.)