Login
Register
@
Dark Mode
Profile
Edit my Profile
Messages
My favorites
Register
Activity
Q&A
Questions
Unanswered
Tags
Subjects
Users
Ask
Previous Years
Blogs
New Blog
Exams
Dark Mode
Turing Machine Notes
Recent questions tagged turing-machine
0
votes
2
answers
481
TM Decidablity
Is it decidable whether a given Turing machine accepts a CFL? give some facts or exp to prove your answer .
manu90
asked
in
Theory of Computation
Jun 18, 2016
by
manu90
1.5k
views
theory-of-computation
turing-machine
3
votes
1
answer
482
ISI2012-PCB-CS-3
Design a Turing machine that recognizes the unary language consisting of all strings of 0’s whose length is a power of 2, i.e., $L = \{0^{2n} \mid n \geq 0\}$
go_editor
asked
in
Theory of Computation
Jun 2, 2016
by
go_editor
921
views
descriptive
isi2012-pcb-cs
theory-of-computation
turing-machine
0
votes
2
answers
483
is pushdown automata less powerful than Turing machines ?
Amit Sharma
asked
in
Theory of Computation
Jun 1, 2016
by
Amit Sharma
6.4k
views
theory-of-computation
turing-machine
pushdown-automata
3
votes
2
answers
484
Turing machines decidability problem
Consider the following two decision problems Whether a Turing Machine takes more than 481 steps on input epsilon? Whether a Turing Machine accepts the null string epsilon? Which of the following statements is true ? Problem a is decidable but b is not Problem a is undecidable but b is decidable Both a and b are decidable Both a and b are undecidable
biranchi
asked
in
Theory of Computation
May 24, 2016
by
biranchi
1.6k
views
theory-of-computation
turing-machine
decidability
2
votes
2
answers
485
Virtual Gate Test Series: Theory Of Computation - Decidability
Here My explanation is : I. We run TM for 1,2,3,4,5....n if it stops in any of these then yes otherwise no II. We run TM for n steps if it stops yes otherwise no III. We run TM for n, n+1, n+2.... ... can say yes but if do not halt we can't say anything because we have to run it infinite number of times Is my explanation correct?
Sumit1311
asked
in
Theory of Computation
Jan 22, 2016
by
Sumit1311
866
views
theory-of-computation
turing-machine
decidability
virtual-gate-test-series
1
vote
1
answer
486
Turing machine
Construct TM tht accept al string of a's and b's where each string is even length palindrome.(here qf is final state, q0 initial state and B blank symbol) Right now this TM accepting all palindrome string. If pink arrow term is replaced with halt then this ... this TM will accept odd length palindrome only. I am not sure if I m doing it right. Plz let me know my mistakes
khushtak
asked
in
Theory of Computation
Jan 15, 2016
by
khushtak
8.6k
views
turing-machine
theory-of-computation
1
vote
2
answers
487
Equivalence of Turing Machines.
Consider the following two arguments: "For every non deterministic TM M1 there exists an equivalent deterministic TM M2 recognizing the same language." "Equivalence of two Turing Machines is undecidable" These two arguments seem a bit contradicting. What can be concluded from these two arguments?
अनुराग पाण्डेय
asked
in
Theory of Computation
Jan 6, 2016
by
अनुराग पाण्डेय
3.4k
views
turing-machine
theory-of-computation
4
votes
2
answers
488
TM
Consider the following turning machine (where,,$\$ $ is represent accept the string). If the string is $01010$ then what will be the output? $10100$ $10101$ $10110$ $10011$
resuscitate
asked
in
Theory of Computation
Dec 5, 2015
by
resuscitate
1.9k
views
turing-machine
4
votes
1
answer
489
Number of symbols necessary to simulate a TM
The number of symbols necessary to simulate a TM with $m$ symbols and $n$ states is ? $m+n$ $8mn+4m$ $mn$ $4mn+m$
monali
asked
in
Theory of Computation
Nov 2, 2015
by
monali
6.7k
views
turing-machine
6
votes
1
answer
490
Which of the folowing are R.E
Which of the following problem(s) is/are Recursively enumerable or its complement is recursively enumerable? I. The language of all Turing machines that accept nothing. II. The language of all Turing machines that accept everything. III. The language of all CFG’s that are ambiguous.
Mari Ganesh Kumar
asked
in
Theory of Computation
Oct 17, 2015
by
Mari Ganesh Kumar
1.9k
views
turing-machine
recursive-and-recursively-enumerable-languages
2
votes
1
answer
491
ISRO2014-59
Which of the following is FALSE with respect to possible outcomes of executing a Turing Machine over a given input? it may halt and accept the input it may halt by changing the input it may halt and reject the input it may never halt
ajit
asked
in
Theory of Computation
Sep 23, 2015
by
ajit
4.8k
views
isro2014
theory-of-computation
turing-machine
0
votes
1
answer
492
Relationship between Problems and Languages
Is there a one to one correspondence between problems and languages? we interchangeably use these while discussing decidabilility and turing machines
Anurag_s
asked
in
Theory of Computation
Aug 13, 2015
by
Anurag_s
374
views
turing-machine
decidability
24
votes
1
answer
493
Which of the following languages are Recursively Enumerable language?
Which of the following languages are Recursively Enumerable language? $\{\langle M \rangle \mid M$ is a TM and there exist an input whose length is less than 100, on which $M$ halts$\}$ ... $\{ \langle M1, M2, M3 \rangle \mid L(M1) = L(M2) \cup L(M3) \}$ All of these
Vikrant Singh
asked
in
Theory of Computation
Jan 27, 2015
by
Vikrant Singh
5.1k
views
turing-machine
recursive-and-recursively-enumerable-languages
theory-of-computation
0
votes
2
answers
494
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..................
dhingrak
asked
in
Theory of Computation
Nov 25, 2014
by
dhingrak
565
views
theory-of-computation
turing-machine
91
votes
5
answers
495
GATE CSE 2014 Set 2 | Question: 35
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
go_editor
asked
in
Theory of Computation
Sep 28, 2014
by
go_editor
27.7k
views
gatecse-2014-set2
theory-of-computation
turing-machine
normal
52
votes
3
answers
496
GATE CSE 2004 | Question: 89
$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\}$ ... $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
Kathleen
asked
in
Theory of Computation
Sep 18, 2014
by
Kathleen
11.0k
views
gatecse-2004
theory-of-computation
turing-machine
difficult
41
votes
5
answers
497
GATE CSE 2003 | Question: 53
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 ... 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$
Kathleen
asked
in
Theory of Computation
Sep 17, 2014
by
Kathleen
11.8k
views
gatecse-2003
theory-of-computation
turing-machine
normal
24
votes
1
answer
498
GATE CSE 2002 | Question: 14
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\}$ ... step $M$ must make? What key property relates the behaviour of $M$ on $w$ to the behaviour of $M'$ on $x$?
Kathleen
asked
in
Theory of Computation
Sep 15, 2014
by
Kathleen
3.2k
views
gatecse-2002
theory-of-computation
decidability
normal
turing-machine
descriptive
difficult
32
votes
3
answers
499
GATE CSE 2001 | Question: 7
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
Kathleen
asked
in
Theory of Computation
Sep 14, 2014
by
Kathleen
4.6k
views
gatecse-2001
theory-of-computation
decidability
turing-machine
easy
descriptive
70
votes
4
answers
500
GATE CSE 2003 | Question: 54
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 ... $L'$ is recursively enumerable, but $ L$ is not Both $L$ and $L'$ are recursive Neither $L$ nor $L'$ is recursively enumerable
Arjun
asked
in
Theory of Computation
Sep 8, 2014
by
Arjun
24.1k
views
theory-of-computation
turing-machine
gatecse-2003
difficult
17
votes
2
answers
501
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
gatecse
asked
in
Theory of Computation
Aug 20, 2014
by
gatecse
2.3k
views
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
decidability
difficult
17
votes
4
answers
502
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
gatecse
asked
in
Theory of Computation
Aug 20, 2014
by
gatecse
5.7k
views
theory-of-computation
identify-class-language
turing-machine
decidability
recursive-and-recursively-enumerable-languages
difficult
39
votes
1
answer
503
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
gatecse
asked
in
Theory of Computation
Aug 7, 2014
by
gatecse
10.7k
views
turing-machine
theory-of-computation
normal
Page:
« prev
1
...
12
13
14
15
16
17
Subscribe to GATE CSE 2024 Test Series
Subscribe to GO Classes for GATE CSE 2024
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
Post GATE 2024 Guidance [Counseling tips and resources]
GATE CSE 2024 Result Responses
[Project Contest] Pytorch backend support for MLCommons Cpp Inference implementation
Participating in MLCommons Inference v4.0 submission (deadline is February 23 12pm IST)
IIITH PGEE 2024 Test Series by GO Classes
Subjects
All categories
General Aptitude
(3.5k)
Engineering Mathematics
(10.4k)
Digital Logic
(3.6k)
Programming and DS
(6.2k)
Algorithms
(4.8k)
Theory of Computation
(6.9k)
Compiler Design
(2.5k)
Operating System
(5.2k)
Databases
(4.8k)
CO and Architecture
(4.0k)
Computer Networks
(4.9k)
Artificial Intelligence
(79)
Machine Learning
(48)
Data Mining and Warehousing
(25)
Non GATE
(1.4k)
Others
(2.7k)
Admissions
(684)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
244k
comments
80.0k
users
Recent questions tagged turing-machine
Recent Blog Comments
category ?
Hi @Arjun sir, I have obtained a score of 591 in ...
download here
Can you please tell about IIT-H mtech CSE self...
Please add your admission queries here:...