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
0
answers
1
Hopcroft, Ullman Theorem 9.7 Reductions
There exists a language Ld = {M | M doesn't belong to L(M)}. Ld is the collection of Turing machines (programs) M such that M does not halt and accept when given itself as input. It is known and proved that Ld is a non-Recursively ... and Ld is non-RE, ATM must be non-RE. But we know that ATM is Recursively Enumerable and undecidable. How is this possible?
dopq12
asked
in
Theory of Computation
Mar 5
by
dopq12
58
views
decidability
theory-of-computation
turing-machine
reduction
recursive-and-recursively-enumerable-languages
5
votes
1
answer
2
GO Classes Test Series 2024 | Mock GATE | Test 14 | Question: 64
Which of the following languages are Turing-recognizable? A. $\{\langle M\rangle \mid M$ is a (deterministic) Turing machine and $M$ accepts 010$\}$. B. $\{\langle M\rangle \mid M$ is a nondeterministic Turing machine and $M$ accepts 010 ... $\left\{\langle M\rangle \mid M\right.$ is a Turing machine and $\left.L(M)=\Sigma^*\right\}$.
GO Classes
asked
in
Theory of Computation
Feb 5
by
GO Classes
414
views
goclasses2024-mockgate-14
theory-of-computation
turing-machine
multiple-selects
2-marks
5
votes
1
answer
3
GO Classes Test Series 2024 | Mock GATE | Test 13 | Question: 55
Recall that a Turing machine $\text{T}$ can be represented or 'coded' by an integer $m$. Let us write 'the $m$ th Turing machine' to mean the Turing machine coded by $m$. Which of the following sets is not recursively enumerable ... machine halts on the input $m$. The set of $n$ such that all Turing machines halt on the input $n$.
GO Classes
asked
in
Theory of Computation
Jan 28
by
GO Classes
427
views
goclasses2024-mockgate-13
goclasses
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
2-marks
4
votes
1
answer
4
GO Classes Test Series 2024 | Mock GATE | Test 11 | Question: 64
Which of the following statements about Turing machines is false? For every context-sensitive language $L$, there is a Turing machine that accepts precisely the strings of $L$. For any grammar $G$ ... Turing machine $A$ which can simulate the behaviour of any given Turing machine $B$ on any given finite input.
GO Classes
asked
in
Theory of Computation
Jan 13
by
GO Classes
478
views
goclasses2024-mockgate-11
goclasses
theory-of-computation
turing-machine
multiple-selects
2-marks
1
vote
0
answers
5
Decidability
L(M)={0} We can have Tyes for {0} and Tno for Σ∗ ({0}⊂Σ∗{0}⊂Σ∗). Hence, L={M ∣ L(M)={0}} is not Turing recognizable (not recursively enumerable) I don’t understand why this is not decidable. We can easily create a turing that accepts this language
amitarp818
asked
in
Theory of Computation
Dec 28, 2023
by
amitarp818
216
views
decidability
theory-of-computation
turing-machine
recursive-and-recursively-enumerable-languages
0
votes
0
answers
6
Turing machine for a^n b^m c^n d^m NET UGC December 2022
The state diagram for the initial part of this turing machine given as: Here, we are basically traversing through the input tape, changing occurence of 'a' to X1, and 'c' to X2. After that we go back in the left direction ... or doing it wrong by skipping one state and directly looping back to 'q0' Please shed some light on it, thanks!
Picturesque
asked
in
Theory of Computation
Nov 1, 2023
by
Picturesque
232
views
theory-of-computation
turing-machine
3
votes
2
answers
7
TOC - Self Doubt
Can anyone explain $\overline{ww}$ is $CFL$ or $CSL$ And if $CFL$ can you write the equivalent $CFG$ for this ?
Jiten008
asked
in
Theory of Computation
Oct 25, 2023
by
Jiten008
333
views
pushdown-automata
theory-of-computation
self-doubt
regular-language
context-free-language
context-sensitive
turing-machine
closure-property
context-free-grammar
0
votes
0
answers
8
Design Turing machines to compute the following functions for x and y positive integers represented in unary. (a) f(x) = 3x
sridharsiddi
asked
in
Theory of Computation
Apr 16, 2023
by
sridharsiddi
738
views
theory-of-computation
turing-machine
0
votes
0
answers
9
Peter Linz Edition 5 Exercise 10.5 Question 3
Consider an offline Turing machine in which the input can be read only once, moving left to right, and not rewritten. On its work tape, it can use at most n extra cells for work space, where n is fixed for all inputs. Show that such a machine is equivalent to a finite automaton.
borhanElmi
asked
in
Theory of Computation
Feb 9, 2023
by
borhanElmi
307
views
theory-of-computation
peter-linz-edition5
turing-machine
1
vote
0
answers
10
DRDO CSE 2022 Paper 2 | Question: 12 (a)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cup L_{2}$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
278
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
2
votes
0
answers
11
DRDO CSE 2022 Paper 2 | Question: 13
Let $L$ be the following language. $L=\left\{P\left(x_{1}, x_{2}, \ldots, x_{n}\right) \mid P\right.$ is a polynomial with an integral root $\}$. Explain why the following Turing Machine description cannot decide the language $L$. ... $0,$ accept. Else, reject.
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
230
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
4-marks
1
vote
0
answers
12
DRDO CSE 2022 Paper 2 | Question: 12 (b)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L=\left\{a \circ b \mid a \in L_{1}, b \in L_{2}\right\}$ where $a$ o $b$ denotes the concatenation of the strings $a$ and $b$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
181
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
1
vote
0
answers
13
DRDO CSE 2022 Paper 2 | Question: 12 (c)
Let $L_{1}$ and $L_{2}$ be two languages decidable by Non-deterministic Turing machines $M_{1}$ and $M_{2}$. Using $M_{1}$ and $M_{2}$, construct a Non-deterministic Turing machine for the following languages. $L_{1} \cap L_{2}$
admin
asked
in
Theory of Computation
Dec 15, 2022
by
admin
259
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
3
votes
2
answers
14
Turing machine question
I saw question where I saw this format being used: L1 = {<M> | L(M) = ϕ} What does exactly <M> mean and why is L(M) = ϕ, mentioned afterwards. Isn’t L() stands for language for something? If the language is equivalent to null, it contains nothing. Then what does it exactly mean?
h4kr
asked
in
Theory of Computation
Dec 7, 2022
by
h4kr
686
views
theory-of-computation
turing-machine
test-series
4
votes
1
answer
15
GO Classes Test Series 2023 | Theory of Computation | Test 5 | Question: 4
Consider the following languages : $\mathrm{L} 1:=\{\langle \text{M}\rangle \mid \text{M}$ is a $\text{TM},$ and $\text{M}$ is the only $\text{TM}$ that accepts $\mathrm{L}(\mathrm{M})\}.$ ... and $|\text{M}|<1000\} .$ Which of the above languages is Decidable? Only $\text{L1}$ Only $\text{L2}$ Both None
GO Classes
asked
in
Theory of Computation
Aug 1, 2022
by
GO Classes
592
views
goclasses2024-toc-5-weekly-quiz
goclasses
theory-of-computation
turing-machine
decidability
1-mark
Page:
1
2
3
4
5
6
...
17
next »
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
(683)
Exam Queries
(1.6k)
Tier 1 Placement Questions
(17)
Job Queries
(80)
Projects
(11)
Unknown Category
(870)
64.3k
questions
77.9k
answers
243k
comments
79.7k
users
Recent questions tagged turing-machine
Recent Blog Comments
Hlo I'm Rupesh I got AIR 3485 in gate CS and AIR...
@Ajay Sasank here is the direct link...
Thank you for the post didi My GATE 2023 & 2024...
I Hope it helps 😊
Today's best post I seen thank you for motivation