Computer Science: An Overview (13th Edition) (What's New in Computer Science)
13th Edition
ISBN: 9780134875460
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
3. Consider the following Turing Machines. Match then with the tickie definition of the language. Write your answer in the blank
column of the table below:
x/x R
a/a R
b/b R A/AL
a/a L
b/b L
a/A R
b/BR
B/BL
#/#L
a/A L
b/BL
#/#R
9₂
4₂
x/x R
40
a/a R
b/b R
X/X R
A/AL
B/B L
95
#/#R
Y
96
A/a L/
B/b L
b/B R
9,
9₂
B/#L
96
#/# R
90
4₂
b/# R
#/#L
99
#/#L
a/AR
A/AR 98
B/BR
A/#L
a/a L
b/b L
#/#L
a/# R
A/AR
B/BR
a/a R
b/b R
X/X R
a/a R
b/b R
9₁
#/# R
9₁
B/BL
#/# L
92
9₁
a/# L
a/a L
9₂
B/BL
#/# L
94
95
b/b L
a/a R
b/# L
b/b R
A.
L = {w#w | w = {a,b}*} B. L = {www = {a,b}*}
90
B/B R
a/a R
b/b R
a/x R
9,
b/x R
B/BL
#/#R
94
a/x R
#/#R
x/x R
a/a R
b/b R
x/xR
#/#R_
a/a R.
b/b R
S
92
B/BR
90
91
#/# R.
b/x R
B/BL
99
95
(910
a/a R
b/b R
x/x R
C. L = ({ww | w = {a, b}*}
#/#R
97
b/x L
#/#R
a/a L
b/b L
a/a R
b/b R
93
96
a/a R
b/b R
#/#L
B/BL
94
x/x L
x/x L
B/BL
a/x L
x/x L
#/#L
a/x L a/a L
b/b L
x/x R
as
9
b/x L
97
D. L = {w#w² | w = {a, b}*}
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.
Explain the formal description of a Turing Machine in clear and short words by describing each component of the formal description.
Chapter 12 Solutions
Computer Science: An Overview (13th Edition) (What's New in Computer Science)
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
- 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.arrow_forwardDesign 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…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
- Design a Turing machine that accepts a string of a and b where the number of a's is one more than the number of of b's? first write the outline then the draw the diagram.arrow_forwardDesign a Turing machine that decides the language above by giving a high-level description of how it operates (how the head moves around, etc.); do not give an actual state diagram.arrow_forwardA 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_forward
- Q1. Construct Turing Machines for the given regular expressions. i. b (aa + ab') + (abb')* + Ã Answer: ii. (a'bbb)' a' + (aa)" (X + a) Answer:arrow_forwardConsider the Turing Machine defined as follows (q0,0,q0,0,R), (q0,1,q1,0,R), (q0,B,q2,B,R), (q1,0,q1,0,R), (q1,1,q0,1,R) and (q1,B,q2,B,R). Describe what this TM does when presented with bit strings defined over the alphabet = {0,1} as input. (Note: B = Blank).arrow_forwardConsider the Turing Machine defined as follows: (q0,0,q0,0,R), (q0,1,q1,0,R), (q0,B,q2,B,R), (q1,0,q1,0,R), (q1,1,q0,1,R) and (q1,B,q2,B,R). Describe what this TM does when presented with bit strings defined over the alphabet Σ = {0,1} as input. (Note: B = Blank).arrow_forward
- draw 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_forwardCreate a Turing machine that computes the function f(x) = 2x + 3, where x is a positive integer represented in unary. The Turing machine starts with the input already on the tape and the read/write head positioned over the leftmost symbol of the input.arrow_forwardConstruct a Turing machine that copies the first three nonblank symbols over the next three blank symbols.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