Dark Mode

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

99 views

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

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

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

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

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

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

177 views

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

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

171 views

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

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

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

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

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

Page:

1
2
3
4
5
6
...
17
next »

Recent questions tagged turing-machine