From a wikipedia page:

One can write down a concrete polynomial p ∈ Z[x1, ..., x9] such that the statement "there are integers m1, ..., m9 with p(m1, ..., m9) = 0" can neither be proven nor disproven in ZFC (assuming ZFC is consistent). This follows from Yuri Matiyasevich's resolution of Hilbert's tenth problem; the polynomial is constructed so that it has an integer root if and only if ZFC is inconsistent.

So I opened the paper, and what I understood is that there exists a universal polynomial, such that

$$x\in W_v \iff \exists m_1\ldots m_9, U(x,v,m_1\ldots m_9) = 0$$

where $W_v$ is a recursively enumerable set indexed by $v$, and $x$ is a binary number or whatever output format we prescribe of our Turing machines.

Now if we select $v$ such that $W_v$ is non-recursive but r.e., then the set $X = \{ x : x\in W_v \} $ is undecidable. That doesn't mean that for every particular $x$, $x \in W_v$ is undecidable in ZFC, right?

For instance let $W_v$ is the set of all Turing machines (no input) that halt, this is a recognisable but not decidable set, and let $x$ be a Turing machine that halts on instantiation, then we can prove $x\in W_v$

Basically I'm having trouble proving the statement in the blockquotes from wikipedia, do let me know how to go about it.

  • 1
    $\begingroup$ You are right, the fact that $X$ is not decidable doesn't mean that we cannot decide membership for any element. Actually, for e.g. the halting problem, you can decide for every element! The thing is that there is not a single algorithm (or TM, or recursive function) that does the job for every input. $\endgroup$ – Manlio Apr 18 at 7:51
  • $\begingroup$ @Manlio Thanks, does that mean the wikipedia statement is wrong or that there's some other way to prove it? $\endgroup$ – ghosts_in_the_code Apr 18 at 8:08

Let me elaborate my comment a bit: the fact that a set $X$ is not decidable doesn't mean that we cannot decide membership for any element. It is the converse actually. Namely, for every $X\subset \mathbb{N}$ (let us remain in the context of classical computability) and every $x$, there is a computable function $\varphi=\varphi_{x,X}$ s.t. $\varphi(x) = \chi_X(x)$ where $\chi_X$ is the characteristic function of $X$. This is easy to see: if $x\in X$ let $\varphi$ be the map constantly $1$, otherwise let it be constantly $0$. This clearly proves the claim, albeit in a trivial and non-satisfactory way.

When it comes to provability the focus is slightly different: you want to prove that a certain statement is true or false. In the case of the diophantine polynomial, the claim is "there are $m_1,...,m_9$ s.t. $U(x,m_1,...,m_9)=0$". Now, the set of theorems in ZFC (or in any theory with a r.e. set of axioms) is a r.e. set. This means that $x$ is a theorem in ZFC iff there are $m_1,...m_9$ as above. Now take $x$ to be (index for) the Gödel formula (or any other statement independent of ZFC). Once $x$ is fixed, the polynomial $U$ is just a polynomial of $m_1,...,m_9$ ($x$ is now a parameter). If ZFC could prove (or disprove) that such $m_1,...,m_9$ exist, it could prove (or disprove) Gödel formula, and we know this is not the case.

Here's another (explicit) example of a Turing machine whose behavior eludes ZFC: https://www.scottaaronson.com/blog/?p=2725

| cite | improve this answer | |
  • $\begingroup$ Wow that's interesting, never thought of the last part that the set of all provable theorems is an r.e. set. As a last question, is there any way to explicitly calculate $x$, for instance for the godel formula. By the way I'm asking because I'm exactly trying to find a smaller machine whose halting is independent of ZFC, finding solutions to a Diophantine equation is something that can be written in less states / lines of code $\endgroup$ – ghosts_in_the_code Apr 19 at 9:11
  • $\begingroup$ I mean if $x$ and the universal polynomial are precomputed and stored in the machine, and the machine tries brute forcing a solution to the equation, then its halting or non halting nature is independent of ZFC right? Plus this should have less than 8000 states, it's a simpler computation than the graph theory done in the 8000 state one $\endgroup$ – ghosts_in_the_code Apr 19 at 9:14
  • $\begingroup$ Yes, you can definitely compute explicitly the index for any formula (even though actually doing it can be tedious, and is very dependent on the details of the formalization). The problem of finding a smaller machine is interesting, you may want to take a look at the link I posted, you can use that work to better search the literature I guess. By the WO of $\mathbb{N}$ there must be a "smaller" machine, whatever you mean by smaller (smaller index? less states?). Also you may want to be extra cautious on the details. E.g. different indexing of the TMs can lead to different smaller machine. $\endgroup$ – Manlio Apr 19 at 9:24
  • $\begingroup$ Less states, yes. Main result of the paper is probably just to find the smallest undecidable busy beaver. Also I haven't found any other papers on it, there's an unpublished 2000 state machine by Stefan o Rear on GitHub somewhere $\endgroup$ – ghosts_in_the_code Apr 19 at 9:28

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.