Register

Materials:

Recent questions tagged decidability

0 votes
1 answer
332
TOC Doubt
Turing machine that accept exactly k string,Isnt it completely undecidable?
Turing machine that accept exactly k string,Isnt it completely undecidable?
User Avatar
0 votes
2 answers
340
Self doubt
Can we say Recursive languages are Turing Recognizable? As they are decidable, so they are recognisable also.
Can we say Recursive languages are Turing Recognizable?As they are decidable, so they are recognisable also.
User Avatar
2 votes
2 answers
342
Self doubt
REF: https://gateoverflow.in/76419/decidability Consider the language: 1) L = {<M>| L(M) = $\epsilon$ ... Also, other question is if we can have finite automata that accepts $\epsilon$, then we can also have TM that accepts $\epsilon$, right?
REF: https://gateoverflow.in/76419/decidabilityConsider the language:1) L = {<M>| L(M) = $\epsilon$ } 2) L = {<M>| M accepts epsilon }Now, lets consider the 1st language:...
User Avatar
2 votes
2 answers
343
L={<M> : M is a TM that accepts all even numbers }
L={<M> : M is a TM that accepts all even numbers } is it recursive/R.E??
L={<M : M is a TM that accepts all even numbers }is it recursive/R.E??
User Avatar
0 votes
1 answer
349
Decidable/Undecidable
Let A = {<M>|M is a TM and L(M) is regular}. Then A is _________ a) Decidable language and regular language b) Undecidable but partially decidable c) Totally not decidable d) Decidable language but not regular language
Let A = {<M>|M is a TM and L(M) is regular}. Then A is _________a) Decidable language and regular languageb) Undecidable but partially decidablec) Totally not decidabled)...
User Avatar
0 votes
1 answer
351
DCFl Decidability
Under what operations DCFL is Not decidable?I
Under what operations DCFL is Not decidable?I
User Avatar
0 votes
0 answers
352
virtual-gate -2015 toc
Why is the answer D? How to solve it in simple way other than learning Rice Theorem? Does anyone know Rice thm in short?
Why is the answer D? How to solve it in simple way other than learning Rice Theorem? Does anyone know Rice thm in short?
User Avatar
5 votes
1 answer
353
Rice's Theorem
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
I am unable to understand when to apply Rice's theorem and when to not. How L2 is decidable.
User Avatar
1 votes
1 answer
354
Rices theorem
I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of states?
I mean how it is a trivial property, we can write Tyes ( TM having even states) and Tno ( TM having odd states) for it.Can Turing machine can never have odd number of sta...
User Avatar
1 votes
2 answers
357
tm has more than 7 states
l = { <M> | M is a TM and M has more than 7 states } Is this decidable /undecidable/R.E /non R.e.??
l = { <M | M is a TM and M has more than 7 states }Is this decidable /undecidable/R.E /non R.e.??
User Avatar
Page: