Log In
0 votes

in Theory of Computation 126 views
Not in the syllabus but anyway, all of them are p problems
Given is option a

Please log in or register to answer this question.

Related questions

0 votes
0 answers
L1:{<M> | there exist a Turing machine M' such that <M>$\neq$<M'> and L(M) = L(M')} How this problem becomes trivial? and if it non-trivial then please explain why is that so. According to my understanding, non-trivial properties are the one where a language ... and if it is then is it okay to say M1=M2 because they are kind of same machine but other one is just with some non deterministic nature.
asked Oct 30, 2018 in Theory of Computation Swapnil Naik 105 views
0 votes
0 answers
Writes Non Blank: Given a turing machine T, does it ever writes a non-blank symbol on its tape, when started with a blank tape. how the above problem is solvable? somewhere i got this explanation: Let the machine only writes blank symbol. Then its ... this is a non-trivial property of turing machine and every non trivial property of turing machine is undecidable, so this is also undecidable.
asked Sep 21, 2018 in Theory of Computation aambazinga 96 views
2 votes
0 answers
Here is my analysis. P1: When we bound the number of steps a turing machine can tape, the total number of input possible that can be taken by such turing machine becomes finite and by running TM in an interleaved mode I can decide whether TM M halts on x within k steps. So, ... hence I can decide P3. Hence, P3 is decidable.->REC. So, I think here answer must be 1. Please let me know what's right.
asked Nov 23, 2018 in Theory of Computation Ayush Upadhyaya 206 views
1 vote
0 answers
Use Rice’s theorem, to prove the undecidability of each of the following languages. $INFINITE_{TM} = \{\langle M \rangle \mid \text{M is a TM and L(M) is an infinite language}\}$. $\{\langle M \rangle \mid \text{M is a TM and }\:1011 \in L(M)\}$. $ ALL_{TM} = \{\langle M \rangle \mid \text{ M is a TM and}\: L(M) = Σ^{\ast} \}$.
asked Oct 20, 2019 in Theory of Computation Lakshman Patel RJIT 64 views