[Math] Designing a Turing machine for $a^n$ $b^{2n}$ $a^n$

automataturing-machines

I am new to theory of automata, and i have a little knowledge of designing a turing machine,
I am stuck in this question which is given to us as an assignment,

$\{$$a^n$ $b^{2n}$ $a^n$ : $n\geq0$$\}$ over $\{a,b\}$

what I want from you all is that please help me understand the problem, I don't want anyone to solve it for me because I want to do it myself, I just need a little help to design a turing machine for this problem. Thanks

Best Answer

You can move the head right until you find a $b$, than using a 4° symbol $o$ to "cancel" pair of letter a,b until you don't have any $a$, then travel right until you found a $c$ and repeat. This is the general idea (but it'll be my way, I'm not used to work with touring machine and may be quite overcomplicated) and will need a lot of adjustment and you will have to consider a lot of subcase and situation.

Related Solutions

[Math] Designing a Turing machine for Binary Multiplication

That sounds like a good plan -- except you don't want to add $x$ to $x$; you want to add $x$ to a separate counter that starts at $0$.

Do you already have a machine for addition with the number representation you use (which preserves one of the operands on the tape and increases the other destructively)? Otherwise start by making that.

Alternatively if you're representing the integers in base-2 you could replicate the usual long multiplication algorithm:

Set T=0
While X != 0:
   If the lowest bit of X is 1:
      Set T=T+Y
   End if
   Remove the lowest bit from X
   Append a 0 bit at the end low of Y
End while
The result is in T

This may not even be more complex to program, and will run faster (though that is typically not a relevant consideration when we talk about Turing machines. It might be a relevant difference here because it is more than a polynomial difference).

[Math] Designing a turing machine for primality check.

Firstly, your intuition about how such a program would work is absolutely correct, and for all effective purposes would be completely satisfactory (in my view).

Secondly, as you probably know, prime numbers must be defined in terms of multiplication/division because prime numbers have exactly 2 factors (factorization being a concept developed from multiplication/division).

Thirdly, before trying to make a turing machine that identifies prime numbers, I would focus on making a turing machine that multiplies or divides.

Lastly, have you ever seen the code for a turing machine that multiplies or divides? The codes themselves are pretty non-trivial, especially if you want to limit your turing machine to simply using 1s and 0s. I would imagine that a program for identifying primes would be even more impressive, being that the program must contain the concepts of multiplication/division and then expand on them.

Good luck!

Best Answer

Related Solutions

[Math] Designing a Turing machine for Binary Multiplication

[Math] Designing a turing machine for primality check.

Related Question