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.
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
0
answers
1
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
(
79
points)

35
views
turingmachine
0
votes
1
answer
2
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)

132
views
decidability
theoryofcomputation
turingmachine
0
votes
0
answers
3
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
(
23.9k
points)

83
views
turingmachine
theoryofcomputation
selfdoubt
+1
vote
0
answers
4
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
(
133
points)

34
views
theoryofcomputation
turingmachine
0
votes
0
answers
5
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
(
2.3k
points)

57
views
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
6
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)

40
views
theoryofcomputation
turingmachine
0
votes
1
answer
7
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)

50
views
theoryofcomputation
turingmachine
+2
votes
1
answer
8
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
(
3.5k
points)

84
views
decidability
turingmachine
theoryofcomputation
0
votes
1
answer
9
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
(
147
points)

66
views
theoryofcomputation
turingmachine
decidability
shaisimonson
+1
vote
2
answers
10
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
11
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)

60
views
turingmachine
0
votes
1
answer
12
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)

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

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

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

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

28
views
homomorphism
turingmachine
+1
vote
0
answers
17
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)

45
views
ricetheorem
decidability
theoryofcomputation
selfdoubt
turingmachine
+4
votes
0
answers
18
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)

33
views
theoryofcomputation
turingmachine
pushdownautomata
dfa
+1
vote
0
answers
19
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
(
2.3k
points)

60
views
theoryofcomputation
turingmachine
+2
votes
0
answers
20
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
21
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
(
407
points)

117
views
decidability
contextfreelanguage
turingmachine
reduction
+3
votes
1
answer
22
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)

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

37
views
theoryofcomputation
turingmachine
0
votes
0
answers
24
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
(
533
points)

114
views
turingmachine
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
25
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
(
83.8k
points)

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

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

62
views
turingmachine
theoryofcomputation
0
votes
0
answers
28
Doubt in Rice's Theorem
I have a doubt while understanding step 2 in proof of Rice's Theorem According to my understanding,proof of Rice's theorem as follows ( Please suggest If something is wrong in my understanding) P is a property of languages of TM which is nontrivial ... Same problem as ATM). Can M' take decision in finite time. Please give me some insights to I can understand this point.
asked
Dec 15, 2017
in
Theory of Computation
by
Durgesh Singh
Junior
(
877
points)

88
views
ricetheorem
decidability
theoryofcomputation
selfdoubt
turingmachine
+1
vote
6
answers
29
doubt_theory of computation
If L1 = { an  n ≥ 0 } and L2 = { bn  n ≥ 0 }, Consider then L1 . L2 wil be a) (ab)^n b) a^n b^n c) b^n a^n d)b^m a^n e) { a^m b^n  m ≥ 0, n ≥ 0 } why answer is d why noy b ????
asked
Dec 9, 2017
in
Theory of Computation
by
air1ankit
Active
(
3.2k
points)

146
views
theoryofcomputation
finiteautomata
regularexpressions
madeeasytestseries
turingmachine
0
votes
0
answers
30
self_doubt theory of computation
....... how can we solve question by this table need help
asked
Dec 8, 2017
in
Theory of Computation
by
air1ankit
Active
(
3.2k
points)

55
views
theoryofcomputation
regularexpressions
finiteautomata
turingmachine
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
Selected for M.Tech Computer Science in University of Hyderabad
Gate 2019 suggestion
IIIT Hyderabad interview Experience  2017
Experts please enlighten me!
IIT Gandhinagar MTECH CSE Interview Experience  May 8, 2018
Follow @csegate
Gatecse
Recent questions tagged turingmachine
Recent Blog Comments
That is google form link. You may try ...
As far as I know, the institute is new and ...
Link
1. One offer per round according to your ...
ok . then also answer would remain same , if your ...
35,458
questions
42,704
answers
121,329
comments
42,105
users