Register

Recent questions tagged turing-machine

0 votes
0 answers
454
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 difference. Correct me if i am wrong..
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
1 votes
2 answers
456
turing machine
How FA with a queue is equal to Turing machine?
How FA with a queue is equal to Turing machine?
User Avatar
1 votes
1 answer
457
turing machine
Which of the above statement is true?
Which of the above statement is true?
User Avatar
11 votes
2 answers
458
turing machine
Does turing machine accepts epsilon?
Does turing machine accepts epsilon?
User Avatar
4 votes
2 answers
459
What is the difference ??
Please explain clearly?
Please explain clearly?
User Avatar
14 votes
2 answers
463
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.
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
14 votes
4 answers
464
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.
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 votes
1 answer
465
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 example NFA can be converted to DFA, DPDA, NPDA, DTM, NTM.
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 votes
1 answer
466
Turing machine
Any good source to study the halting concept of Turing machine,other than Peter Linz?
Any good source to study the halting concept of Turing machine,other than Peter Linz?
User Avatar
0 votes
3 answers
467
Self Doubt
Are Turing Recognizable and Turing Acceptable languages same? What is their relationship with recursive enumerable and recursive language?
Are Turing Recognizable and Turing Acceptable languages same? What is their relationship with recursive enumerable and recursive language?
User Avatar
5 votes
0 answers
468
UNDECIDABLE
User Avatar
2 votes
1 answer
469
class of language
1. L = {<M>|M is a TM and L(M) is countable} 2. L = {<M>|M is a TM and L(M) is uncountable} what is the class of 1 and 2 recursive/RE/NOT RE
1. L = {<M>|M is a TM and L(M) is countable}2. L = {<M>|M is a TM and L(M) is uncountable}what is the class of 1 and 2 recursive/RE/NOT RE
User Avatar
2 votes
1 answer
470
Halting Problem
User Avatar
2 votes
1 answer
471
Decidability
i m confused between 2 problems 1. X={M| L(M)=ε} 2. Y ={M| M accepts ε} where M is Turing Machine is this 2 problems are different and also explain decidability of both ie. decidable/semi-decidable/undecidable....
i m confused between 2 problems 1. X={M| L(M)=ε} 2. Y ={M| M accepts ε}where M is Turing Machineis this 2 problems are different and also explain decidability of both...
User Avatar
5 votes
2 answers
475
Halting Problem of Turing Machines
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
Can anyone provide the proof of halting problem of turing machines by contradiction ? If possible, give example, how is it reduced to other turing problems ?
User Avatar
0 votes
1 answer
476
Turing Machine
Construct the Turing Machine that accepts the language of palindromes over {a, b}. Also specify the moves trace the strings abaa, abba, aabaa.
Construct the Turing Machine that accepts the language of palindromes over {a, b}. Also specify the moves trace the strings abaa, abba, aabaa.
User Avatar
Page: