The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
GATE Overflow
Facebook Login
or
Email or Username
Password
Remember
Login
Register

I forgot my password
Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Prev
Blogs
New Blog
Exams
First time here? Checkout the
FAQ
!
x
×
Close
Use the google search bar on side panel. It searches through all previous GATE/other questions. For hardcopy of previous year questions please see
here
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
1
answer
1
Made Easy Test Series:TOCTuring Machine
$P_{1}:$ {$<M>M $ is a TM that accepts atleast $2$ strings of different length} $P_{2}:$ {$<M>M $ is a TM and there exists an input whose length less than $100,$ on which $M$ halts } The number of problem which is $RE$ but not $REC$ _____________
asked
Apr 30
in
Theory of Computation
by
srestha
Veteran
(
114k
points)

52
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
2
Self doubt Turing machine
$1)L=M$ is a turing machine $M$ accepts two strings of different length $2)L=M$ is a turing machine $M$ accepts atleast two strings of different length Which one RE? Which one REC? How to compute the different length string?
asked
Apr 13
in
Theory of Computation
by
srestha
Veteran
(
114k
points)

18
views
turingmachine
theoryofcomputation
0
votes
0
answers
3
Ullman (TOC) Edition 3 Exercise 8.3 Question 3 (Page No. 343)
Design a subroutine to move a TM head from its current position to the right, skipping overall $0's,$ until reaching a $1$ or a blank. If the current position does not hold $0,$ then the TM should halt. You may assume that there are no tape ... a TM that accepts all strings of $0's$ and $1's$ that do not have two $1's$ in a row$.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

30
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
4
Ullman (TOC) Edition 3 Exercise 8.3 Question 2 (Page No. 343)
A common operation in Turingmachine programs involves $"$shifting over$".$ Ideally, we would like to create an extra cell at the current head position, in which we could store some character. However, we cannot edit ... perform this operation. Hint $:$ Leave a special symbol to mark the position to which the head must return.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

23
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
5
Ullman (TOC) Edition 3 Exercise 8.3 Question 1 (Page No. 343)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$ Redesign your Turing machines from Exercise $8.2$ to take advantage of the programming techniques.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

21
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
6
Ullman (TOC) Edition 3 Exercise 8.2 Question 5 (Page No. 337)
Consider the Turing machine $M=(\{q_{0},q_{1},q_{2},q_{f}\},\{0,1\},\{0,1,B\},\delta,q_{0},B,\{q_{f}\})$ Informally but clearly describe the language $L(M)$ if $\delta$ consists of the following sets of rules$:$ ...
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

18
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
7
Ullman (TOC) Edition 3 Exercise 8.2 Question 4 (Page No. 336)
In this exercise we explore the equivalence between function computation and language recognition for Turing machines. For simplicity, we shall consider only functions from nonnegative integers to nonnegative integers, but the ideas of this problem ... $?$ If not, explain how you could modify the construction to make it work.
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

30
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
8
Ullman (TOC) Edition 3 Exercise 8.2 Question 3 (Page No. 336)
Design a Turing machine that takes as input a number $N$ and adds $1$ to it in binary. To be precise, the tape initially contains a $ \$ $ followed by $N$ in binary. The tape head is initially scanning the $ \$ $ in state ... $ of your TM when given input $\$111.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

27
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
9
Ullman (TOC) Edition 3 Exercise 8.2 Question 2 (Page No. 335  336)
Design Turing machines for the following languages$:$ $\text{The set of strings with an equal number of 0's and 1's.}$ $\{a^{n}b^{n}c^{n}n\geq 1\}.$ $\{ww^{R}\text{w is any string of 0's and 1's\}}.$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

