Problem 8: Design a Turing machine that takes inputs like ...B1110111111B.... deletes the middle 0, and keeps the same number of 1s (so, in this case, it should output ...B111111111B...). This can be thought of as adding two numbers.

Problem 8: Design a Turing machine that takes inputs like ...B1110111111B.... deletes the middle 0, and keeps the same number of 1s (so, in this case, it should output ...B111111111B...). This can be thought of as adding two numbers.

C++ Programming: From Problem Analysis to Program Design

8th Edition

ISBN:9781337102087

Author:D. S. Malik

Publisher:D. S. Malik

Chapter10: Classes And Data Abstraction

Section: Chapter Questions

Problem 19PE

See similar textbooks

Related questions

Q: An online warehouse provides features for their customers to browse and search products and to place…

A: Online shopping is used to purchase different products through internet and use case diagram is just…

Q: The function f(x) = x-e has a zero on the interval [0, 1] O False O True

A: please check the solution below

Q: Suppose the Ethernet transmission algorithm is modified as follows: After each successful…

A: Before transferring the data, the channel is detected in accordance with the Ethernet Transmission…

Q: Suppose the Ethernet transmission algorithm is modified as follows: After each successful…

A: In this, the channel is detected prior to sending the information. Assuming the channel is viewed as…

Q: time domain specification? define corner frequency ?

A: The answer for the above mentioned question is given in the following steps for your reference.

Q: Assume that 35% of a program cannot be sped up, and the remaining 65% has no dependencies and hence…

Q: Create a apex class called addition and then create a method to add the 2 integer and return the…

A: Introduction to apex: Apex is a strongly typed, object-oriented programming language that allows…

Q: Please in C Language Write a program that uses an existing text file (text.txt) to determine…

A: Given Write a program that text file (text.txt) to find the number of occurrences of each letter

Q: In this problem, you will write a solution to the Fizz Buzz problem (description to follow) within…

A: Here is c++ program with implement of code:

Q: Create a webpage to sort three numbers using JavaScript conditional statement. For example, x=0,…

A: HTML code <!DOCTYPE html><html><head><meta charset=utf-8…

Q: Please do it with regular expression. Don't use loops please. Do fast, I have no time left Write a…

A: Required:- Please do it with regular expression. Don't use loops, please. Do fast, I have no time…

Q: - Suppose a TCP message that contains 1024 bytes of data and 20 bytes of TCP header is passed to IP…

Q: An online warehouse provides features for their customers to browse and search products and to place…

A: Solution:: Package diagram, a kind of (related to what holds something together and makes it…

Q: What form of Denial of Service attack is well known for spoofing the source and destination address…

Q: When it comes to cloud security, what is the "shared responsibility" paradigm like?

A: Introduction A shared responsibility paradigm is a sort of cloud security model.

Q: (a) Define digital watermarking technology.

Q: Write a program that converts distances measured in kilometers to miles.One kilometer is…

A: Kilometers must be entered by the user. The kilometres variable holds this value. Since 1 kilometre…

Q: element specifies the URL of the script on the web server that will be invoked to process the form’s…

A: The given question is a MCQ type question.

Q: Suppose the Ethernet transmission algorithm is modified as follows: After each successful…

A: Before transferring data, the Ethernet transmission algorithm detects the channel. If the channel is…

Q: This program was run once and the output was 15. If we run this program another 100 times how many…

A: Here we have a code written in C++ programing language. Inside the main block, we have used rand()…

Q: PROVIDE JS SOURCE CODE Design a web page with a text box (username) where the user can enter a name…

A: Here, Code instructions are given

Q: Suppose a workstation has an I/O bus speed of 1 Gbps and memory bandwidth of 2 Gbps. Assuming DMA is…

Q: I need help in this C program. Assume a list of integers stored in a text file named…

A: ALGORITHM:- 1. Declare a file and insert the integer elements in it. 2. Read the integers from the…

Q: Sites like Zillow get input about house prices from a database and provide nice summaries for…

A: The program is written in C++. Check the program screenshot for the correct indentation. Please…

Q: Apex Assignment: Create a apex class called addition and then create a method to add the 2 integer…

A: Basically Apex class is a collection of data members and methods.

Q: I need help in this C program. Assume two lists of integers both in ascending order. The first list…

A: Assume two lists of integers both in ascending order. The first list was stored in binary files…

Q: c) Assuming an 8-bit system is used (i.e. the system uses 8 bits to represent an integer):…

