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
Turing machine
is multi dimension Tm contain multiple tape or just a single tape, arrange differently?
asked
1 hour
ago
in
Theory of Computation
by
shashank joshi
(
47
points)

4
views
turingmachine
theoryofcomputation
0
votes
0
answers
2
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
17 hours
ago
in
Theory of Computation
by
Pavan Shetty
(
53
points)

17
views
turingmachine
grammar
type
of
0
votes
0
answers
3
Decidability
asked
3 days
ago
in
Theory of Computation
by
Na462
Loyal
(
6.9k
points)

131
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
4
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
4 days
ago
in
Theory of Computation
by
Mizuki
Active
(
1k
points)

23
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
1
answer
5
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
4 days
ago
in
Theory of Computation
by
Mizuki
Active
(
1k
points)

19
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
6
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
in
Theory of Computation
by
Abhisek Tiwari 4
Active
(
1.5k
points)

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

15
views
turingmachine
theory
theoryofcomputation
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
8
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 are ... 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
in
Theory of Computation
by
Swapnil Naik
Active
(
2k
points)

22
views
theoryofcomputation
ricetheorem
turingmachine
decidability
0
votes
0
answers
9
Decidability Doubt
A recursive language is empty or a recursive language contains all strings over sigma*. Why this problem is undecidable?
asked
Oct 29
in
Theory of Computation
by
aditi19
Active
(
1.2k
points)

24
views
decidability
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
10
Ace Book
asked
Oct 28
in
Theory of Computation
by
abhishek1995_cse
(
155
points)

26
views
contextfreelanguage
regularlanguages
theoryofcomputation
turingmachine
0
votes
0
answers
11
Turing Machine
A turing machine $\left \langle M,w,i \right \rangle$ where $M$ is TM , $w$ is string and $i$ is bit. Is the bit $i$ is encoding at last of the string $w$ or at first?
asked
Oct 12
in
Theory of Computation
by
srestha
Veteran
(
101k
points)

22
views
turingmachine
theoryofcomputation
0
votes
0
answers
12
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
Sep 21
in
Theory of Computation
by
aambazinga
Active
(
1.5k
points)

24
views
theoryofcomputation
decidability
ricetheorem
turingmachine
0
votes
0
answers
13
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
Sep 19
in
Theory of Computation
by
RohitKumarSingh
(
27
points)

17
views
turingmachine
theoryofcomputation
peterlinz
0
votes
1
answer
14
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
(
23.6k
points)

112
views
theoryofcomputation
decidability
turingmachine
+2
votes
1
answer
15
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
(
23.6k
points)

143
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
16
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
(
101k
points)

8
views
theoryofcomputation
peterlinz
turingmachine
selfdoubt
0
votes
0
answers
17
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
(
101k
points)

23
views
theoryofcomputation
peterlinz
turingmachine
selfdoubt
0
votes
0
answers
18
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
(
101
points)

24
views
theoryofcomputation
turingmachine
recursiveandrecursivelyenumerablelanguages
0
votes
0
answers
19
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
(
6.9k
points)

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

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

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

92
views
testseries
madeeasytestseries
testbooktestseries
theoryofcomputation
decidability
turingmachine
acetestseries
0
votes
0
answers
23
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
Active
(
2k
points)

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

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

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

33
views
theoryofcomputation
turingmachine
0
votes
0
answers
27
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.4k
points)

48
views
theoryofcomputation
decidability
turingmachine
0
votes
0
answers
28
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
Active
(
1.2k
points)

12
views
theoryofcomputation
turingmachine
+1
vote
1
answer
29
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
Active
(
1.2k
points)

58
views
decidability
recursiveandrecursivelyenumerablelanguages
turingmachine
0
votes
0
answers
30
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
Active
(
1.2k
points)

27
views
theoryofcomputation
decidability
turingmachine
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
Basic LaTeX guide
IIT Madras Phd
Databases GO Classroom
Happy Birthday Sir Arjun
NIELIT EXAM DATE 2018
Follow @csegate
Gatecse
Recent questions tagged turingmachine
Recent Blog Comments
Sir for final year student who have exam in...
I guess you meant while chasing :) Anyway those...
I'll write a post on how to best...
@Gaurav Go through all the previous yr questions,...
42,572
questions
48,562
answers
155,429
comments
63,581
users