0
votes
1answer
29 views

Prove language is in $NP$ without using a reduction

I've been stuck on this question for hours, can't seem to figure this out. $L = \{\langle M, x, y \rangle\ |\ M$ is a non-deterministic Turing machine over $\{0,1\}$ and $x,y \in \{0,1\}^*$ and ...
3
votes
1answer
96 views

Rice's theorem_Theory of computation

Is there any body tell me, where is wrong in this proof Problem: The set of number of turing machine that has 5 state is decidable or not? Answer: The set is obviously 'Set of partial computable ...
2
votes
3answers
3k views

Proving that a Turing Machine that only accepts even length strings is undecidable

I need to prove that a Turing Machine that only accepts even length strings in undecidable. The proof I was thinking is explaining the following: Given an input that contains even length strings, if ...
2
votes
1answer
105 views

Where is the flaw in the following proof?

Where is the flaw in the following proof, that if a language is Turing recognizable then we can enumerate it? Proof Let $TM1$ be a Turing machine for language $L$. We can create an enumerator $E$ ...
1
vote
1answer
74 views

Seeking Alternate Proof Regarding Closure Of Recursively Enumerable Languages Under Shrink

So I would like to show that the class of Recursively Enumerable languages are closed under the shrink operation. In other words, $\mathrm{shrink}_a(L) = \{x \mid x=\mathrm{shrink}_a(w), w\in L\}$ and ...