Computer Science: An Overview (12th Edition)
12th Edition
ISBN: 9780133760064
Author: Glenn Brookshear, Dennis Brylow
Publisher: PEARSON
expand_more
expand_more
format_list_bulleted
Concept explainers
Question
Chapter 12.2, Problem 1QE
Program Plan Intro
Turing machine:
- Turing machine is used as a tool to understand the power of
algorithmic processes. - It consists of a control unit which is used to read and write symbols on a tape.
- A tape is divided into cells and each cell has one of finite sets of symbols.
Expert Solution & Answer
Want to see the full answer?
Check out a sample textbook solution
Students have asked these similar questions
7. Design a Turing machine that adds two integers together. The number system is as following,
O is represented as 1, 1 is represented as 11, 2 is represented as 111, and so on.
Question 1
A Turing Machine is defined by the following 5 tuples:
(0,0,1,0,R)
(0,1,1,1,L)
(0,b,b,O,L)
(1,0,0,1,L)
(1,1,0,1,R)
The initial configuration is shown below:
b 0 0 1 1 1 b
0
Select the correct statements below:
There is no 'O' on the tape when the machine halts.
Rule (0,1,1,1,L) is never applied.
Rule (1,0,0,1,L) is never applied.
This Turing Machine will halt.
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…
Chapter 12 Solutions
Computer Science: An Overview (12th Edition)
Ch. 12.1 - Prob. 1QECh. 12.1 - Prob. 2QECh. 12.1 - Prob. 3QECh. 12.1 - Prob. 4QECh. 12.2 - Prob. 1QECh. 12.2 - Prob. 2QECh. 12.2 - Prob. 3QECh. 12.2 - Prob. 4QECh. 12.2 - Prob. 5QECh. 12.3 - Prob. 1QE
Ch. 12.3 - Prob. 3QECh. 12.3 - Prob. 5QECh. 12.3 - Prob. 6QECh. 12.4 - Prob. 1QECh. 12.4 - Prob. 2QECh. 12.4 - Prob. 3QECh. 12.5 - Prob. 1QECh. 12.5 - Prob. 2QECh. 12.5 - Prob. 4QECh. 12.5 - Prob. 5QECh. 12.6 - Prob. 1QECh. 12.6 - Prob. 2QECh. 12.6 - Prob. 3QECh. 12.6 - Prob. 4QECh. 12 - Prob. 1CRPCh. 12 - Prob. 2CRPCh. 12 - Prob. 3CRPCh. 12 - In each of the following cases, write a program...Ch. 12 - Prob. 5CRPCh. 12 - Describe the function computed by the following...Ch. 12 - Describe the function computed by the following...Ch. 12 - Write a Bare Bones program that computes the...Ch. 12 - Prob. 9CRPCh. 12 - In this chapter we saw how the statement copy...Ch. 12 - Prob. 11CRPCh. 12 - Prob. 12CRPCh. 12 - Prob. 13CRPCh. 12 - Prob. 14CRPCh. 12 - Prob. 15CRPCh. 12 - Prob. 16CRPCh. 12 - Prob. 17CRPCh. 12 - Prob. 18CRPCh. 12 - Prob. 19CRPCh. 12 - Analyze the validity of the following pair of...Ch. 12 - Analyze the validity of the statement The cook on...Ch. 12 - Suppose you were in a country where each person...Ch. 12 - Prob. 23CRPCh. 12 - Prob. 24CRPCh. 12 - Suppose you needed to find out if anyone in a...Ch. 12 - Prob. 26CRPCh. 12 - Prob. 27CRPCh. 12 - Prob. 28CRPCh. 12 - Prob. 29CRPCh. 12 - Prob. 30CRPCh. 12 - Prob. 31CRPCh. 12 - Suppose a lottery is based on correctly picking...Ch. 12 - Is the following algorithm deterministic? Explain...Ch. 12 - Prob. 34CRPCh. 12 - Prob. 35CRPCh. 12 - Does the following algorithm have a polynomial or...Ch. 12 - Prob. 37CRPCh. 12 - Summarize the distinction between stating that a...Ch. 12 - Prob. 39CRPCh. 12 - Prob. 40CRPCh. 12 - Prob. 41CRPCh. 12 - Prob. 42CRPCh. 12 - Prob. 43CRPCh. 12 - Prob. 44CRPCh. 12 - Prob. 46CRPCh. 12 - Prob. 48CRPCh. 12 - Prob. 49CRPCh. 12 - Prob. 50CRPCh. 12 - Prob. 51CRPCh. 12 - Prob. 52CRPCh. 12 - Prob. 1SICh. 12 - Prob. 2SICh. 12 - Prob. 3SICh. 12 - Prob. 4SICh. 12 - Prob. 5SICh. 12 - Prob. 6SICh. 12 - Prob. 7SICh. 12 - Prob. 8SI
Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.Similar questions
- The Church-Turing thesis tells us that Choose one: a.A mechanical device can be intelligent. b.A mechanical device can process mathematical deduction. c.A computer cannot have a soul.arrow_forwardExplain the formal description of a Turing Machine in clear and short words by describing each component of the formal description.arrow_forwardDesign a Turing machine that multiplies any +ve number by four. So if tape contains the number 5 (in its binary form) then TM should leave 20 on the tape (in binary form). Basically you need to implement this function: Y = 4Xarrow_forward
- A Turing Machine is defined by the following 5 tuples: (0,0,1,0,R) (0,1,1,1,L) (0,b,b,0,L) (1,0,0,1,L) (1,1,0,1,R) The initial configuration is shown below: b001 1|1b Select the correct statements below: This Turing Machine will halt. Rule (0,1,1,1,L) is never applied. O Rule (1,0,0,1,L) is never applied O There is no '1' on the tape when the machine haltsarrow_forwarddraw the state diagram of a Turing Machine that will compute x + y, where x and y are given in unary representation. Assume that the non-blank portion of the input tape consists of x occurrences of ones (to represent x) followed by a $ sign and then y occurrences of ones with an infinite number of blanks on both sides of the non-blank portion of the tape. The non-blank portion of the output of your Turing Machine is expected to be x ones followed by the $ sign followed by y ones followed by the # sign followed by x + y ones. For example, if x = 5 and y = 7, then your input tape will be 11111$1111111, which produces the output tape 11111$1111111#111111111111 (with blanks on both sides of the non-blank portion). handwritten will workarrow_forwardThe language L is defined as L={a"b"c" | n>1} over the alphabet E={a,b,c}. Build a Turing Machine that accepts the language L. i) Explain shortly the logic behind your design. ii) Draw the Turing Machine. iii) Show the execution chain for the word aabbccccce.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Database System ConceptsComputer ScienceISBN:9780078022159Author:Abraham Silberschatz Professor, Henry F. Korth, S. SudarshanPublisher:McGraw-Hill Education
Starting Out with Python (4th Edition)Computer ScienceISBN:9780134444321Author:Tony GaddisPublisher:PEARSON
Digital Fundamentals (11th Edition)Computer ScienceISBN:9780132737968Author:Thomas L. FloydPublisher:PEARSON
C How to Program (8th Edition)Computer ScienceISBN:9780133976892Author:Paul J. Deitel, Harvey DeitelPublisher:PEARSON
Database Systems: Design, Implementation, & Manag...Computer ScienceISBN:9781337627900Author:Carlos Coronel, Steven MorrisPublisher:Cengage Learning
Programmable Logic ControllersComputer ScienceISBN:9780073373843Author:Frank D. PetruzellaPublisher:McGraw-Hill Education
Database System Concepts
Computer Science
ISBN:9780078022159
Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan
Publisher:McGraw-Hill Education
Starting Out with Python (4th Edition)
Computer Science
ISBN:9780134444321
Author:Tony Gaddis
Publisher:PEARSON
Digital Fundamentals (11th Edition)
Computer Science
ISBN:9780132737968
Author:Thomas L. Floyd
Publisher:PEARSON
C How to Program (8th Edition)
Computer Science
ISBN:9780133976892
Author:Paul J. Deitel, Harvey Deitel
Publisher:PEARSON
Database Systems: Design, Implementation, & Manag...
Computer Science
ISBN:9781337627900
Author:Carlos Coronel, Steven Morris
Publisher:Cengage Learning
Programmable Logic Controllers
Computer Science
ISBN:9780073373843
Author:Frank D. Petruzella
Publisher:McGraw-Hill Education