2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Is this an actual homework problem or something for fun? You are going to need to take the string 111#111 and remove one of the ones to get 111#11 then recursively apply the factorial for 11, etc. It's gonna be painful, which is why I asked if it was homework, because, if so, I hate this sort of problem. :) $\endgroup$
    – Thomas Andrews
    Commented Feb 17, 2015 at 18:28
  • 1
    $\begingroup$ @ThomasAndrews yes, this is an assignment. I also hate this kind of problems. :P $\endgroup$
    – Aniq
    Commented Feb 17, 2015 at 18:33

2 Answers 2

Reset to default
1
$\begingroup$

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.

$\endgroup$
8
  • $\begingroup$ Usually, these problems are worked with "111" representing three - that is, the most trivial encoding of all. $\endgroup$
    – Thomas Andrews
    Commented Feb 17, 2015 at 19:05
  • $\begingroup$ Ow right, I will edit my answer. $\endgroup$
    – Marcos Treviso
    Commented Feb 17, 2015 at 19:34
  • $\begingroup$ @meitcher I need help in unary. So if you can show me how to do it in unary, it will be very helpful for me. Thanks $\endgroup$
    – Aniq
    Commented Feb 17, 2015 at 21:57
  • $\begingroup$ I edited my answer again and put an algorithm. If you are working with JFLAP and still get stuck, send an email to me ;-). $\endgroup$
    – Marcos Treviso
    Commented Feb 17, 2015 at 23:06
  • $\begingroup$ @meitcher yes I am using JFLAP. Can you help me, I don't know how to multiply two unary. $\endgroup$
    – Aniq
    Commented Feb 18, 2015 at 14:38
1
$\begingroup$

I have made this state diagram for Unary number, if anything is unclear, I'll gladly explain it.

$\endgroup$
1
  • $\begingroup$ If you are not able to understand the state diagram, then leave a comment I'll redraw it and upload it again with explanation. $\endgroup$
    – Nishant Saxena
    Commented Mar 5, 2019 at 13:20

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .