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
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
by
borhanElmi
99
views
theory-of-computation
peter-linz-edition5
turing-machine
1
vote
0
answers
2
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
62
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
1
vote
0
answers
3
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
34
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
4-marks
1
vote
0
answers
4
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
30
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
1
vote
0
answers
5
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
48
views
drdocse-2022-paper2
theory-of-computation
decidability
turing-machine
2-marks
descriptive
2
votes
2
answers
6
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
183
views
theory-of-computation
turing-machine
test-series
0
votes
1
answer
7
Test Series
[email protected]
2022
Please explain the ans. Ans is (B)
Amit Mehta
asked
in
Theory of Computation
Jul 19, 2022
by
Amit Mehta
177
views
turing-machine
7
votes
2
answers
8
GATE CSE 2022 | Question: 36
Which of the following is/are undecidable? Given two Turing machines $\textit{M}_{1}$ and $\textit{M}_{2},$ decide if $\textit{L(M}_{1}) = \textit{L(M}_{2}).$ Given a Turing machine $\textit{M},$ decide if $\textit{L(M)}$ is ... $\textit{M},$ decide if $\textit{M}$ takes more than $1073$ steps on every string.
Arjun
asked
in
Theory of Computation
Feb 15, 2022
by
Arjun
4.2k
views
gatecse-2022
theory-of-computation
turing-machine
decidability
multiple-selects
2-marks
0
votes
1
answer
9
Automata
L = {w: w ε{0,1}*,Every substring of four symbols has at most two 0’s} Write a program using c++ or java. The input program is the string to be tested.The automata must be tested with v= {w: w ε L} and the output should either reject or accept the string v.
fxavain
asked
in
Compilers, Architecture, HPC
Feb 11, 2022
by
fxavain
171
views
finite-automata
theory-of-computation
turing-machine
2
votes
2
answers
10
Made Easy Test series
Consider the following language : P1 : {<M, x, k>| M is a TM and M does not halt on x within k steps} P2 : {<M>| M is TM and L(M) = $\phi$} P3 : {<M>| M is a TM and L(M) = finite language} The number of problems which are not RE is/are _______ ?
Aashay kaurav
asked
in
Theory of Computation
Oct 16, 2021
by
Aashay kaurav
391
views
made-easy-test-series
theory-of-computation
turing-machine
2
votes
3
answers
11
NIELIT 2016 DEC Scientist B (CS) - Section B: 6
Which of the following is wrong? Turing machine is a simple mathematical model of general purpose computer Turing machine is more powerful than finite automata Turing Machine can be simulated by a general purpose computer All of these
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 31, 2020
by
Lakshman Patel RJIT
7.7k
views
nielit2016dec-scientistb-cs
theory-of-computation
turing-machine
1
vote
4
answers
12
NIELIT 2017 DEC Scientist B - Section B: 37
Which of the following statement is true? $S1$: The power of a multi-tape Turing machine is greater than the power of a single tape Turing machine. $S2$: Every non-deterministic Turing machine has an equivalent deterministic Turing machine. $S1$ $S2$ Both $S1$ and $S2$ None of the options
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
2.5k
views
nielit2017dec-scientistb
theory-of-computation
turing-machine
2
votes
2
answers
13
NIELIT 2017 DEC Scientist B - Section B: 57
Which machine is equally powerful in both deterministic and non-deterministic form? Push Down Automata Turing machine Linear Bounded Automata None of the options
Lakshman Patel RJIT
asked
in
Theory of Computation
Mar 30, 2020
by
Lakshman Patel RJIT
1.1k
views
nielit2017dec-scientistb
pushdown-automata
turing-machine
0
votes
1
answer
14
Michael Sipser Edition 3 Exercise 5 Question 34 (Page No. 241)
Let $X = \{\langle M, w \rangle \mid \text{M is a single-tape TM that never modifies the portion of the tape that contains the input $w$ } \}$ Is $X$ decidable? Prove your answer.
Lakshman Patel RJIT
asked
in
Theory of Computation
Oct 20, 2019
by
Lakshman Patel RJIT
505
views
michael-sipser
theory-of-computation
turing-machine
decidability
proof
Page:
1
2
3
4
5
6
...
17
next »
Subscribe to GATE CSE 2023 Test Series
Subscribe to GO Classes for GATE CSE 2023
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
My journey from being a MSc student to AIR 239 in GATE CSE 2023 and qualified UGC-NET JRF.
NEEPCO Recruitment 2023
GATE CSE 2023 Results
IIIT Banglore MTech 2023-24
IIIT-Delhi MTech 2023-24
Subjects
All categories
General Aptitude
(2.5k)
Engineering Mathematics
(9.3k)
Digital Logic
(3.3k)
Programming and DS
(5.9k)
Algorithms
(4.6k)
Theory of Computation
(6.7k)
Compiler Design
(2.3k)
Operating System
(5.0k)
Databases
(4.6k)
CO and Architecture
(3.8k)
Computer Networks
(4.7k)
Non GATE
(1.3k)
Others
(2.5k)
Admissions
(653)
Exam Queries
(844)
Tier 1 Placement Questions
(17)
Job Queries
(76)
Projects
(9)
Unknown Category
(866)
Recent questions tagged turing-machine
Recent Blog Comments
congrats pranab
Congratulations @Pranab Paul 10 🥳
sir give access to these tests at least mid May...
Was there interview for mtech as well?
Check CCMT website for previous year cutoff for...