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
Design 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 = 4X
Fill out the following blanks for the instructions of a Turing machine that
moves an input string over {a, b} to the right one cell position. The read/write
head of the control unit initially is at the left end of the input string. The rest
of the tape cells are blank. The TM will move the entire string to the right
one cell position and leave all remaining tape cells blank. The read/write
head ends at the right end of the output string.
(0, a, A, R,
|)
found an a
, b, A, R,L
found a b
Ʌ, A, S, halt)
Done
( 1
a, a, R,
b, a, R,
,
Ʌ, a, S, halt)
found an a & to write an a
found a b & to write an a
Done
found an a & to write a b
found a b & to write a b
( 2, a, b, R,
, b, b, R,
Ʌ, b, S, halt)
Done
Construct a Turing Machine that computes the expression 2x+y, where x, y ≥ 0, and are represented on the tape as a sequence of 1s separated by a 0. For e. g., Say, x = 3, y = 5 are represented on the screen as ⊢111011111; At the end of the computation, the tape contents should be ⊢11111111111 representing the number 2x+y = 2(3)+5 = 11.
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
- Example 9.7 For E = {a,b}, design a Turing machine that accepts L= {a,b„:n21}. Intuitively, we solve the problem in the following fashion. Starting at the leftmost a, we check it off by replacing it with some symbol, say x. We then let the read-write head travel right to find the leftmost b, which in turn is checked off by replacing it with another symbol, say y. After that, we go left again to the leftmost a, replace it with an x, then move to the leftmost band replace it with y, and so on. Traveling back and forth this way, we match each a with a corresponding b. If after some time no a's or b's remain, then the string must be in L. Working out the details, we arrive at a complete solution for which Q= {qo91;9293,94},F= {q4}, E= {a,b},T={a,b, x, y,¤}. The transitions can be broken into several parts. The setarrow_forwardHere is a description of a Turing machine. The input alphabet is (a, b). The state set is: {90, 91, 92, 93, 94, 9acc, grej} The transition function is given in the table below: 9⁰ (9₁, a, R) b (92, b, R) (grej, *, R) 93 94 (qacc. a, R) (qrej, a, R) (arej, b, R) (qacc, b, R) (arej,*, R) (qrej, *, R) (a) Draw the configuration of the Turing machine after 3 steps on input "aabba". When the Turing machine is in the initial configuration, it has executed zero steps. a 91 (9₁, a, R) * 92 (92, a, R) (9₁, b, R) (93, *, L) (92, b, R) (94*, L) (b) For how many steps does the Turing machine run on input string "a" before the Turing machine halts? Does the Turing machine accept the string "a"? (c) Simulate the Turing machine on input "aaba". Does it accept? Draw the final two configurations of the Turing machine computation. In the last configuration, the Turing machine is either in the accept or reject state. (d) Simulate the Turing machine on input "aabb". Does it accept? Draw the final two…arrow_forwardQUESTION 4 The string 'abbba' will be accepted by the Turing Machine shown. Y:y. R a; a. R a ; a, L q1 ax,R by.L X: x,R q2 x; x,R b;b.R y:y.L b;b.L x; x, L b;b.R b:b.R q3 q4 96 q11 z;z, R 97 b;b,R q10 98 b:y.R b;b,L z;z.L q12 99 O True O Falsearrow_forward
- Construct a Turing machine that computes the function ? of ? is equal to two ?, i.e. if the input is zero to the power ? then the output would be zero to the power two ? e.g. if it says 000 on the tape before the machine is run it should read 000000 on the tape when it has stopped.arrow_forward1. Implement the following Boolean equations in a Structured Text program. If the program was for a state machine what changes would be required to make it work? light = (light + dark • switch) • switch • light dark (dark + light • switch) • switch • darkarrow_forwardFORMAL LANGUAGES AND AUTOMATIC THEORY A Moore-type finite automaton for a language using the alphabet ∑= {0, 1, 2, 3, 4, 5, 6, 7, 8, 9} design. The machine will produce the remainder of the 3 division of the number at the entrance at the exit. For example; If there is 251 at the entrance, the output will be 2. In other words, the remainder of 251 to 3 is 2. As the entrance 144312 arrival will be 0 There is no limit to the length of the input sequencearrow_forward
- Write the following Informal sentences to a Formal words: Traffic accidents are on the rise these days. Most of the accidents brought about injuries and death. Researchers have found out that most of the accidents are brought by inexperienced drivers, for example young drivers.arrow_forwardPlease draw out a DETERMINISTIC Turing Machinearrow_forwardOnly do part c,d,e,farrow_forward
- Use JFLAP to represent a Turing machine that represents the following algorithm. given alphabet is a, b, c, and x. and the regx is (a+b+c)m where m>= 3, make a machine that reads the first character places an x backs up and puts the original character down. The machine is then to ff past ALL a,b,c then ff past all x to the next a,b,c. read that character replace it with an x, rewind past all x, past all a,b,c to the next blank and put it down. Continue until there are only blanks past the x characters.arrow_forwardHow can I create a Turing machine with ones and zeros, which finds out if an integer n, represented as a sequence of n 1s (111 representes 3), is divisible by 2 or not. It should start in position of the 1 on the far left. When it stops, the output should be 0 if the number is divisible by 2, and 1 if the number is not divisible by 2. Examples: Input = 111, Output = 001 (3 is not divisible by 2, 3 divided by 2 gives 1 in remainder) Input = 1111, Output = 0000 (4 is divisible by 2, 4 divided by 2 gives 0 in remainder)arrow_forwardb/a/L c/c/L a/c/R c/b/R a/c/R a/b/L c/a/L bp/R b/b/R a/a/R c/c/R (b) In this part we are looking at the Turing-Machine above. We assume here that b is the blank symbol, {a,c} is the input alphabet. (1) Give two words recognised by this Turing Machine. (ii) Give a computation for the input cc. If you think the computation diverges, give the first 5 configurations of the computation.arrow_forward
arrow_back_ios
SEE MORE QUESTIONS
arrow_forward_ios
Recommended textbooks for you
Principles of Information Systems (MindTap Course...Computer ScienceISBN:9781285867168Author:Ralph Stair, George ReynoldsPublisher:Cengage Learning
Principles of Information Systems (MindTap Course...
Computer Science
ISBN:9781285867168
Author:Ralph Stair, George Reynolds
Publisher:Cengage Learning