[Math] Construct a Turing-Machine for Factorial(unary)

automataturing-machines

I am designing a turing machine which calculates the factorial of any given input for example, $3! = 3.2.1$, on tape it will look like this $Blank|1|1|1|Blank$

What I have done so far is that, I made a turing machine which copy string like $111#111$ but I dont know how many times I have to copy it.

I don't want the answer, I just want a lead to start and to get on the right track.

Best Answer

Are you working with decimal or binary numbers? The easy way is working with binary.

My idea for this is just implement a module that multiply two numbers. And then you can split the tape with a arbitrary symbol like '&'. Using the module created, make the number in the left side of '&' multiply the number in right side of '&', after multiplying, just decrement the number in the left side. When the number in the left is equal to one, you can stop.

For example (5!):

Blank | 101 | & | 0000001 | Blank

Blank | 100 | & | 0000101 | Blank

Blank | 011 | & | 0010100 | Blank

Blank | 010 | & | 0111100 | Blank

Blank | 001 | & | 1111000 | Blank

The result is 1111000 in binary. If you want work in decimal, you have to implement the multiplication module for all digits [0-9].

Now just decrement the value in the right side until the value is 0, and each iteration add 1 to other place. This is gonna work, but a better way is make operations for "111" representation, and do them instead of binary operations.

Algorithm:

1. Go to left and crate symbol '&' in a blank space.
2. Go to left and put factorial number (5! = '11111').
3. Go to right until the symbol is not '&'.
4. Go 1 more step to right.
5. Write '1' in a blank space.
6. While left side of '&' not equals to '1'
    7. Multiply the number in the left side of '&' with the number in the right side of '&'.
    8. Put the result in the right side of '&'.
    9. Decrement the number in the left side of '&'.

To do this in a Turing Machine is a kind of tedious, because you will need implement the methods of multiply, decrement and comparison. But using unary representation is not so hard to do.

Btw, are you using some software to make your tests? In my graduation I use JFLAP, is easy to work with it.

Related Question