Which is the best approach to solve Turing machines exercises?

Question

I've this exercise of which I'm not very sure about my solution.

Exercise:

Define the transition table about a Turing Machine that accepts words
  on the {a, b} alphabet where each a is followed by only two b.

My proposed solution is:

(f stands for transition function)

f(q0, a) = (a, q1, R)
f(q0, b) = HALT
f(q1, a) = HALT
f(q1, b) = (b, q2, R)
f(q2, a) = HALT
f(q2, b) = ACCEPT

I came up with this after thinking in the same way as finite state machines, even if I know are different with respect to Turing Machines (no tape, no reading/writing symbols and no right/left moves).

So, my question is, which is the best way of reasoning when I have to solve these kinds of problems?

Thank for your attention!

Andres · Answer

Understanding de problem: the statement says "where each a is followed by only two b", so I suppose any string of the form (abb)* is valid.
This is a Regular Language, so you can make a Turing Machines that works exactly like a Finite Automaton. No need to go Left, no need to replace any symbol, no need to use extra slots.
To design a TM for a more complex language, you need to define an strategy first. How are you going to mark slots and to go left and right to solve your problem? Of Course, this could be not trivial.

David Richerby · Answer

There isn't really a "best way of reasoning". Mathematical proof is essentially a creative act and there isn't a straightforward recipe you can follow. I usually find it helps to treat Turing machine construction as a programming problem, which is basically what it is.

Answered by David Richerby on November 17, 2021

Which is the best approach to solve Turing machines exercises?

2 Answers

Add your own answers!

Ask a Question