The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
0
answers
1
Self Doubt: Decidability
L={<M1,M2> such that L(M1)<L(M2)} is it recursive enumerable? here L(M1) < L(M2) signifies language L(M1) is reducible to L(M2) .
asked
15 hours
ago
in
Theory of Computation
by
ajaysoni1924
Boss
(
10.1k
points)

14
views
thoery
theoryofcomputation
turingmachine
decidability
recursiveandrecursivelyenumerablelanguages
+1
vote
0
answers
2
UGCNETJune2019II79
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
413k
points)

13
views
ugcnetjune2019ii
decidability
turingmachine
0
votes
0
answers
3
UGCNETJune2019II80
asked
Jul 2
in
Theory of Computation
by
Arjun
Veteran
(
413k
points)

18
views
ugcnetjune2019ii
turingmachine
0
votes
0
answers
4
Question related to Linear bound automata
How do a^n! and a^n^2 come under machine Linear Bound Automata? I know that LBA is a reduced form of standard Turing Machine where tape is restricted to be used for inputs(for also input of infinite length) But can anyone help me by designing a ... stack which may help for comparing any two of them only i.e, either for a & b or b&c or a&c).
asked
Jun 12
in
Theory of Computation
by
Akash Kumar Roy
Junior
(
529
points)

26
views
theoryofcomputation
linearboundautomata
turingmachine
0
votes
1
answer
5
ace academy test series toc turing machine
asked
May 28
in
Theory of Computation
by
hitesh159
(
141
points)

76
views
theoryofcomputation
turingmachine
acetestseries
+1
vote
1
answer
6
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
(
112k
points)

81
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
7
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
(
112k
points)

24
views
turingmachine
theoryofcomputation
0
votes
0
answers
8
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
(
41.4k
points)

32
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
9
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
(
41.4k
points)

24
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
10
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
(
41.4k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
11
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
(
41.4k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
12
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
(
41.4k
points)

32
views
ullman
theoryofcomputation
turingmachine
descriptive
0
votes
0
answers
13
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
(
41.4k
points)

30
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
14
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
(
41.4k
points)

18
views
ullman
theoryofcomputation
turingmachine
0
votes
1
answer
15
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
(
112k
points)

206
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
16
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
(
41.4k
points)

25
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
17
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
(
41.4k
points)

14
views
ullman
theoryofcomputation
turingmachine
0
votes
0
answers
18
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
(
10.6k
points)

15
views
peterlinz
theoryofcomputation
turingmachine
difficult
0
votes
0
answers
19
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
(
10.6k
points)

6
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
20
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
(
10.6k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
21
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
(
10.6k
points)

19
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
22
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
(
10.6k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
23
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
(
10.6k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
24
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
(
10.6k
points)

27
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
25
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
(
10.6k
points)

7
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
26
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
(
10.6k
points)

4
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
27
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
(
10.6k
points)

2
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
28
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
(
10.6k
points)

19
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
29
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
(
10.6k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
0
votes
0
answers
30
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
(
10.6k
points)

11
views
peterlinz
theoryofcomputation
turingmachine
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
How to prepare for GATE with a fulltime job??
Interview Experience at IISc
All subject Gate notes from Standard Books!!
My journey from Wipro to an IISc student  GATE 2019
Interview Experience at IITPalakkad
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
https://drive.google.com/open?id=1lzQpNHE4Phvo9JFA...
Sir, I will say the "
THE PURPOSE OF...
Can rely upon these notes?
where is the test link for this week(july 1521)?
49,808
questions
54,474
answers
188,226
comments
74,352
users