Turing machine with input in unary notation
Not what you're looking for?
Devise a Turing machine with input given in unary notation (i.e., a string of n 1's denotes the integer n, and numbers are delimited by 0's) such that the machine produces the following output:
0 if x is divisible by 4
1 if x is congruent to 1 modulo 4
2 if x is congruent to 2 modulo 4
3 if x is congruent to 3 modulo 4
Show the state table for the machine.
Purchase this Solution
Solution Summary
The Turing machine is defined, and a detailed explanation of what happens at each step of the computation is provided.
Solution Preview
When the machine starts, there are two 0's on the tape (one at each end) as delimiters, n 1's between the two 0's, and blanks ad infinitum to the left of the first (leftmost) 0, and blanks ad infinitum to the right of the second (rightmost) 0.
What we are going to do is devise a Turing machine that will read 1's in groups of four, and then wipe out the existing group of four 1's before it reads the next group of four 1's.
After reading a group of four 1's, it will replace the rightmost 1 in the group with a 0; then it will move to the left and place a blank in the cell that contains the leftmost 0; finally, it will move to the right and place a blank in each of the cells that originally contained one of the first three 1's in the group of four (counting from left to right), and it will then proceed to read a new group of four 1's (if any).
If there are fewer than four 1's to be read at any point (when the machine is ready to start reading 1's again, after taking the steps already indicated, to deal with the previous group of four 1's), the machine will read the remaining 1's (if any), and then halt. The output will be the then-current contents of the tape:
If n is divisible by 4, there will be no 1's left to be read, so the contents of the tape will be 00, which is the code for "0".
If n is congruent to 1 mod 4, there will be just one 1 left to be read, so the contents of the tape will be 010, which is the code for "1".
If n is congruent to 2 mod 4, there will be just two 1's left to be read, so the contents of the tape will be 0110, which is the code for "2".
If n is congruent to 3 mod 4, there will be just three 1's left to be read, so the contents of the tape will be ...
Education
- AB, Hood College
- PhD, The Catholic University of America
- PhD, The University of Maryland at College Park
Recent Feedback
- "Thanks for your assistance. "
- "Thank you. I understand now."
- "Super - Thank You"
- "Very clear. I appreciate your help. Thank you."
- "Great. thank you so much!"
Purchase this Solution
Free BrainMass Quizzes
Javscript Basics
Quiz on basics of javascript programming language.
C# variables and classes
This quiz contains questions about C# classes and variables.
Inserting and deleting in a linked list
This quiz tests your understanding of how to insert and delete elements in a linked list. Understanding of the use of linked lists, and the related performance aspects, is an important fundamental skill of computer science data structures.
Basic Computer Terms
We use many basic terms like bit, pixel in our usual conversations about computers. Are we aware of what these mean? This little quiz is an attempt towards discovering that.
Java loops
This quiz checks your knowledge of for and while loops in Java. For and while loops are essential building blocks for all Java programs. Having a solid understanding of these constructs is critical for success in programming Java.