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

I forgot my password
All Activity
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous
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
undecidability
Writes Non Blank: Given a turing machine T, does it ever writes a nonblank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then ... is a nontrivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked
3 days
ago
in
Theory of Computation
by
aambazinga
Junior
(
985
points)

9
views
theoryofcomputation
decidability
ricetheorem
turingmachine
0
votes
0
answers
2
Peter Linz Chapter 12.1 Q14
Consider the set of all nstate Turing machines with tape alphabet Γ = {0,1, B}. Give an expression for m(n), the number of distinct Turing machines with this Γ.
asked
5 days
ago
in
Theory of Computation
by
RohitKumarSingh
(
27
points)

9
views
turingmachine
theoryofcomputation
peterlinz
0
votes
1
answer
3
TM that accepts input string x
$D = \left \{ M \mid \ M \text{ is a TM that accepts the input string } x \right \}$ What is complement of D and is it Decidable, Turing recognizable or not Turing recognizable?
asked
Sep 15
in
Theory of Computation
by
Mk Utkarsh
Boss
(
17k
points)

88
views
theoryofcomputation
decidability
turingmachine
+2
votes
1
answer
4
Decidability (Acceptance problem)
Whether the given languages are recursive, recursively enumerable or non RE 1) $L = \left \{ <M>  <M> \ accepts \ all \ strings \ of \ length \ at \ most \ 5 \right \}$ 2) $L = \left \{ <M>  <M> \ accepts \ strings \ of \ length \ at \ most \ 5 \right \}$
asked
Sep 14
in
Theory of Computation
by
Mk Utkarsh
Boss
(
17k
points)

112
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
5
Turing Machine (Peter Linz)
How $H'$ ending with initial state $q_{0}$? Plz explain with the figure given
asked
Sep 13
in
Theory of Computation
by
srestha
Veteran
(
96.1k
points)

3
views
theoryofcomputation
peterlinz
turingmachine
selfdoubt
0
votes
0
answers
6
Turing Machine (Peter Linz)
Need some explanation on these two states. How from first state we can go to the last state as shown the symbol?
asked
Sep 13
in
Theory of Computation
by
srestha
Veteran
(
96.1k
points)

14
views
theoryofcomputation
peterlinz
turingmachine
selfdoubt
0
votes
0
answers
7
Doubt in Turing Machines
Consider the following T.M. {Note Σ ={a,b} ⌈ = {*,a,b} Δ = empty cells of Tape. Which of the following string does not accepted by T.M. ? (i) aabbaa (ii) ε (iii) aabb
asked
Sep 11
in
Theory of Computation
by
goluabhinan
(
77
points)

19
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
Turing machine
Consider <M> be the encoding of a TM as a string over the alphabet {0,1}. Consider L = {<M>  M is a TM that halts on all the input and L(M) = L' for some Undecidable language L' } then L is ? A. Decidable and Recursive B. Decidable and Non recursive C. Undecidable and RE D. Undecidable and Non RE
asked
Sep 9
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

19
views
turingmachine
recursiveandrecursivelyenumerablelanguages
decidability
0
votes
0
answers
9
TOC Undecidability
asked
Sep 9
in
Theory of Computation
by
sidlewis
(
327
points)

21
views
theoryofcomputation
decidability
ricetheorem
contextfreelanguages
turingmachine
0
votes
0
answers
10
Difference between computability and decidability
asked
Sep 7
in
Theory of Computation
by
surbhijain93
(
129
points)

29
views
decidability
turingmachine
0
votes
0
answers
11
test series
Can someone explain this problem?
asked
Sep 4
in
Theory of Computation
by
Kalpataru Bose
(
439
points)

65
views
testseries
madeeasytestseries
testbooktestseries
theoryofcomputation
decidability
turingmachine
acetestseries
0
votes
0
answers
12
Gateoverflow questions
I am confused between the answer of these 2 questions. Here the questions are almost similar, in both of them we need to find out which ones are decidable but both of them have different answers and I am not able to decide which one is correct. https://gateoverflow.in/82703/tocturingmachine https://gateoverflow.in/98850/turingmachine
asked
Sep 2
in
Theory of Computation
by
Swapnil Naik
Junior
(
831
points)

27
views
turingmachine
decidability
0
votes
0
answers
13
Decidability
Ans. D
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

23
views
decidability
theoryofcomputation
turingmachine
0
votes
1
answer
14
Turing Decidable
asked
Sep 2
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

44
views
theoryofcomputation
turingmachine
decidability
0
votes
1
answer
15
Language Represented by TM
Ans. C
asked
Aug 30
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

32
views
theoryofcomputation
turingmachine
0
votes
0
answers
16
Doubt TOC
which of the following is/are decidable? 1)for some input if an arbitrary TM makes 5 moves. 2) whether an arbitary TM halts within 5 steps 3) whether an arbitary TM prints some non blank character 4)the set of codes for TM that never make a left move. 5)an arbitrary TM halts after 100 steps 6)a TM prints a specific letter 7) a turing machine computes the product of two numbers.
asked
Aug 24
in
Theory of Computation
by
Sumit Singh Chauhan
Active
(
1.3k
points)

35
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
17
TOC, REL
Set of all languages that are not Recursively Enumerable is uncountable. This is true. WHY?
asked
Aug 16
in
Theory of Computation
by
manisha11
Junior
(
833
points)

12
views
theoryofcomputation
turingmachine
+1
vote
1
answer
18
TOC decidability
Let <M> be the encoding of Turing machine as a string over Σ = {0, 1}. Let L = {<M>  M is TM on input w will visit some state P}. The language L is (a) Decidable (b) Undecidable but partially decidable (c) Undecidable and not even partially decidable (d) Not a decision problem
asked
Aug 10
in
Theory of Computation
by
manisha11
Junior
(
833
points)

46
views
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
0
answers
19
Theory Of Computation , Decidability
9. Let L ≤ ML’ denote the language L is mapping reducible (many to one reducible) to language L’. Which one of the following is True? (a) If L ≤ pL’ and L’ is semidecidable then L is semidecidable. (b) If L ≤ pL’ and L is RE then L’ is RE. (c) If L ≤ pL’ and L is decidable then L’ decidable. (d) If L ≤ pL’ and L is recursive. Solution: Option (a) PLEASE Explain
asked
Aug 10
in
Theory of Computation
by
manisha11
Junior
(
833
points)

24
views
theoryofcomputation
decidability
turingmachine
0
votes
1
answer
20
Gate overflow old question
Referring to the question https://gateoverflow.in/227957/selfdoubt If the TM accepts exactly 100 strings can we not design a FA for it which would make it a regular language?
asked
Jul 31
in
Theory of Computation
by
Vikas Verma
Active
(
1.4k
points)

49
views
theoryofcomputation
turingmachine
finiteautomata
+1
vote
0
answers
21
self doubt
Given a TM, M accepts 100 strings. Is it decidable, semi decidable or fully undecidable??
asked
Jul 24
in
Theory of Computation
by
Vegeta
(
289
points)

93
views
decidability
theoryofcomputation
turingmachine
+3
votes
1
answer
22
Decidability Vs SemiDecidability Vs Undecidability Self Doubt
asked
Jul 12
in
Theory of Computation
by
Balaji Jegan
Active
(
1.7k
points)

587
views
decidability
theoryofcomputation
turingmachine
+1
vote
2
answers
23
Decidable
1)Let G be CFG. Whether L(G) is CFL. Q)Is it decidable or not? 2)Let G be CFG and unambiguous. Whether L(G) is CFL. Q)Is it decidable or not?
asked
Jun 1
in
Theory of Computation
by
srestha
Veteran
(
96.1k
points)

138
views
decidability
theoryofcomputation
turingmachine
+1
vote
0
answers
24
Introduction to Computer Theory
Construct a Turing Machine to compute the following function: $$f(x,y) = 1 \text{ if length(x) > length(y)} \\ =0 \text{ otherwise}{}$$ where $x$ and $y$ are strings over the alphabet set $\{a b\}$. The output should be written on the tape after a \$. For example, if input is $\$abaab\$aaba$, then output should be $\$abaab\$aaba\$1$
asked
May 30
in
Theory of Computation
by
The Capricorn
(
147
points)

37
views
theoryofcomputation
turingmachine
0
votes
0
answers
25
Introduction to Computer Theory
Construct a Turing Machine that computes length of a given input string. For Example, if the input is $abbaab$, the output should be $abbaab00110$.
asked
May 28
in
Theory of Computation
by
The Capricorn
(
147
points)

34
views
theoryofcomputation
turingmachine
0
votes
0
answers
26
Turing Machine
Design a TM that accepts strings over the alphabet{a,b} i)Of even length ii)containing the substring "abababa" iii)not containing two consecutive zeros
asked
Apr 28
in
Theory of Computation
by
Sourav_35
(
201
points)

47
views
turingmachine
0
votes
1
answer
27
TOC Decidability Theory
Which of the following problems is solvable? a) Writing a universal Turing machine b) Determining if an arbitrary Turing machine is a Universal Turing Machine c) Determining if a universal Turing Machine can be written in fewer than k instructions for some k d) Determining if a universal Turing Machine and some input will halt
asked
Apr 25
in
Theory of Computation
by
gauravkc
Loyal
(
6.4k
points)

194
views
decidability
theoryofcomputation
turingmachine
0
votes
0
answers
28
Codes of Turing Machine
As codes of turing machines are unique for a given turing machine,Say no i have two turing machines ,one for even a's and other for odd a's over the input a,b. Now both these machines will have same transition function but ... state and codes of turing machine is the representation of transition function,so how do these two turing machines will have different codes?
asked
Apr 11
in
Theory of Computation
by
rahul sharma 5
Boss
(
24.7k
points)

132
views
turingmachine
theoryofcomputation
selfdoubt
+1
vote
0
answers
29
Introduction to Computer Theory
Construct a Turing Machine for the language of all strings of this form $L= \{(a^m)(b^n) \mid {\text{n is a multiple of m, and m belongs to N}\}}$
asked
Apr 5
in
Theory of Computation
by
The Capricorn
(
147
points)

44
views
theoryofcomputation
turingmachine
0
votes
0
answers
30
Turing Machine
$L(M)$ = Contains atmost $10$ Strings ? Is it Recursively enumerable ? According to me its Not. Because according to Rices theorem there exist a non monotonic property which makes it Non recognizable. because $T_{yes}$ = $\phi$(i.e. NULL) and $T_{no} = (a+b)^* $ say $\Sigma = \{a,b\} $ and $T_{yes}$ is proper subset of $T_{no}$ Hence its not Recursively enumerable right?
asked
Apr 4
in
Theory of Computation
by
Na462
Loyal
(
5.7k
points)

67
views
turingmachine
recursiveandrecursivelyenumerablelanguages
Page:
1
2
3
4
5
6
7
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
kvs pgt
Algorithms GO Classroom
Programming and DS GO Classroom
Discrete Mathematics GO Classroom
Digital Logic GO Classroom
Follow @csegate
Gatecse
Recent questions tagged turingmachine
Recent Blog Comments
@Arjun sir how to remove such post? should i hide...
[email protected]
.Plz do share @Sanjay sharma
Please post it as question
This is blog area post it as question
[email protected]
39,778
questions
46,781
answers
140,752
comments
58,672
users