Construct a deterministic two-tape Turing machine, which begins with a string of the form an on the first tape, and a string of the form a™ on the second tape. (n, m € N.) Both heads begin scanning the left-most character of each string. The Turing machine should accept if the number n is an integer multiple of the number m; i.e. there is some integer k such that n=k-m. First, describe the algorithm that your machine uses. Then draw a transition diagram for the machine. To answer properly, your machine should handle the cases when either n or m is zero correctly.

Construct a deterministic two-tape Turing machine, which begins with a string of the form an on the first tape, and a string of the form a™ on the second tape. (n, m € N.) Both heads begin scanning the left-most character of each string. The Turing machine should accept if the number n is an integer multiple of the number m; i.e. there is some integer k such that n=k-m. First, describe the algorithm that your machine uses. Then draw a transition diagram for the machine. To answer properly, your machine should handle the cases when either n or m is zero correctly.

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Similar questions

A = {w € {0,1}* | Iwlo = 2*|wl1} wo denotes the number occurrences of 0 in w and w1 denotes the number occurrences of 1 in w Show that by detail a formal description of a Turing machine M which decides A.
Let A = { <M> IM is a turing machine and IL(M) (>100}. Is A decidable (yes/no)? Prove it
Construct a deterministic two-tape Turing machine, which begins with a string of the form an on the first tape, and a string of the form am on the second tape. (n, m ∈ N.) Both heads begin scanning the left-most character of each string. The Turing machine should accept if the number n is an integer multiple of the number m; i.e. there is some integer k such that n = k · m. First, describe the algorithm that your machine uses. Then draw a transition diagram for the machine. To answer properly, your machine should handle the cases when either n or m is zero correctly.
2) Recall that a final state of a Turing machine T is a state that is not the first state in any of the 5-tuples that make up T. Construct a Turing machine that recognizes the set {0²n1n | n ≥ 0}. Write down 5- tuples for the Turing Machine. (You will not receive credit if you only draw an FSM.)
The 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.
) Build a Turing Machine over the alphabet Σ = {a,b} that accepts all words which do not start andend with the same letter. Show the execution traces with the following input strings:(a) Λ(b) abba(c) baba
Design a Turing machine M that decides the language L = {0n1n|n> 0}.
Let M be a Turing machine and w be a string in the input alphabet of M. Consider the problem A = {(M, w)|M moves left at some point during its computation on w} %3| Show that A is decidable.
2. a. Describe carefully the relationships between the languages below using the operator. That is, your answer should look like A ≤ B ≤ C or A ≤B, A≤ C etc. TD = set of Turing Decidable (recursive) decision problems TA = set of Turing Acceptable (recognizable, recursively enumerable) decision problems NP ' = set of decision problems that have nondeterministic polynomial Turing Machines NPC = set of NP-complete decision problems P = set of decision problems with polynomial solvers
The reverse function maps a string w to wR. Draw a multi-tape Turing machine that computes the reverse of a binary string. That is, given a binary string w as input, your Turing machine should compute wR, write the result to tape 1, and halt.
Suppose that Turing machine M computes the unary number-theoretic function f defined by f(n) = n2 + 6n + 3 and suppose, further, that M is started scanning the leftmost 1 in an unbroken string of six 1s on an otherwise blank tape. Then M will halt scanning the leftmost 1 in an unbroken string of how many 1s?
(b) Suppose that you were asked to design a Turing machine that, when started scan- ning a square on a completely blank tape, writes the string ababbaab on the tape and halts scanning the leftmost symbol of this string. What is the minimal number of states required in order to accomplish this?