Does my solution show that the language is uncomputable by applying rice's theorem?

126 Views Asked by At

If p is a Turing machine then L(p) = {x | p(x) = yes}.

Let A = {p | p is a Turing machine and L(p) is a finite set}.

Is A computable? Justify your answer.

So I'm trying to figure out how to solve this question and here is the answer that I've come up with:

(i) So we know that A is a non-trivial problem since some turing machines L(p) is a finite state and some turing machines where L(p) is not a finite state.

(ii) A respects equivalence when given any 2 equivalent turing machines p and q.

 p ε A ⇒ p is a turing machine and L(p) is a finite set

       ⇒ q is a turing machine and L(q) is a finite set

       ⇒ q ε A

Therefore, by applying Rice's theorem we can see that A is uncomputable.

0

There are 0 best solutions below