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.
Best Answer
Yes, you are right that Rice's theorem applies here and implies $A$ is not computable.
For a direct reduction to the halting problem (which is really nothing more than the proof of Rice's theorem specialized to this particular case), given a program $a$ and input $i,$
It's clear that this inner program is equivalent to "return $1$" if $a$ halts on input $i$ and equivalent to "loop" if it doesn't. And "return $1$" accepts infinitely many inputs (all of them) whereas "loop" accepts only finitely many (none).