Turing machine question needs help!

[cyper]

Can anyone design a turning machine which does the multiplication of integer n and m? The input tape starts with a string n+1 1s. This string represents integer n. After this string, there is a blank symbol B. After blank symbol, there is the other string which are m+1 1s. This string represents integer m. After computation, the turning machine should halt with n*m+1 1s on the tape. The result string represents the product of integer n and m. Of course, the tape alphabets are 0, 1 and B.

 

For example, if I want to to the multiplcation of integer 2 and 3. The input tape should have string 111B1111. After computation, the turing machine should halt with the string 1111111 on the tape. Thanks.

[neo007]

lol, yea sure...give me five minutes and it'll be ready. lol

Its been a while since i've done any programming, and even when i did it was simple stuff, like integer A + integer B

What you're trying to do looks complicated.

It would help if you stated what language you are using.

[Aeternus]

Right, having never played with Turing machines before (despite having heard of them), I decided to give it a go having read up on the general concept.

 

The idea seems simple enough, you have states and a state will transistion to a different state depending on the value at the head and so on, if a state can't transistion then the machine halts. One can define which direction the head moves at each transistion as well as the change of value that the head makes before moving. The head can move however far one likes in any direction where empty "cells" are usually defined by 0.

 

I knocked together something using a Turing Machine Simulator I found to test it and so here is the code -

 

  1,1,2,_,>
  1,B,8,_,>
  2,1,2,1,>
  2,B,3,B,>
  3,_,9,_,<
  3,1,4,_,>
  3,B,6,B,<
  4,1,4,1,>
  4,B,4,B,>
  4,_,5,B,<
  5,B,5,B,<
  5,1,5,1,<
  5,_,3,_,>
  6,_,6,1,<
  6,B,7,B,<
  7,1,7,1,<
  7,_,1,_,>
  8,1,8,_,>
  8,B,8,1,>
  8,_,H,_,<
  9,B,H,_,>

 

Where it is in the format State A , Character , State B, New Character, Direction . Where direction "<" means move the head left, ">" means move the head right and where the state H is simply a state that has no transistions and is therefore the halt state. This is simply the format that the simulator I was using uses and where you have used "0" , it uses "_" and I couldn't be arsed to convert them all back after having debugged it in the applet. It's late here now so.... I might try and post this in a more readable format (ie using better named states, using 0 instead of _ and using named directions) tomorrow.

 

Knowing my like there will be some stupid problem with it but it seems to work , although one could probably make a much better one (as I have no real experience with this sort of thing).

 

Machine Simulator