Homework Exercise 1

Due: by 6pm on Wed 16 Jan
Worth: 1.5%

  1. Give an example of a Turing Machine that never halts (i.e. for all inputs, the TM never enters its accepting or rejecting state), a separate example of a Turing Machine that always accepts (i.e., the TM accepts every input), and a separate example of a Turing Machine that always rejects (i.e., the TM rejects every input). Give formal descriptions for all your TMs.

  2. Let M be the TM with input alphabet Σ = {a,b}, tape alphabet Γ = {a,b,_}, and transition function given by the following table (where q0 is the initial state, qA is the accepting state, qR is the rejecting state, and square brackets [] have been put around "superfluous" transitions — transitions that will never be encountered because of the design of the TM, and that are specified only for the sake of completeness):

    a b _
    q0 q1,_,R q4,_,R qA,_,R
    q1 q2,a,R q2,b,R qR,_,R
    q2 q2,a,R q2,b,R q3,_,L
    q3 q7,_,L qR,_,L [q3,_,L]
    q4 q5,a,R q5,b,R qR,_,R
    q5 q5,a,R q5,b,R q6,_,L
    q6 qR,_,L q7,_,L [q6,_,L]
    q7 q7,a,L q7,b,L q0,_,R

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

    1. ε (the empty string)
    2. a
    3. aa
    4. aba
    5. abbbaba

  3. Let M be a Turing Machine with accepting state qA and rejecting state qR, and let M' be a Turing Machine identical to M except that qR is the accepting state of M' and qA 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')?