If P is a property of turing machines, does P $\leq_T$ COUNT_P imply that P $\in$ RE $\cup$ coRE?

Question

Fix an input and tape alphabet $\Sigma$ and $\Gamma$. Let P be a property of turing machines over these alphabets, i.e., a subset of $\{\langle M \rangle \mid M \text{ is a TM over the alphabets } \Sigma \text{ and } \Gamma\}$. Define COUNT_P to be the function $\mathbb{N} \to \mathbb{N}$ describing the number of $n$-state turing machines over these alphabets which satisfy property $P$ (here, we also fix the states to be $\{1, 2, \dots, n\}$, so that we can't have two turing machines which are the same but with differently named states. Basically, we want the set of $n$-state turing machines to be finite).

One can show that if P is a recognizable (or co-recognizable) property, then P $\leq_T$ COUNT_P (here $\leq_T$ denotes Turing-reducibility). What can be said about the converse of this statement? Indeed, if P $\leq_T$ COUNT_P, is P either recognizable or co-recognizable? I don't have any real reason to believe that this is true or false, but just would like to know an answer in either direction (seems difficult to find a counter-example or to prove it to be true).

Answer 1

Let $L \subseteq \mathbb{N}$ be a set of your choice, let $N(M)$ be the number of states in a Turing machine $M$, and let $P = \{ \langle M \rangle : N(M) \in L \}$. Then $P$ reduces to $\mathsf{COUNT}_P$, but $P$ can be arbitrarily hard.