A: This question comes from Number System which is a paper of Computer Science. Let's discuss it in the…

Q: help me to write a program in c++ compiler plz Q6: write a program to calculate the addition table…

A: As you asked multiple questions we are answering first question. If you want solution of any…

Q: A(n) ________________ element indicates that its contents should be emphasized. A emphasize…

A: A(n) ________________ element indicates that its contents should be emphasized. emphasize focus…

Q: Based on the following scenario: Salim Bersaudara Sdn Bhd (SBSB) is a factory that produces…

A: The answer is given below.

Q: Using HTML Create a web page that will prompt the user for a name and age, and write a message…

A: I have provided HTML CODE( having internal JS ) along with CODE SCREENSHOT and OUTPUT…

Q: 1. This program will calculate value of the function for range of x and steps given in your variant.…

A: Answer along with code and output screenshot is given below

Q: Q1. What are the basic interfaces of Java Collections Framework? Q2. What are the Data Types…

A: Below is the answer to above question. I hope this will be helpful for you...

Q: Propose a lookup algorithm for an IP forwarding table containing prefixes of varying lengths that…

Q: Create a file named StudentArrayList.java, within the file create a class named StudentArrayList.…

A: Introduction Create a file named StudentArrayList.java, within the file create a class named…

Q: signal.. Each time slot contains 148 bits. Just 114 of these 148 bits reflect speech or other info.…

A: The answer is

Q: Suppose the Ethernet transmissi follows: After each successful tra one or two slot times before atte

A: According to Ethernet transmission algorithm, the channel is sensed before transmitting the data. If…

Q: Given the recurrence relation: • T(n) = 8 if n 6. Find the value of T(495). [Hint: Use a recursion…

Q: Feed me 4 hex digits: 0001 1 Children 0 Adult 0 Senior Citizen No Matinee Discount No Blockbuster…

A: Feed me 4 hex digits: 00011 Children0 Adult0 Senior CitizenNo Matinee DiscountNo Blockbuster…

Q: A micro instruction format has micro operation field which is divided into 2 subfields F1 and F2,…

A: Logic , if there are n micro- operation then we can represent it in form of 2n where n will…

Q: using HTML Create a web page that will pop up an alert message that welcomes the user to the web…

A: The above question is solved in step 2 and step 3 :-

Q: PROGRAMMABLE LOGIC CONTROLLERS

A: ) notation list of ladder diagram of inputs and outputs Inputs Start button- PB1 Stop push button -…

Q: X435: Generics - Comparable Cage Modify the Cage class to implement Comparable. The definition of…

A: Java Comparable interface is used to order the objects of the user-defined class. The interface is…

Q: statuses for all registered children that is emailed to the staff and authorities concerned. They…

A: Solution: The SDLC should not be scrapped for every project because some systems may be prematurely…

Q: Suppose the Ethernet transmission algorithm is modified as follows: After each successful…

A: According to Ethernet transmission algorithm, the channel is sensed before transmitting the data. If…

Q: Q2: al (1) Write colon (:) way to display the following matrix: A = 3 4 5 6 7 13 14 15 16 171 2)…

A: As I have read the guidelines I can provide answers to only 1 part of the questions in case of…

Q: Your task is to create a program that prompts the user with the following user menu: Please enter…

A: The above question is solved in step 2 and step 3 :-

Q: 5. Write down the insertBefore method which inserts a new element in the list before the node…

