1
$\begingroup$

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 practice problem and was wondering if the following solution would be valid for this question.

Yes, A is computable, here is an algorithm that solves it.

If P is a turing machine then L(P) is the set of all strings so that, when you run P on input x, P eventually stops and accepts x.

is x in P?(P, x)

  1. Run P(x)

  2. if x is a member of P,

  3. answer yes

  4. else

  5. answer no

$\endgroup$