Design a Turing machine to compute the x mod y, y>0 function. On entry, the number is represented as a unary number using |. This way, 5 will turn to |||||. When two numbers are inputted, they are placed as unary numbers separated by #. The answer must contain states, with clear instructions on what to do when finding a symbol, namely what state to go to, where to go (Stay, Left, Right) and what symbol to put in a cell. E.g.: q0 If found _, put _, go to q1 and Stay. If found |, put |, go to q0 and Left. q1 If found _, put _, go to q1 and Right If found |, put X, go to q2 and Right. Etc… Feel free to use as many auxiliary symbols as you need. In the end, the program needs to output n '|' symbols without spaces('_') or anything, where n is the result of x mod y. So, the result for input 10 and 7 and output for it would look like this: We input numbers in the machine, and they appear on the Turing machine line like this, every symbol in its cell: Input: ||||||||||#||||||| Once the program is done, there should be no other symbols on the line, except for n '|' symbols, where n is the result of x mod y. In this example, we have 10 mod 7, so it will be 3: Output: ||| Thank you!
Design a Turing machine to compute the x mod y, y>0 function. On entry, the number is represented as a unary number using |. This way, 5 will turn to |||||. When two numbers are inputted, they are placed as unary numbers separated by #. The answer must contain states, with clear instructions on what to do when finding a symbol, namely what state to go to, where to go (Stay, Left, Right) and what symbol to put in a cell.
E.g.:
q0
If found _, put _, go to q1 and Stay.
If found |, put |, go to q0 and Left.
q1
If found _, put _, go to q1 and Right
If found |, put X, go to q2 and Right.
Etc…
Feel free to use as many auxiliary symbols as you need. In the end, the program needs to output n '|' symbols without spaces('_') or anything, where n is the result of x mod y.
So, the result for input 10 and 7 and output for it would look like this:
We input numbers in the machine, and they appear on the Turing machine line like this, every symbol in its cell:
Input: ||||||||||#|||||||
Once the program is done, there should be no other symbols on the line, except for n '|' symbols, where n is the result of x mod y. In this example, we have 10 mod 7, so it will be 3:
Output: |||
Thank you!
Trending now
This is a popular solution!
Step by step
Solved in 3 steps
