Decision and the Uncountable Spectrum

Question

In 2000, Hart, Hrushovski, and Laskowski classified all complete first order theories in a countable language up to their uncountable spectra. However, does this also imply that given a $any$ (recursive, first order, complete, in a countable language), $T$, one can determine what it's uncountable spectrum is? More explicitly, is there a decision procedure for doing so?

Clearly, we can do this for unstable theories. But first, we need to determine whether or not an arbitrary (recursive) theory $T$ is unstable. Likewise for categorical theories.

Thanks.

Answer 1

There is no algorithm to decide if a recursive theory is stable or not.

Edit: The original construction did not work, as Alex Kruckaman noted in the comments. Here is a way to fix this.

Suppose that there was an algorithm to decide if a recursive theory is stable or not. Here is an algorithm to solve the halting problem using it. Given a Turing machine M and a word w, consider a language with a single binary relation $<$. The theory asserts that $<$ is a linear ordering with a maximal and minimal element, such that furthermore every element expect the minimal has an immediate predecessor and every element expect the maximal has an immediate successor. If $\phi_n$ is the sentence that asserts that there are at most $n$ elements in the universe, then $\phi_n$ holds in our theory iff the machine has already halted on the $n$-th step.

You get a complete theory. If the machine halts then it is just the theory of a finite linearly ordered set, clearly stable. Otherwise, it is the theory of a copy of the nonnegative integers numbers followed by a copy of the nonpositive integers, which is unstable.

This proof also shows that there is no algorithm to decide if a theory is categorical, or NIP, etc.

Edit: in fact, I think that the decision problem on stability should be of complexity $\Pi_2$. You need to show that for every formula there is some $N$ such that the formula cannot linearly order a set of size $N$. This gives an upper bound of $\Pi_2$ on the complexity, and the problem is general enough to probably be $\Pi_2$-complete.