Redirected
1,505 views
2 votes
2 votes

Consider the language L,
L = {< M >|M is a turing machine and L(M) ≤p {0p 12p|p > 0}}
Where the symbol ‘≤p’ refers to polynomial time reducible which of the following
is true regarding the above language?
a. L is undecidable
b. L is decidable
c. L is regular
d. none

1 Answer

0 votes
0 votes

the language is accepted by DPDA.so it is decidable

if  Aα(reducible)B   if B is decidable then A is also decidable

so M is decidable(turing machine)

but turing machine acceptance problem is undecidable.

we cannot guarntee that turing maching halts for all inputs,it depends on the input given

so turing machine acceptance is undecidable

Related questions

0 votes
0 votes
0 answers
2
baofbuiafbi asked Nov 14, 2023
141 views
Is the following language decidable or not? If you deem it decidable, you need to give an algorithm and analyse its running time. If not decidable, you need to prove it. ...
0 votes
0 votes
0 answers
3
baofbuiafbi asked Nov 14, 2023
142 views
Prove L = {F | F is a boolean formula and F evaluates to true on every asignment" is decidable (include algorithm and running time in big o notation)
0 votes
0 votes
0 answers
4
Abhipsa Panda asked May 24, 2022
148 views
How is equality problem for DCFL decidable?