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
+1
vote
2
answers
1
Decidable
1)Let G is CFG. Whether L(G) is CFL. Q)Is it decidable or not? 2)Let G is CFG and unambiguous. Whether L(G) is CFL. Q)Is it decidable or not?
asked
Jun 1
in
Theory of Computation
by
srestha
Veteran
(
86.9k
points)

84
views
decidability
theoryofcomputation
turingmachine
+1
vote
0
answers
2
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)

27
views
theoryofcomputation
turingmachine
0
votes
0
answers
3
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)

21
views
theoryofcomputation
turingmachine
0
votes
0
answers
4
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
(
199
points)

39
views
turingmachine
0
votes
1
answer
5
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
(
5.4k
points)

149
views
decidability
theoryofcomputation
turingmachine
0
votes
0
answers
6
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.1k
points)

99
views
turingmachine
theoryofcomputation
selfdoubt
+1
vote
0
answers
7
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)

37
views
theoryofcomputation
turingmachine
0
votes
0
answers
8
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
Active
(
3.3k
points)

58
views
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
9
Decidability
A turing machine $M$ halts if started with a blank tape. This is undecidable . Can somebody explain this in easiest way possible.
asked
Mar 19
in
Theory of Computation
by
Saurav
Active
(
2.2k
points)

42
views
theoryofcomputation
turingmachine
0
votes
1
answer
10
Decidability
Decide whether or not the state $q$ is ever entered when $M$ is applied to string $w$. Can somebody explain the solution.
asked
Mar 19
in
Theory of Computation
by
Saurav
Active
(
2.2k
points)

51
views
theoryofcomputation
turingmachine
+2
votes
2
answers
11
what type of language
{$<M>\mid M$ is a $TM$ that doesn't accept any even number} what type of language is it? Recursively enumerable Recursive Not recursively enumerable none of the above
asked
Mar 15
in
Theory of Computation
by
Sambit Kumar
Active
(
4k
points)

97
views
decidability
turingmachine
theoryofcomputation
0
votes
1
answer
12
Self Doubt on Decidability
Here in this video https://www.youtube.com/watch?v=8TuLr0cggMY&list=PL601FC994BDD963E4&index=87 professor is explaining that Turing Machine that accept something is recursively enumerable. We would run multiple inputs on turning machine in parallel using ... there are even two strings that are being accepted won't we get to know using the same method ?
asked
Mar 4
in
Theory of Computation
by
Jeevesh
(
155
points)

76
views
theoryofcomputation
turingmachine
decidability
shaisimonson
+1
vote
2
answers
13
Uttrakhand Asst. Professor Exam74
A turing machine crashes If the machine reads all the input characters without traversing some state. If the machine traverses all its states till the input remains If the transitional function is not defined None of the above
asked
Mar 2
in
Others
by
gatecse
Boss
(
18k
points)

37
views
uttarakhandasstprof2018
theoryofcomputation
turingmachine
0
votes
0
answers
14
turing machine
which of the following turing recognizable..????? L1 = {⟨M⟩∣ TM M accepts more than 2 distinct inputs} L2 = {⟨M⟩∣ TM M accepts at most 2 distinct inputs}
asked
Feb 1
in
Theory of Computation
by
rajoramanoj
Active
(
4.3k
points)

61
views
turingmachine
0
votes
1
answer
15
Turing Machine  Membership Problem
Is membership problem for TM decidable or undecidable?
asked
Jan 31
in
Theory of Computation
by
Akash Mishra
Junior
(
999
points)

99
views
turingmachine
theoryofcomputation
0
votes
0
answers
16
Turing machine
Cant we infer that their complexity remains same
asked
Jan 31
in
Theory of Computation
by
Pawan Kumar 2
Active
(
4.5k
points)

38
views
turingmachine
0
votes
0
answers
17
Turing Machine
...................................
asked
Jan 30
in
Theory of Computation
by
Tuhin Dutta
Loyal
(
7.9k
points)

81
views
theoryofcomputation
turingmachine
+1
vote
0
answers
18
Turing machine
Can anybody explain how a Two stack PDA behaves as a TM?
asked
Jan 24
in
Theory of Computation
by
Na462
Active
(
3.3k
points)

35
views
turingmachine
selfdoubt
+1
vote
0
answers
19
What does h(L) = HALT mean or siginify?
While trying to understand homomorphism for recursive proof I came across the following link  https://courses.engr.illinois.edu/cs373/sp2013/Lectures/lec26.pdf Look for proposition 4. In the last point of the proof it is written that h(L) = HALT. What does it mean?  ... : h(0) = 0, h(1) = 1, and h(a) = h(b) = ε$. $h(L) = HALT$ which is undecidable.
asked
Jan 23
in
Theory of Computation
by
tarunmaganti
(
265
points)

31
views
homomorphism
turingmachine
+1
vote
0
answers
20
Rice's Theorem
What is monotonic and nonmonotonic property. Please explain the second postulate of Rice's Theorem.
asked
Jan 23
in
Theory of Computation
by
Sumaiya23
Active
(
1.3k
points)

46
views
ricetheorem
decidability
theoryofcomputation
selfdoubt
turingmachine
+4
votes
0
answers
21
Self doubt
Which of the following statement TRUE & also EXPLAIN WHY... (1) "Power of Turing Machine is Equal to Power of DFA with 2 Stack" (2) "Power of Turing Machine is Equal to Power of DFA with 2 Counter" (3) "Power of Push Down Automata is Equal ... DFA with 1 stack <= DFA with 2 counter <= DFA with 2 stack } (6) Power of Stack is More than power of Counter
asked
Jan 22
in
Theory of Computation
by
Harsh Mehta
Active
(
1.3k
points)

35
views
theoryofcomputation
turingmachine
pushdownautomata
dfa
+1
vote
0
answers
22
Complement of Halting problem
I totally understand the Halting problem, what about complement of halting problem? Is this the set of all those language which never halts? Why complement of halting problem is not re? Proof plz
asked
Jan 21
in
Theory of Computation
by
Na462
Active
(
3.3k
points)

72
views
theoryofcomputation
turingmachine
+2
votes
0
answers
23
made easy test series
A) Decidable REC B) Undecidable and RE C) Undecidable and non RE D) Decidable but RE
asked
Jan 13
in
Theory of Computation
by
yankur9
Active
(
2.2k
points)

