Following Pooten [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] 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, is 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?