please draw Design a Turing machine which, given a positive integer n, determines the value [n/2]. The unarysystem can be used to represent the value of n: for the input, we write n consecutive 0's on theinput tape (surrounded by blanks) and position the read/write head at the leftmost 0. When yourTuring machine halts, the result should appear on the tape-also in unary-with the read/writehead positioned at the leftmost 0 of the result.

Answered: Image /qna-images/answer/6be88e73-9bd5-4187-a767-91fbdb928dde.jpg

Design a Turing machine which, given a positive integer n, determines the value [n/2]. The unary system can be used to represent the value of n: for the input, we write n consecutive 0's on the mput tape (surrounded by blanks) and position the read/write head at the leftmost 0. When your Turing machine halts, the result should appear on the tape-also in unary-with the read/write ead positioned at the leftmost 0 of the result.

Design a Turing machine which, given a positive integer n, determines the value [n/2]. The unary system can be used to represent the value of n: for the input, we write n consecutive 0's on the mput tape (surrounded by blanks) and position the read/write head at the leftmost 0. When your Turing machine halts, the result should appear on the tape-also in unary-with the read/write ead positioned at the leftmost 0 of the result.

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

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.
Our goal is to construct a deterministic one-tape Turing machine that accepts strings over Σ = {a, b} which are palindromes. A palindrome is a string that is the same when read forwards and backwards, for example, abbabba. The Turing machine should operate in the following way: 1. Remember the first character of the input in the state control, and erase this character (replace it with a blank). 2. Move the head to the last (right-most) character of the input. 3. Verify that this character is the same character as the one stored in the state control. If it is, delete this character. If it is a different character, immediately halt and reject. 4. Move the head to the left-most character of the input. 5. If there are any characters left on the input, repeat from step 1. 6. If in step 1 or 3 the tape is empty (i.e. all characters of the input have been erased), halt and accept. First, take a minute to think about the algorithm and convince yourself that it indeed accepts all palindromes…
Define a Turing machine that accepts an integer n as an input string in unary representation, w = { 1 } *, and calculates n mod 3. When the machine halts, the tape should contain only the unary representation of f(w) followed by a zero. For example, ƒ(1111) = 10 or f(11111) 11111) = 0.
Given a Turing machine that accepts a palindrome using two tapes, give the execution trace with the string bbabb, in a step by step manner. The specifications of the TM are as follows: The input alphabet is E = {a,b} and the tape alphabet is I = {a, b, 0}. The set Q of states consists of the following five states: start state; copy w to the second tape w has been copied; head of first tape moves to the left head of first tape moves to the right; head of second tape moves to the left; until now, all tests were positive 1o : 41 : 12 : Jaccept : accept state Ircjcct : reject state The transition function & is specified by the following instructions: Goal goaaRR + qobbRR 91aa → qqaaLN nha + q baLN 9ıbb → q1bbLN q1 Ja → 42C«RN 1J0 → qaccept 4200 → jzauRL 12ab → Treject qzba → greject qzbb → yzibRL 4200 → jaccept
Our goal is to construct a deterministic one-tape Turing machine that accepts strings overΣ = {a, b} which are palindromes. A palindrome is a string which is the same when read forwards andbackwards, for example abbabba. The Turing machine should operate in the following way:1. Remember the first character of the input in the state control, and erase this character (replace it witha blank).2. Move the head to the last (right-most) character of the input.3. Verify that this character is the same character as the one stored in the state control. If it is, deletethis character. If it is a different character, immediately halt and reject.4. Move the head to the left-most character of the input.5. If there are any characters left on the input, repeat from step 1.6. If in step 1 or 3 the tape is empty (i.e. all characters of the input have been erased), halt and accept.
4. The Turing machine M below recognizes the language L = {02" | n ≥ 0}. 0/0, L x/T, L 1/2, R A/A.R A/A, R start- 92 he 24 A/A.R 1/2, R In each of the parts below, give the sequence of configurations that M enters when started on the indicated input string. (a) 00 (b) 000000 Solution: 90 q1 A/A, R: 0/A, R A/A.R ha 0/x, R 0/2, R 95 A/A, L 93x/x, R 0/0, R
In the homework we saw Turing machines for AND, OR, NOT. Here's the definition for XOR. q0 0 B q1 q1 BR q2 д0 1 В q3 q3 BR q4 q4 0 1 q5 q4 1 0 q6 Trace the machine's execution on input 11 by showing the successive configurations. List one configuration per line with a single space separating each part of the configuration. Recall that the parts of the configuration are in the following order: current-state current-head tape-to-left tape- to-right. Use "e" for ɛ and use it only in the "tape-to-left" or "tape-to-right" positions when there is nothing but blanks in those directions. Otherwise list all characters explicitly (and use B for a blank character when needed). initially q0 1 e 1 Step 1 Step 2 Step 3
Computer Science Design a Turing machine that computes the function f(w) = wwR, w ∈ {0, 1}+. Consider that I don't want to know any turing machine that accepts L = {wwR , w ∈ {0, 1}+}. I want to know turing machine that calculates the f(w) = wwR, w ∈ {0, 1}+. If I write to the tape 0011 at initial state, I would like to see 00111100 at the end. Could you please draw states with bubbles and show each input transition expicitly. There is not explicit solution in chegg. As a suggestion drawing of https://turingmachine.io/ could be very helpfull.
Q1. Design a Turing machine to count number of l's in the tape and write the output at beginning of the tape. (Consider that tape has binary numbers only). Q2. Consider the TM defined by M = (Q. E,r, 8, q0, B, F) 8 ( qo, a ) = (q1, a , R) 8 ( qo , b ) = ( q1 , b, R) 8( qo, B) = (q1,B , R) 8(q1, a) = ( qo, a, L) 8(q1, b )= ( qo, b , L) 8 ( qı, B ) = ( qo, B, L) What is the state of TM on input 'ab'?
For a Turing machine M, (M) refers to the binary representation of M. For a Turing machine M, L(M) contains the set of all strings accepted by M. For a Turing machine M and an input x € {0,1}*, Steps(M, x) refers to the number of steps taken by M to execute on x before it halts. Here, one step of execution of M on x = one movement (left or right) of the tape head. For a Turing machine M and an input x = {0,1}*, we define the following: ReachCells(M,x) = {i : M reaches ith tape cell when M is executed on x} Informally, it contains all locations on the tape that are visited when M is ecuted on x. The leftmost location on the tape is the first tape cell, the location next to it is the second tape cell, and so on. A string w₁ is an anagram of w2 if w₁ can be obtained by rearranging the alphabets of w2. Formally, if w₁ is an n length string, wê is called an anagram of w₁ if there exists a permutation à on n elements such that π(w₁) = W2.
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.
Construct a Turing machine (your answer must show all of the 5-tuples involved) that computes n mod 3, where n ≥ 0. You must use unary ones format: 0 is 1, 1 is 11, 2 is 111, and n is n+1 1s.Note that all computations: of n mod m must be either 0 (1), 1 (11), or 2 (111).Be sure to leave the read/write head over the leftmost 1 when done.Verify your Turing machine by giving a step-by-step trace of 2 mod 3 and 7 mod 3.