= Solution
\b[No.] The property
$$
\mathcal S=\{n:|W_n|\text{ is a finite perfect square}\}
$$
is an <index set>: it depends only on the domain $W_n$ of the partial function computed, not on the syntax of its program. It is nontrivial. For example, an index whose domain is a singleton belongs to $\mathcal S$, whereas an index whose domain has two elements does not. The <Rice theorem> therefore shows that $\mathcal S$ is not a <computable set>, so no algorithm can decide the requested property for arbitrary $n$.
Invoking the <Church–Turing thesis>, this also rules out any effective procedure in the informal sense, because such a procedure would be represented by a computable function.
Back to article page
