2
$\begingroup$

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

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.