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
Turing Machines Theory
What is the difference between Turing Recognizable and Turing Decidable? Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

51
views
theoryofcomputation
turingmachine
decidability
0
votes
0
answers
2
Turing Machines
What does this statement mean? There exists a Turing Machine that enumerates a set S of (encoding of) decider Turing Machines such that S includes Turing Machines that decide infinitely many different decidable languages. Thanks!
asked
Jan 22
in
Theory of Computation
by
Abhipsa Mishra
(
149
points)

18
views
theoryofcomputation
turingmachine
0
votes
1
answer
3
TOCTuring Machine
Consider the given below Turing Machine and identify the correct language accepted: (a+b)*aa(a+b)* b*a(bb*a)*a b*ab*a None of these The answer is given as (1). But I think (3) is correct as well. Can anyone tell me why only (1) is correct.
asked
Jan 20
in
Theory of Computation
by
Anurag Aizen Mukherj
(
29
points)

36
views
theoryofcomputation
turingmachine
testseries
0
votes
0
answers
4
Made Easy test series
Which of the following languages are recursive? L1: { <M,k>  M is a turing machine and { w ∈ L(M) : w ∈ a*b* }  <=k} L2: { <M>  there exists a turing machine M’ such that <M> ≠ <M’> and L(M) = L(M’)
asked
Jan 9
in
Theory of Computation
by
Sambhrant Maurya
Active
(
1.5k
points)

45
views
madeeasytestseries
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
5
Language accepted by this Turing Machine
As per the given solution,B should be the correct answer right why is D given as the correct answer as the machine accepts atleast one b.
asked
Jan 5
in
Theory of Computation
by
sripo
Active
(
1.5k
points)

31
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
regularexpressions
0
votes
0
answers
6
Conversion of multitape TM to single tape TM
asked
Dec 26, 2018
in
Theory of Computation
by
smsubham
Loyal
(
9.1k
points)

43
views
theoryofcomputation
turingmachine
0
votes
0
answers
7
decidablilty
I learned that recursive language are decidable; correct me if I am wrong. However, I have found some arguments that seem to contradict this. These may or may not be correct; please let me know. If a language is an REL (recursive enumerable ... recursive or not *undecidable*. Hence, recursive languages should be undecidablewhich they are not! What is wrong with the above reasoning?
asked
Dec 25, 2018
in
Theory of Computation
by
rballiwal
Active
(
1.1k
points)

43
views
finiteautomata
turingmachine
0
votes
0
answers
8
decidability
please someone explain what are these problems and how to solve these problems for every language with proper explanation? MEMBERSHIP PROBLEM EMPTINESS PROBLEM COMPLETENESS PROBLEM EQUILITY PROBLEM SUBSET PROBLEM DISJOINTNESS PROBLEM IS GIVEN LANGUAGE REGULAR FINITENESS PROBLEM
asked
Dec 24, 2018
in
Theory of Computation
by
Rahul_Rathod_
Junior
(
565
points)

58
views
decidability
#theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
9
Self doubt
I know that for a recursively enumerable language there exists an unrestricted grammar and we have formally defined unrestricted grammar. I want to know whether for every recursive language, there is a grammar or not, and if there is, is there a formal definition of the same?
asked
Dec 20, 2018
in
Theory of Computation
by
subho16
(
129
points)

47
views
theoryofcomputation
turingmachine
grammar
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
10
Zeal Theory of Computation module.
Does the statement given below is true? If a language L is recursive enumerable than there does not exits a TM that could accept complement of L but reject L.
asked
Dec 17, 2018
in
Theory of Computation
by
Ayan21
(
107
points)

54
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
1
answer
11
self doubt  Turing Machines
I have doubt in the following question: Let L(R) be the language represented by regular expression R. Let L(G) be the language generated by CFG G. Let L(M) be the language accepted by a turing machine M. Now, I am getting confused over the keyword “accepted”. What should L(M) be considered? Is it REC or RE?
asked
Dec 17, 2018
in
Theory of Computation
by
Harsh Kumar
Active
(
1k
points)

38
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
12
Turing Machine lecture content stan..
A = { <M,w>  M is a TM that accepts W} what is A’( A complement)? Pls guide : M is a Tm doesn,t accept w, Unable to approach further Source:https://web.stanford.edu/class/archive/cs/cs103/cs103.1134/lectures/20/Small20.pdf
asked
Dec 16, 2018
in
Theory of Computation
by
Learner_jai
Active
(
2.6k
points)

40
views
turingmachine
decidability
+1
vote
1
answer
13
Turing MachineTechtud
If Turing Machine input tape length,restricted to input length, then the language accepted by Turing Machine $A)$ Regular Language $B)$ CFL $C)$ CSL $D)$ None Ans given CSL but I thought it should be regular then what is difference between input restricted and constant size tape? https://gateoverflow.in/26653/gate199117a Plz confirm what is correct?
asked
Dec 13, 2018
in
Theory of Computation
by
srestha
Veteran
(
108k
points)

