Sign in to follow this  
JinJo

turing machine (if else and while loop)

Recommended Posts

JinJo    100
Hi I need to write a turing machine that given the input m and n, which is any natural number, give the output k = n mod m. Now the turing machines have only the symbols 1 and ^ (which is a blank space on the tape), and a number like 4 would be stored on the tape as 1111. the tape can only check the current position and either change the data to 1 or ^ then move the tape head left, right or stay still. I have an algorithm similar to this:
int mod(int m, int n)
{
    while(n < m)
    {
        int i = 0;
        while(i < n)
        {
           m-=1;
           i+=1;
        }
    }
    return m;
}


that should work but the syntax me be wrong 'cos i'm in a hurry. now if the tape input was like this 111^1111111^ the output should be 111^1111111^11 as 7 mod 3 = 2. I can't really draw out my machine hear but basically i know how to loop a state but say i want to say: if(m < n) how would i best do this? I can only read one digit at a time and change it to 1 or ^ and move left, right or stay still. I hope no one thinks i am cheating hear as i do have everything drawn out it's just this part that's annoying,even a link to a tutorial would be nice. Thanks.

Share this post


Link to post
Share on other sites
ToohrVyk    1596
Why do you keep thinking in terms of "if/while/etc" algorithms? Turing machines are not really thought to work this way...

What I would do is the following:

1- Copy both values to the right (should be quite easy if you replace copies values by "c" and revert them to "1" when copying is done)
2- You got the m and n part of your copy. While there are unmarked "1" in m, mark an "1" in n (replace it with a "x"). If there is no unmarked "1" in n to be marked, move to 4.
3- If all "1" in m have been marked as "x", unmark them all (replace them by "1"). Move back to 2.
4- Move back into the tape until you reach m (the copy) while replacing all characters by "^". Once you get there, replace "1" by "^", and "x" by "1". When you reach the "^" that was at the beginning of the m copy, you're done.

Share this post


Link to post
Share on other sites
ToohrVyk    1596
Maybe an example would be better...


Step 1:
Part a:
111^1111111^
c11^1111111^c^
cc1^1111111^cc^
ccc^1111111^ccc^
Part b:
ccc^c111111^ccc^c^
ccc^cc11111^ccc^cc^
ccc^ccc1111^ccc^ccc^
ccc^cccc111^ccc^cccc^
ccc^ccccc11^ccc^ccccc^
ccc^cccccc1^ccc^cccccc^
ccc^ccccccc^ccc^ccccccc^
Part c:
1cc^ccccccc^ccc^ccccccc^
11c^ccccccc^ccc^ccccccc^
111^ccccccc^ccc^ccccccc^
111^1cccccc^ccc^ccccccc^
111^11ccccc^ccc^ccccccc^
111^111cccc^ccc^ccccccc^
111^1111ccc^ccc^ccccccc^
111^11111cc^ccc^ccccccc^
111^111111c^ccc^ccccccc^
111^1111111^ccc^ccccccc^
111^1111111^1cc^ccccccc^
111^1111111^11c^ccccccc^
111^1111111^111^ccccccc^
111^1111111^111^1cccccc^
111^1111111^111^11ccccc^
111^1111111^111^111cccc^
111^1111111^111^1111ccc^
111^1111111^111^11111cc^
111^1111111^111^111111c^
111^1111111^111^1111111^

Step 2:

111^1111111^x11^x111111^
111^1111111^xx1^xx11111^
111^1111111^xxx^xxx1111^

Step 3:
111^1111111^1xx^xxx1111^
111^1111111^11x^xxx1111^
111^1111111^111^xxx1111^

Step 2:
111^1111111^x11^xxxx111^
111^1111111^xx1^xxxxx11^
111^1111111^xxx^xxxxxx1^

Step 3:
111^1111111^1xx^xxxxxx1^
111^1111111^11x^xxxxxx1^
111^1111111^111^xxxxxx1^

Step 2:
111^1111111^x11^xxxxxxx^

Step 4:
111^1111111^x11^xxxxxx^^
111^1111111^x11^xxxxx^^^
111^1111111^x11^xxxx^^^^
111^1111111^x11^xxx^^^^^
111^1111111^x11^xx^^^^^^
111^1111111^x11^x^^^^^^^
111^1111111^x11^^^^^^^^^
111^1111111^x1^^^^^^^^^^
111^1111111^x^^^^^^^^^^^
111^1111111^1^^^^^^^^^^^



And, indeed, 7 mod 3 = 1

Share this post


Link to post
Share on other sites
JinJo    100
Well I hadn't had the chance to check the forum aftre my 2nd post last night and ToohrVyk your right, I realised when I could use other symbols that I didn't need to think of if/else or while etc as I can just copy the values (mind you it took me 5 hours to design my TM (is that bad, I've never done them before).

However my code is slightly different here's roughly what happens:


^111^1111111^
^111^xxxxxxx^
^111^xxxxxx1^1^
^111^xxxxx11^11^
^111^xxxx111^111^
^111^xxx1111^1111^
^111^xx11111^11111^
^111^x111111^111111^
^111^1111111^1111111^

^yyy^1111111^1111111^
^1yy^1111111^111111z^
^11y^1111111^11111zz^
^111^1111111^1111zzz^
^111^1111111^1111^

repeats so it ends up as
^111^1111111^1^



is that much more long winded, my TM has about 23 states and doesn't allow m or n to be zero on startup.

Share this post


Link to post
Share on other sites
ToohrVyk    1596
How do you detect that you "end" as? Your machine would turn the final 1 to a y, and then what? Detect there are no more 1 left and revert every y to a 1?

Aside from that, looks cool.

Share this post


Link to post
Share on other sites
JinJo    100
Nah it checks to see if it has any 1's to change into a z for each y, if not it changes all z's back to 1's and y's back to 1's.

Now I have to code it in java by 2:15 today and i have a maths test at 1:15.

The main problem is, I have never coded anything in java other than hello world. I have most of it designed out as to what it's got to do but I don't know how to setup gui's in Java (like positions, sizes and stuff).

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

Sign in to follow this