17
views
ullman
theoryofcomputation
turingmachine
0
votes
1
answer
10
Made Easy Test Series : TOC Turing Machine
Consider $\left \langle M \right \rangle$ be the encoding of a turing machine as a string over alphabet $\Sigma =\left \{ 0,1 \right \}$. Consider $D=${$\left \langle M \right \rangle$ $M$ is TM that halt on all ... NonRecursive $(C)$ Recursively enumerable $(D)$ Not Recursively enumerable My question is Is it not a Halting Problem they are asking for?
asked
Apr 13
in
Theory of Computation
by
srestha
Veteran
(
114k
points)

186
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
11
Ullman (TOC) Edition 3 Exercise 8.2 Question 1 (Page No. 335)
Show the $ID's$ of the Turing machine of Fig.$8.9$ if the input tape contains$:$ $00$ $000111$ $00111$
asked
Apr 13
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

24
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
12
Ullman (TOC) Edition 3 Exercise 8.1 Question 1 (Page No. 324)
Give reductions from the helloworld problem to each of the problems below. Use the informal style of this section for describing plausible program transformations, and do not worry about the real limits such as maximum file size or ... $?$
asked
Apr 11
in
Theory of Computation
by
Lakshman Patel RJIT
Boss
(
36.4k
points)

14
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
13
Peter Linz Edition 5 Exercise 9.3 Question 1 (Page No. 248)
Consider the set of machine language instructions for a computer of your choice. Sketch how the various instructions in this set could be carried out by a Turing machine.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

13
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
14
Peter Linz Edition 5 Exercise 9.2 Question 8,9,10 (Page No. 245)
$\text{Exercise 8}:$ Give an implementation of the macroinstruction $\text{searchright} (a,q_i,q_j),$ ... $a$ by a blank. If the input contains no $a$, replace the rightmost nonblank symbol by a $b.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
15
Peter Linz Edition 5 Exercise 9.2 Question 7 (Page No. 245)
Sketch the construction of a Turing machine that can perform the addition and multiplication of positive integers $x$ and $y$ given in the usual decimal notation.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
16
Peter Linz Edition 5 Exercise 9.2 Question 6 (Page No. 245)
Suggest a method for representing rational numbers on a Turing machine, then sketch a method for adding and subtracting such numbers.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
17
Peter Linz Edition 5 Exercise 9.2 Question 5(e) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^n : n\text{ is a prime number}\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
18
Peter Linz Edition 5 Exercise 9.2 Question 5(d) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}$. For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{a^nb^m : m = n^2,n\geq1\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
19
Peter Linz Edition 5 Exercise 9.2 Question 5(c) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $\text{The complement of the language in }L = \{ww^R\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

17
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
20
Peter Linz Edition 5 Exercise 9.2 Question 5(b) (Page No. 245)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{w_1w_2: w_1 \neq w_2: w_1 = w_2\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
21
Peter Linz Edition 5 Exercise 9.2 Question 5(a) (Page No. 244)
Provide a “highlevel” description for Turing machines that accept the following languages on $\{a,b\}.$ For each problem, define a set of appropriate macroinstructions that you feel are reasonably easy to implement. Then use them for the solution. $L = \{ww^R\}.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
22
Peter Linz Edition 5 Exercise 9.2 Question 4 (Page No. 244)
Use a block diagram to sketch the implementation of a function f defined for all $w_1,w_2,w_3\in \{1\}^+$ by $f(w_1,w_2,w_3) = i,$ where $i$ is such that $w_i = \text{max}(w_1,w_2,w_3)$ if no two $w’s$ have the same length, and $i=0$ otherwise.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
23
Peter Linz Edition 5 Exercise 9.2 Question 3(d) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n!,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
24
Peter Linz Edition 5 Exercise 9.2 Question 3(e) (Page No. 244)
Using adders, subtracters, comparers, copiers or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^{n!},$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
25
Peter Linz Edition 5 Exercise 9.2 Question 3(c) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = 2^n,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
26
Peter Linz Edition 5 Exercise 9.2 Question 3(b) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n^5,$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
27
Peter Linz Edition 5 Exercise 9.2 Question 3(a) (Page No. 244)
Using adders, subtracters, comparers, copies or multipliers, draw block diagrams for Turing machines that compute the functions for all positive integers $n$ $f(n) = n(n+1),$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

3
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
28
Peter Linz Edition 5 Exercise 9.2 Question 2 (Page No. 244)
Establish a convention for representing positive and negative integers in unary notation. With your convention, sketch the construction of a subtracter for computing $xy.$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
29
Peter Linz Edition 5 Exercise 9.2 Question 1 (Page No. 244)
$\text{Example}:$ Design a Turing machine that multiples two positive integers in unary notation. Write out the complete solution to Example.
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
30
Peter Linz Edition 5 Exercise 9.1 Question 19 (Page No. 240)
You may have noticed that all the examples in these sections had only one final state. Is it generally true that for any Turing machine, there exists another one with only one final state that accepts the same language$?$
asked
Apr 9
in
Theory of Computation
by
Rishi yadav
Boss
(
11k
points)

5
views
peterlinz
theoryofcomputation
turingmachine
proof
Page:
1
2
3
4
5
6
...
13
next »
Quick search syntax
tags
tag:apple
author
user:martin
title
title:apple
content
content:apple
exclude
tag:apple
force match
+apple
views
views:100
score
score:10
answers
answers:2
is accepted
isaccepted:true
is closed
isclosed:true
Recent Posts
IISc Intelligent Systems RA interview experience
COAP Round 2 may begin at 5PM Today
IIT Kanpur MS Interview experience
My GATE preparation and what you can learn from it
IIT Bombay RA (2019) Programming Questions
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Rank 464. OBC
Thanks for sharing your exp Naveen and congrats...
what is cross word question exactly
how you prepared for such tricky questions
please anyone who has idea of this reply
49,456
questions
53,658
answers
186,156
comments
70,919
users