Csdrhrt

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.

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,$

1. write a program that, for any input $j$, first runs $a$ on input $i$ and
   then (if it finishes) returns $1,$ and then


2. use the oracle for $A$ to analyze this program to decide whether it
   accepts only finitely many inputs or not, returning $0$ if it does,
   and $1$ if it doesn't.

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).