96
views
turingmachine
theoryofcomputation
0
votes
0
answers
14
ME Test Series #TOC decidability
Consider <M> be the encoding of Turing Machine as string over alphabet $\Sigma$ = {0,1}.Consider L= { <M> M is TM that halt on all input and L(M) = L` for some undecidable language L` . Then L is Decidable and Recursive Decidable and non Recursive Undecidable and Recursive Undecidable and non Recursive
asked
Dec 13, 2018
in
Theory of Computation
by
Hemanth_13
Loyal
(
6.5k
points)

82
views
theoryofcomputation
decidability
madeeasytestseries
turingmachine
0
votes
2
answers
15
Halting problem of TM which recognize recursive languages is undecidable?
Halting problem of Turing machines which recognize recursive languages is undecidable. (True / False)
asked
Dec 10, 2018
in
Theory of Computation
by
gmrishikumar
Active
(
1.7k
points)

88
views
decidability
recursiveandrecursivelyenumerablelanguages
theoryofcomputation
turingmachine
ricetheorem
0
votes
0
answers
16
NIELIT Qtn
Consider the following possible outcomes of executing a Turing machine over a given input. Which of the following outcome is NOT possible? A)TM halts and accepts the input B)TM halts and rejects the input C)TM hangs and accepts the input D)TM never halts.
asked
Dec 2, 2018
in
Theory of Computation
by
pps121
Active
(
1.5k
points)

49
views
turingmachine
theoryofcomputation
0
votes
0
answers
17
Decidability Doubt
$L_1 = \{ \text{<M>}  \ \text{M is a TM, } \text{M}_0 \ \text{is a TM that halts on all inputs and, } \text{M}_0 \in L(M) \}$ ... infinite because $\exists$ infinite number of TM's which accept $\Sigma^*$. Now $L(M)$ is not even RE. If that then how $L_1$ is RE. Please explain both.
asked
Nov 23, 2018
in
Theory of Computation
by
Mk Utkarsh
Boss
(
34.1k
points)

70
views
theoryofcomputation
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
+1
vote
1
answer
18
TOC:LBA halting problem
How halting problem is decidable for LBA ( Linear bounded Automata) it may also hang between left and right moves.
asked
Nov 19, 2018
in
Theory of Computation
by
chauhansunil20th
Active
(
4.8k
points)

64
views
theoryofcomputation
turingmachine
decidability
0
votes
1
answer
19
Turing machine
is multi dimension Tm contain multiple tape or just a single tape, arrange differently?
asked
Nov 18, 2018
in
Theory of Computation
by
shashank joshi
(
69
points)

32
views
turingmachine
theoryofcomputation
0
votes
0
answers
20
Basic Doubt
Correct ans is Type  0. My doubt is LBA is also TM and LBA belongs to type  1 then why ans is not type  1
asked
Nov 17, 2018
in
Theory of Computation
by
Pavan Shetty
(
87
points)

44
views
turingmachine
grammar
type
of
0
votes
0
answers
21
Decidability
asked
Nov 14, 2018
in
Theory of Computation
by
Na462
Loyal
(
8.6k
points)

220
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
22
Decidability
How to distinguish between a problem which is (undecidable) and which is (undecidable but partially decidable); or rather for a given problem how to say in which category it falls?
asked
Nov 14, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

60
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
23
Decidability
Decidable or Undecidable? Given a Turing machine M, a string s and an integer k, M accepts s within k steps. Please elaborate.
asked
Nov 14, 2018
in
Theory of Computation
by
Mizuki
Active
(
1.3k
points)

57
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
24
Recursive language
https://gateoverflow.in/86546/theoryofcomputation22 Total recursive functions are similar to a) Recursive Languages b) Recursive Enumerable languages c) can not relate d) none what is partial,preemptive and total recursive function and how related to Mentioned languages???? "Recursive Enumerable language is range of total recursive function"What it means?
asked
Nov 5, 2018
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
3.9k
points)

35
views
recursiveandrecursivelyenumerablelanguages
turingmachine
theoryofcomputation
0
votes
1
answer
25
Turing machine
What is the meaning of non trivial property related to a language. Please explain with an example.
asked
Oct 30, 2018
in
Theory of Computation
by
Lovejeet Singh
(
29
points)

29
views
turingmachine
theory
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
26
Undecidability
L1:{<M>  there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it nontrivial then please explain why is that so. According to my understanding, nontrivial properties ... it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked
Oct 30, 2018
in
Theory of Computation
by
Swapnil Naik
Active
(
3k
points)

43
views
theoryofcomputation
ricetheorem
turingmachine
decidability
Page:
1
2
3
4
5
6
...
8
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
Official keys are out now.
JEST 2019 MEMORY BASED QUESTION PAPER
Relax... But....
Barc : Arjun Sir
JEST Sample Question
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Agreed. And i see some people who have even...
@
As far as I read from various sources, GOAPS will...
ask the same question of the jest exam on GO and...
@Arjun sir please help us for which question we...
47,910
questions
52,287
answers
182,227
comments
67,728
users