Following Poonen [1], Davis[2], Chaitin [3], and Ord and Kieu [4]:
Is it possible that there is a polynomial $P$ of degree $d\le 4$, along with a prefix-free universal Turing machine $T$, such that the $k^{th}$ bit of the halting probability, $\Omega_T$, is $0$ if and only if
$$P(x,y,z)=k$$
has an infinite (or even) number of solutions?
A lot of attention has been given to questions about the decidability of
$$x^3+y^3+z^3=k$$
However, after Heath-Brown [5] [5a] it might be reasonable to say that if $k$ doesn't have an obstruction mod 9 then it can be represented as the sum of three cubes in an infinite number of ways.
Nonetheless I always liked Chaitin's results (and Ord and Kieu's follow-up), but Chaitin concedes that his explicit construction of an exponential Diophantine equation with a parameter encoding an $\Omega$ is, at 17,000 variables, in his words "a little large."
After learning that problems as simple as the sum of three cubes can have such a dynamic and complex behavior, I'm wondering if Chaitin's construction can be "reversed" in some sense, by starting from a much simpler Diophantine equation to find a universal Turing machine? Have we learned a lot in the last twenty years or so about if and how complexity begets universality?