A: temp = head while temp.next: if temp.next.data == elem: break if temp.next.data == head.data:…

Q: Tracethefollowingcodebyshowingthevaluesofthe3variablesinthetableontheright,foreachlineof code thatis…

A: var keyword: It is used to declare the variable. Syntax: var x; x is the name of that variable.

Q: There are blank 3 digit counting numbers that are made using only the odd digits 1,3,5,7,9 ?

A: To form a 3 digit number using 1,3,5,7,9. We know that all the 3 digit places are must be one of the…

Concept explainers

Problems on Turing Machines

In the computational world, the Turing machine is a powerful computation engine. The invention of the Turing Machine is done by Alan Turing in 1936. A Turing Machine (TM) is a diagrammatic model of a fictional computer. It determines an output from a set of input variables using a pre-defined set of rules. It is used to get around the limitations of finite automata and pushdown automata.

Question

Problem 8: Design a Turing machine that takes inputs like...B1110111111B.....
deletes the middle 0, and keeps the same number of 1s (so, in this case, it should
output ...B111111111B...). This can be thought of as adding two numbers.

Expert Solution

This question has been solved!

Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.

SEE SOLUTION Check out a sample Q&A here

Step 1

VIEW

Step 2

VIEW

Step by step

Solved in 2 steps

SEE SOLUTION Check out a sample Q&A here

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 set
Show that the following function is Turing-computable. f(x)=x+1 . I want the drawing
You will disappoint me if you solve it without drawing I just want you to draw me the following question please: Turing machine that computes the function f(x,y) = x+2y, with both x and y strictly positive integers.
4. Draw the Turing machine that computes the function f(x,y) = x+2y, with both x and y strictly positive integers.
Not so. The real question states that: Construct a turing machine that computes the function ?(?) = 2?, , i.e. if the input is 0^? then the output would be 0^2? 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.
Design a Turing machine M that decides the language L = {0n1n|n> 0}.
b/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.
4. LetΣ ={a, b}. LetL={aibai|i≥0}.Give a Turing machine (TM) that accepts the languageL.Assume (as in the examples done in our course videos) that, when theTM starts, the head is on a blank symbol,∆, and the input string isimmediately after that blank symbol on the tape. For example, if theinput string wereaaabaaa, then the inital tape configuration would be∆aaabaaa
Build a Turing Machine T.M. with three tracks that receives two binary numbers and indicates which of the two is higher. We will consider that the data are stored in the first two tracks and aligned to the right, it means, the least significant bits of both are located in the same column. In the third track it will be written a B, a L or an E, indicating respectively that the first number is larger, smaller or equal to the second.
A common problem that arises in software maintenance is identifying (and then removing) dead code, code that will never be executed no matter what input the program is given. The analogous problem for TMs would be to determine if a state is never entered, no matter what input the TM is given. Prove by reduction that Ldead, the set of pairs (T,s) where T is a Turing machine and s is a dead state, is not recursive.
The puzzle called the Towers of Hanoi consists of three pegs, one of which contains several rings stacked in order of descending diameter from bottom to top. The problem is to move the stack of rings to another peg. You are allowed to move only one ring at a time, and at no time is a ring to be placed on top of a smaller one. Observe that if the puzzle involved only one ring, it would be extremely easy. Moreover, when faced with the problem of moving several rings, if you could move all but the largest ring to another peg, the largest ring could then be placed on the third peg, and then the problem would be to move the remaining rings on top of it. Using this observation, develop a recursive algorithm for solving the Towers of Hanoi puzzle for an arbitrary number of rings.
Computer Science provide a three-tape turing machine for L = a^n where n => 0 is perfect square. λ should be accepted. tape 1: string to be processed n^2 a's tape 2: strings of length n^2. These sequences will be made up of symbol Y tape 3: strings of length n. These sequences should be made up of symbol Y. Tape 2 and 3 recursively generated from string 1, only last string retained on tape.