The Gateway to Computer Science Excellence
For all GATE CSE Questions
Toggle navigation
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
Recent questions tagged turingmachine
Turing Machine Notes
0
votes
2
answers
1
what is number of states in following Turing m/c?
What are the min number of states in Turing machine L={0^n 1^n} As per below link we need 4 states including final state .... But cant we do in 3 states....? For identifying 1st 0 convert it to X(change state from q0 to q1), then ... need q3.....? http://www.eecs.wsu.edu/~ananth/CptS317/Lectures/TuringMachines.pdf Please explain..................
asked
Nov 25, 2014
in
Theory of Computation
by
dhingrak
Active
(
1k
points)

266
views
theoryofcomputation
turingmachine
+5
votes
8
answers
2
Virtual Gate Test Series: Theory Of Computation  Turing Machine
Let $M$ range over Turing machine descriptions, Consider the set $\text{REG = {M  L(M) is a regular set }}$ and let the complement of $REG$ be $CoREG.$ Which of the following is true? REG is recursively enumerable but CoREG is not REG is not recursively enumerable but CoREG is Both are recursively enumerable. None of the above
asked
Nov 18, 2014
in
Theory of Computation
by
Isha Karn
(
459
points)

632
views
theoryofcomputation
turingmachine
virtualgatetestseries
+60
votes
3
answers
3
GATE2014235
Let $\langle M \rangle$ be the encoding of a Turing machine as a string over $\Sigma=\left\{0,1\right\}$ ... $L$ is: decidable and recursively enumerable undecidable but recursively enumerable undecidable and not recursively enumerable decidable but not recursively enumerable
asked
Sep 28, 2014
in
Theory of Computation
by
jothee
Veteran
(
105k
points)

9.4k
views
gate20142
theoryofcomputation
turingmachine
normal
+31
votes
1
answer
4
GATE200489
$L_1$ is a recursively enumerable language over $\Sigma$. An algorithm $A$ effectively enumerates its words as $\omega_1, \omega_2, \omega_3, \dots .$ Define another language $L_2$ over $\Sigma \cup \left\{\text{#}\right\}$ ... are true $S_1$ is true but $S_2$ is not necessarily true $S_2$ is true but $S_1$ is not necessarily true Neither is necessarily true
asked
Sep 19, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

4k
views
gate2004
theoryofcomputation
turingmachine
difficult
+25
votes
4
answers
5
GATE200353
A single tape Turing Machine $M$ has two states $q0$ and $q1$, of which $q0$ is the starting state. The tape alphabet of $M$ is $\{0, 1, B\}$ and its input alphabet is $\{0, 1\}$. The symbol $B$ is the blank symbol used to indicate end of an input string. The ... does not halt on any string in $(00+1)^*$ $M$ halts on all strings ending in a $0$ $M$ halts on all strings ending in a $1$
asked
Sep 17, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

2.8k
views
gate2003
theoryofcomputation
turingmachine
normal
+16
votes
1
answer
6
GATE200214
The aim of the following question is to prove that the language $\{M \mid M$ $\text {is the code of the Turing Machine which, irrespective of the input, halts and outputs a}$ $1\}$ ... is the second step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?
asked
Sep 16, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

1.1k
views
gate2002
theoryofcomputation
decidability
normal
turingmachine
descriptive
difficult
+20
votes
2
answers
7
GATE20017
Let a decision problem $X$ be defined as follows: $X$: Given a Turing machine $M$ over $\Sigma$ and any word $w \in \Sigma$, does $M$ loop forever on $w$? You may assume that the halting problem of Turing machine is undecidable but partially decidable. Show that $X$ is undecidable Show that $X$ is not even partially decidable
asked
Sep 15, 2014
in
Theory of Computation
by
Kathleen
Veteran
(
52.2k
points)

1.3k
views
gate2001
theoryofcomputation
decidability
turingmachine
easy
descriptive
+43
votes
3
answers
8
GATE200354
Define languages $L_0$ and $L_1$ as follows : $L_0 = \{\langle M, w, 0 \rangle \mid M \text{ halts on }w\} $ $L_1 = \{\langle M, w, 1 \rangle \mid M \text{ does not halts on }w\}$ Here $\langle M, w, i \rangle$ is a triplet, whose first component ... $L'$ is not $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable
asked
Sep 8, 2014
in
Theory of Computation
by
Arjun
Veteran
(
425k
points)

7.3k
views
theoryofcomputation
turingmachine
gate2003
difficult
+7
votes
2
answers
9
L(M) = Σ*
$L= \{\langle M \rangle\mid L(M) = \Sigma^*\} $ A. $L$ is RE but $L'$ is not RE B. Both $L$ and $L'$ are RE C. $L$ is not RE but $L'$ is RE D. Both $L$ and $L'$ are not RE
asked
Aug 20, 2014
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

958
views
theoryofcomputation
turingmachine
decidability
difficult
+9
votes
4
answers
10
L(M) is infinite
$L= \{\langle M\rangle \mid L(M)\text{ is infinite}\}$ $L$ is RE but $L'$ is not RE Both $L$ and $L'$ are RE $L$ is not RE but $L'$ is RE Both $L$ and $L'$ are not RE
asked
Aug 20, 2014
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

1.6k
views
theoryofcomputation
turingmachine
decidability
difficult
+18
votes
1
answer
11
Consider the following languages
Consider the following languages $A=\left\{ \langle M\rangle \mid \text{ TM M accepts at most 2 distinct inputs} \right\}$ $B=\left\{\langle M \rangle \mid \text{ TM M accepts more than 2 distinct inputs} \right\}$ Identify the ... Turing recognizable $A$ is not Turing recognizable Both $A$ and $B$ are Turing recognizable Neither $A$ nor $B$ is Turing recognizable
asked
Aug 7, 2014
in
Theory of Computation
by
gatecse
Boss
(
16.8k
points)

3.8k
views
turingmachine
theoryofcomputation
normal
Page:
« prev
1
...
11
12
13
14
15
16
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
Linear Algebra Important Points
GATE 2020
OFFICIAL GATE MOCK TEST RELEASED
IIITH: Winter Research Admissions 2019 (For Spring 2020)
TIFR and JEST exam
Follow @csegate
Recent questions tagged turingmachine
Recent Blog Comments
Arjun sir, plz provide go book through...
@
[email protected]
Can this be updated?
Even In 2019 my 16 questions goes for negative...
i also don't have any pdf, actually, I added the...
i don't have , if you have upload it
50,647
questions
56,508
answers
195,530
comments
100,966
users