Register

Recent questions tagged turing-machine

3 3 votes
1 1 answer
840
840 views
doubt
Which of the following is RE / NOT RE ?I.<M>|M is a TM that accepts all even numbers.II.<M>|M is a TM that does not accept all even numbers.II.<M>|M is a TM rejects all e...
User Avatar
12 12 votes
3 answers 3 answers
2.9k
2.9k views
GATE CSE 1988 | Question: 2viii
State the halting problem of the Turing machine.
User Avatar
0 0 votes
0 0 answers
388
388 views
turing machines
what is the difference between a turing machine and real-world computers?do turing machines use stack ??please tell about the memory of turing machines
User Avatar
2 2 votes
1 1 answer
1.1k
1.1k views
ACE-MockTest2:Turing Machine Decidability Problem
User Avatar
0 0 votes
2 2 answers
1.2k
1.2k views
turing machine
If we limit the size of tape in turing machine, what would be the resultant machine?
User Avatar
1 1 vote
0 0 answers
363
363 views
Decidability+TM
I dont get how the first is decidable and I have no idea about other two. Detailed explanation would be helpful
User Avatar
1 1 vote
2 2 answers
1.1k
1.1k views
Decidability
User Avatar
0 0 votes
0 0 answers
814
814 views
TOC-Turing Machine REL
User Avatar
0 0 votes
0 0 answers
360
360 views
Turing Machine
Is Turing Machine that accpet Regular Languages Decidable ?
User Avatar
1 1 vote
1 answers 1 answer
1.6k
1.6k views
Calicut Gate Academy Test Series | TOC Q32
Let ⟨M⟩ be the encoding of a Turing machine as a string over Σ={0,1} Let L={⟨M⟩∣M is a Turing machine that accepts a string of length 2014}.Then L isRecursively enumerabl...
User Avatar
2 2 votes
3 3 answers
4.9k
4.9k views
a turing machine computes the product of two numbers,? decidable or undecidable
for1. given any two specific numbers2. any two arbitrary numbers
User Avatar
0 0 votes
1 1 answer
664
664 views
decidability 
Decidability of M is a TM and L(M) is a regular language ?
User Avatar
0 0 votes
1 answers 1 answer
2.1k
2.1k views
turning machine
TM 'M1' accepts atmost 2 distinct input .TM 'M2' accept more than 2 distinct input . Which of the machine is Turning recognizable ?
User Avatar
0 0 votes
0 0 answers
448
448 views
Test by Bikram | Theory of Computation | Test 1 | Question: 24
By reading any string, which of the following is possible for a Turing Machine?TM halts in Final StateTM halts in Non Final StateTM enters into Infinite LoopAll of these
User Avatar
2 2 votes
2 2 answers
1.2k
1.2k views
MadeEasy Test Series: Theory Of Computation - Turing Machine
User Avatar
36 36 votes
3 answers 3 answers
23.4k
23.4k views
GATE CSE 1990 | Question: 3-vi
Recursive languages are:A proper superset of context free languages.Always recognizable by pushdown automata.Also called type $0$ languages.Recognizable by Turing machine...
User Avatar
6 6 votes
1 answers 1 answer
3.9k
3.9k views
turing machine
User Avatar
0 0 votes
0 0 answers
1.1k
1.1k views
closure properties
I think the question is wrong , it is related to closure properties of NP problems and NP problems are recursive so closed under concatenation, intersection, union, set d...
User Avatar
0 0 votes
0 0 answers
2.6k
2.6k views
universal turing machine
User Avatar
1 1 vote
2 2 answers
2.8k
2.8k views
turing machine
How FA with a queue is equal to Turing machine?
User Avatar
1 1 vote
1 1 answer
948
948 views
turing machine
Which of the above statement is true?
User Avatar
11 11 votes
2 answers 2 answers
8.5k
8.5k views
turing machine
Does turing machine accepts epsilon?
User Avatar
4 4 votes
2 answers 2 answers
2.4k
2.4k views
What is the difference ??
Please explain clearly?
User Avatar
1 1 vote
0 0 answers
613
613 views
PDA QUESTION GATE
δ={((q0,0,z0),(q0,0z0)),((q0,0,0),(q0,00)) ((q0,1,0),(q0,10)) ((q0,1,1),(q0,11),(q0,0,1),(q1,∈)) ((q1,0,1),(q1,t)),((q1,0,0),(q1,∈))((q1,∈,z0),(qF,∈))The language corresp...
User Avatar
2 2 votes
3 3 answers
3.2k
3.2k views
TOC Turing Machine
Consider the following languagesL1 = {< M, q |M is a turing machine that visits state q on some input within 10 steps}L2 = {< M |M is a turing machine, |M | < 100 where...
User Avatar
0 0 votes
0 0 answers
317
317 views
Explain following lines
Turing machine model of computation are:1. A finite amount of internal state.2. An infinite amount of external data storage.3. A program specified by a finite number of i...
User Avatar
19 19 votes
5 answers 5 answers
6.8k
6.8k views
GATE CSE 1987 | Question: 2m
State whether the following statements are TRUE or FALSE:The problem as to whether a Turing machine $M$ accepts input $w$ is undecidable.
User Avatar
21 21 votes
5 answers 5 answers
6.7k
6.7k views
GATE CSE 1987 | Question: 2l
State whether the following statement are TRUE or FALSE.$A$ is recursive if both $A$ and its complement are accepted by Turing machines.
User Avatar
0 0 votes
1 1 answer
808
808 views
Equivalency of diffetent automata
Write about the equivalency of different automata such as DFA, NFA, DPDA, NPDA, DTM, NTM. Which automata or machine can be converted to other machines and why? For exampl...
User Avatar
0 0 votes
1 1 answer
574
574 views
Turing machine
Any good source to study the halting concept of Turing machine,other than Peter Linz?
User Avatar
Page: