TransWikia.com

Which is the best approach to solve Turing machines exercises?

Computer Science Asked by ocram on November 17, 2021

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!

2 Answers

  1. 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.
  2. 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.
  3. 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.

Answered by Andres on November 17, 2021

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

Add your own answers!

Ask a Question

Get help from others!

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP