Homework Exercise 1

Give an example of a Turing Machine that never halts, a separate example of a Turing Machine that always accepts, and a separate example of a Turing Machine that always rejects. (Give formal descriptions for all your TMs.)

Let M be the TM with input alphabet Σ = {a,b}, tape alphabet Γ = {a,b,_}, and transition function given by the following table (where q₀ is the initial state, q_A is the accepting state and q_R is the rejecting state.

	`a`	`b`	_
`q`₀	`q`₁,_,R	`q`₄,_,R	`q_A`,_,R
`q`₁	`q`₂,`a`,R	`q`₂,`b`,R	`q_R`,_,R
`q`₂	`q`₂,`a`,R	`q`₂,`b`,R	`q`₃,_,L
`q`₃	`q`₇,_,L	`q_R`,_,L	`q`₃,_,L
`q`₄	`q`₅,`a`,R	`q`₅,`b`,R	`q_R`,_,R
`q`₅	`q`₅,`a`,R	`q`₅,`b`,R	`q`₆,_,L
`q`₆	`q_R`,_,L	`q`₇,_,L	`q`₆,_,L
`q`₇	`q`₇,`a`,L	`q`₇,`b`,L	`q`₀,_,R

Give the sequence of configurations in the computation of M on each input string below.

ε (the empty string)
a
aa
aba
abbbaba

Let M be a Turing Machine with accepting state q_A and rejecting state q_R, and let M' be a Turing Machine identical to M except that q_R is the accepting state of M' and q_A is the rejecting state of M'. Recall that the language recognized by M is defined as: L(M) = { w ∈ Σ^* : M accepts input string w }, i.e., for all input strings w ∈ Σ^*, w ∈ L(M) if M accepts w, and w ∉ L(M) if M rejects w or M loops on w.
1. What can you say about L(M'), the language recognized by M', compared to L(M), the language recognized by M?
2. If M always halts (i.e., M either accepts or rejects for every input, or equivalently, M never loops on any input), can you say that M' always halt?
3. If M always halts, what is the relationship between L(M) and L(M')?