45
views
turingmachine
recursiveandrecursivelyenumerablelanguages
+3
votes
0
answers
24
Decidability
a) L is decidable b) L is undecidable c) L is regular d) None of these
asked
Jan 10
in
Theory of Computation
by
Nymeria
(
415
points)

128
views
decidability
contextfreelanguage
turingmachine
reduction
+3
votes
1
answer
25
Turing machine
REC, RE or NOT RE ? L = {<M>  M is a TM and <M> >= 5}
asked
Jan 6
in
Theory of Computation
by
Shivansh Gupta
Active
(
2.4k
points)

150
views
turingmachine
+1
vote
0
answers
26
Test Series
Please explain how to solve this question.!
asked
Jan 2
in
Theory of Computation
by
Anmol_Binani
Junior
(
613
points)

37
views
theoryofcomputation
turingmachine
0
votes
0
answers
27
Turing Machine
A. L is undecidable B. L is decidable C. L is regular. D. None of these. Please explain in detail.
asked
Dec 23, 2017
in
Theory of Computation
by
Shubham Kumar Gupta
Junior
(
537
points)

115
views
turingmachine
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
28
Turing Machine
Let M range over TM description. Consider the set REG={M L(M) is a regular set.} and let the complement of REG is CoREG. Among REG and CoREG which one is R.E. and which one not? ____________________________________________________________________________ I answered both are R.E., but it is incorrect according to given ans. Plz let me know is ans incorrect?
asked
Dec 21, 2017
in
Theory of Computation
by
srestha
Veteran
(
86.9k
points)

60
views
turingmachine
theoryofcomputation
+1
vote
1
answer
29
Self Doubt
The smallest number of states a TM can have?
asked
Dec 16, 2017
in
Theory of Computation
by
Soumya29
Loyal
(
9.9k
points)

55
views
theoryofcomputation
turingmachine
0
votes
0
answers
30
self_doubt
1) L(M) is recognized by a TM having even number of states. 2) L(M) is infinite. whether this language are follow nontrivial property ? Whether this languages are decidable ?.
asked
Dec 15, 2017
in
Theory of Computation
by
Nils
Junior
(
881
points)

68
views
turingmachine
theoryofcomputation
Page:
1
2
3
4
5
6
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 CSA and CDCS written test and interview Experince
IIIT Hyderabad Interview Experience
My failure, Oh wait SUCCESS journey
ALGORITHMS CHECKLIST:
A Failure who got into IISc
Follow @csegate
Gatecse
Recent questions tagged turingmachine
Recent Blog Comments
Sir I didn't get an email for GO classroom, ...
any one with marks less than 125 selected?
Thank you @Arjun Sir, @NamitaAIR1, @Priyanka, ...
Your story is very inspiring for the boys like me ...
So you completed your Btech in 5 yrs? How could ...
36,194
questions
43,647
answers
124,091
comments
42,931
users