0
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ Welcome to cs.SE! We discourage "please check my answer" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$ – Raphael Jan 11 '18 at 11:49
  • $\begingroup$ Thank you for the suggestions! I just edit the question, I hope it's going better. Please let me know if I have to rephrase it! $\endgroup$ – ocram Jan 11 '18 at 20:12
  • $\begingroup$ My personal opinion is tha the best way to solve such exercises is to convince your teacher that, even though such exercises are a wonderful source of exam questions that make your teacher's life easy, they should be kept to a minimum. Time is better spent learning a humane programming language, or designing circuits in a high-level language, and how such languages are equivalent to Turing machines (or maybe implementing a compiler to Turing machines). $\endgroup$ – Andrej Bauer Jul 11 '18 at 7:57
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ A programming problem in which you have to use your nose to press the keys on the keyboard, and you need a really long toungue to get the upper-case letters. $\endgroup$ – Andrej Bauer Jul 11 '18 at 7:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.