I’ve been wondering – and surely I’m not the first –
about the relation between Godel’s first Incompleteness
Theorem, and Turing’s halting problem. viz: Are they
logically equivalent? Can one be derived from the other?
If you look at the books, they all go something like:
Hilbert’s program blah blah, which was undercut by Godel,
later Turing began to think about mechanical computability,
invented his model, and showed the existence of
uncomputable functions. The student is left on his own
to think: these results look very similar.
Is it more than a conceptual analogy? Can we show rigorously,
with a suitable axiomatic system, that they are equivalent?
If so, that indicates a broad failure of the literature, which
only hints at such a relationship, in lieu of presenting it explicitly.
Mark
Mark-T wrote:
> I’ve been wondering – and surely I’m not the first –
> about the relation between Godel’s first Incompleteness
> Theorem, and Turing’s halting problem. viz: Are they
> logically equivalent? Can one be derived from the other?
Goedel’s work predates Turing’s work, and indeed predates the
definition of a Turing machine, and hence the very formulation of the
halting problem. There is a version of Goedel’s theorem which goes: Any
recursively enumerable set of sentences in the first-order language of
arithmetic is pi-1-incomplete. This is very closely related to the
unsolvability of the halting problem. Because for each pi-1 sentence we
can construct a Turing machine such that the pi-1 sentence is true if
and only if the Turing machine does not halt. (This is a non-trivial
result, how hard it is to prove depends on how you define "pi-1
sentence". On one definition of "pi-1 sentence", it would follow from
the work of Turing. But, on the definition of "pi-1 sentence" more
common today, it follows from the difficult MRDP theorem). Our version
of Goedel’s theorem says that the set of true pi-1 sentences is not
recursively enumerable. Since the set of true sigma-1 sentences is
clearly recursively enumerable, this is the same as saying the set of
pi-1 sentences is not recursive, which, in light of the fact mentioned
above, is the same as saying the halting problem is recursively
unsolvable. Turing’s method of proof and Goedel’s method of proof are
also very closely related.
> If you look at the books, they all go something like:
> Hilbert’s program blah blah, which was undercut by Godel,
> later Turing began to think about mechanical computability,
> invented his model, and showed the existence of
> uncomputable functions. The student is left on his own
> to think: these results look very similar.
> Is it more than a conceptual analogy? Can we show rigorously,
> with a suitable axiomatic system, that they are equivalent?
Well, they’re both provable in PA, so they must be equivalent in PA.
You will have trouble precisely defining the notion of "equivalence"
that you really want here.
- Hide quoted text — Show quoted text -
> If so, that indicates a broad failure of the literature, which
> only hints at such a relationship, in lieu of presenting it explicitly.
> Mark
"Rupert" <rupertmccal…@yahoo.com> writes:
> Because for each pi-1 sentence we
> can construct a Turing machine such that the pi-1 sentence is true if
> and only if the Turing machine does not halt. (This is a non-trivial
> result, how hard it is to prove depends on how you define "pi-1
> sentence". On one definition of "pi-1 sentence", it would follow from
> the work of Turing. But, on the definition of "pi-1 sentence" more
> common today, it follows from the difficult MRDP theorem).
What do you have in mind here?
Torkel Franzen wrote:
> "Rupert" <rupertmccal…@yahoo.com> writes:
> > Because for each pi-1 sentence we
> > can construct a Turing machine such that the pi-1 sentence is true if
> > and only if the Turing machine does not halt. (This is a non-trivial
> > result, how hard it is to prove depends on how you define "pi-1
> > sentence". On one definition of "pi-1 sentence", it would follow from
> > the work of Turing. But, on the definition of "pi-1 sentence" more
> > common today, it follows from the difficult MRDP theorem).
> What do you have in mind here?
Well, I was thinking we could define a pi-1 sentence to be a sentence
of the form AxF(x) with F a primitive recursive class-sign (as defined
in, say, Goedel’s paper). Alternatively, and this is what I meant by
the more modern definition, you could define a pi-1 sentence to be a
sentence starting with Ax and then followed by a formula in the
first-order language of arithmetic with only bounded quantifiers. On
the latter definition of pi-1 sentence, to prove for every Turing
machine that there’s a pi-1 sentence which is true if and only if the
Turing machine does not halt, as far as I know requires the MRDP
theorem.
"Rupert" <rupertmccal…@yahoo.com> writes:
> Alternatively, and this is what I meant by
> the more modern definition, you could define a pi-1 sentence to be a
> sentence starting with Ax and then followed by a formula in the
> first-order language of arithmetic with only bounded quantifiers. On
> the latter definition of pi-1 sentence, to prove for every Turing
> machine that there’s a pi-1 sentence which is true if and only if the
> Turing machine does not halt, as far as I know requires the MRDP
> theorem.
No, we don’t need the MRDP theorem for that.
Rupert wrote:
> Alternatively, and this is what I meant by
> the more modern definition, you could define a pi-1 sentence to be a
> sentence starting with Ax and then followed by a formula in the
> first-order language of arithmetic with only bounded quantifiers. On
> the latter definition of pi-1 sentence, to prove for every Turing
> machine that there’s a pi-1 sentence which is true if and only if the
> Turing machine does not halt, as far as I know requires the MRDP
> theorem.
No, you need MRDP theorem to show that every Pi_1 sentence can be
written as Ax_1,…,Ax_nP(x_1,..,x_n)=/=0 with P Diophantine. After all,
it’s obvious that every statement of the form "The Diophantine equation
P has no solution" can be written as Ax_1,…,x_n Q(x_1,..,x_n) where
Q(x) has no unbounded quantifiers. The fact that for every Turing
machine there is a Pi_1 sentence which is true iff the machine does not
halt follows from e.g. the existence of a Delta_0 coding of finite
sequences.
–
Aatu Koskensilta (aatu.koskensi…@xortec.fi)
"Wovon man nicht sprechen kann, daruber muss man schweigen"
– Ludwig Wittgenstein, Tractatus Logico-Philosophicus