Turing machine to solve a^(0+1+2+3+....+n)

user_13587169 0
Viewed 50

Can anyone give me some insight how that Turing machine can be implemented?

L = Xa^n       n >= 0 and n = 0 + 1 + 2 + 3 +....+ M

accepted examples: Xa ->(0+1)       Xaaa -> (0+1+2)  Xaaaaaa (0+1+2+3) etc.

I couldn't find any source on the internet.

First, I have to turn one A to Y (I picked Y, nothing special about it)

Secondly I have to turn two A into Y's (This is where I get stuck)

How do we find how many A's will be converted into Y's

automata turing-machines
1 Answers

If you can use a two-tape TM, this strategy is pretty easy:

  1. if the input tape is empty (tape head sees X), halt-accept.
  2. otherwise, add an a to the scratch tape and reset its head to the first a.
  3. move both heads to the right
  4. if the scratch tape head sees X and the input tape head sees X, halt-accept
  5. if the input tape head sees X but the scratch tape head doesn't, halt-reject
  6. otherwise, if the scratch tape head sees X but the input tape head sees a, add an a to the scratch tape, reset its head, and continue from step 3

Example of the two-tape solution running on a simple case of 0+1+2:

Xaaa    Xaaa    Xaaa    Xaaa    Xaaa    XaaaX
 ^   =>  ^   =>   ^  =>   ^  =>    ^ =>     ^ => halt_accept
XX      Xa      XaX     Xaa     Xaa     XaaX
 ^       ^        ^      ^        ^        ^

It seems like a single-tape solution might be a bit harder here. I suppose you could just go to the end of the tape and use that as your "scratch" area. So instead of having a 2-tape solution as above, you'd have a single-tape solution where your tape had both sections. To make that work you'd need to update your scratch to remember where you left off, and then bounce back and forth. The tapes might look like

Xaaa
Xaaabc
Xdaabe
Xdaabcc
Xddabec
Xdddbcc => halt-accept

Note that I am not showing every transition in either case. There will be a lot of transitions that just move the tape head around looking for something; I have collapsed those so that it moves to what it's looking for.

user_8472690
Related