Why is this Turing Machine not a decider?

136 Views Asked by At

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

1

There are 1 best solutions below

0
cherrywoods On

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.