CODEWITHSUNDEEP
automataturing-machines
Loren Beer
Loren Beer

Reputation: 11

Why is this Turing Machine not a decider?

Like I get that a Turing Machine is a decider if it halts for every input. But for this question, it just gave me this diagram and asked me to deduce whether this Turing Machine was considered a decider or not and the answer was no. How was 'no' deduced? I can't seem to wrap my head around this whole decider and non-decider Turing Machine thing. If anyone could help explain this to me. Thanks. Turing Machine diagram

Upvotes: 0

Views: 244

Answers (1)

cherrywoods
cherrywoods

Reputation: 1361

If I am getting this right, then if I write "ba" on the tape and start the Turing machine with the head located at "b", then it will loop forever.

  • Starting at position 0 in state 0.
  • Read "b", replace "b" by "b", go right to position 1, move to state 1
  • Read "a", replace "a" by "a", go left to position 0, move to state 0
  • Read "b", replace "b" by "b", go right to position 1, move to state 1
  • Read "a", replace "a" by "a", go left to position 0, move to state 0
  • Read "b", replace "b" by "b", go right to position 1, move to state 1
  • Read "a", replace "a" by "a", go left to position 0, move to state 0
  • ...

You can see that this will loop forever. Because there is an input for which the Turning machine doesn't halt, it's not a decider.

Upvotes: 3

Related Questions