= Solution
The <clique decision problem> is a <decidable language>: on a valid finite <graph> and an <integer> $k$, reject if $k$ exceeds the number of <vertices>, and otherwise examine all $k$-element <subsets> of <vertices>, accepting if one is a <clique>. Each candidate can be checked by examining all its pairs of distinct <vertices>. This finite search gives at least one <Turing machine> deciding the problem, without any claim of <polynomial time>.
By <well-ordering> of the <natural numbers>, there is a least state count $n_0$ among <Turing machines> deciding the <clique decision problem>. For every $n\geq n_0$, add $n-n_0$ unreachable states to a machine with $n_0$ states. Its behaviour on every <input> is unchanged, and it has exactly $n$ states. For $n<n_0$ there is no such machine, by minimality. Thus
$$
\boxed{\mathcal L_{\mathrm{cliqueTM}}
=\{\operatorname{enc}(n):n\geq n_0\}.}
$$
A <Turing machine> with the fixed constant $n_0$ in its description decides this <threshold language> by validating the <input> and comparing its value with $n_0$. \b[The argument proves the existence of a decider; it does not compute the smallest possible <clique decision problem> decider.] There is no need to search through machine descriptions and attempt to certify their behaviour on every <input>.
Back to article page
