int mod(int m, int n)
{
while(n < m)
{
int i = 0;
while(i < n)
{
m-=1;
i+=1;
}
}
return m;
}
turing machine (if else and while loop)
Author
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:
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.
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.
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.
Maybe an example would be better...
And, indeed, 7 mod 3 = 1
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
Author
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:
is that much more long winded, my TM has about 23 states and doesn't allow m or n to be zero on startup.
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.
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.
Aside from that, looks cool.
Author
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).
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).
This topic is closed to new replies.
Advertisement
Popular Topics
Advertisement