halting problem proof, via diagonalization?

I heard someone say recently, "The proof of the Turing
machine halting problem is an example of diagonalization."

I don't see that. As I recall, it's proof by contradiction;
assume a program which accomplishes the goal, feed
the code of this program to itself, etc., ad absurdum. QED

Whereas diagonalization consists of constructing a list,
then constructing a new object not in the list, etc.

Can anyone reconcile this?


--
Rich

On Fri, 8 Aug 2008 02:09:11 -0700 (PDT), RichD
<r_delaney2001@yahoo.com> wrote:

>I heard someone say recently, "The proof of the Turing
>machine halting problem is an example of diagonalization."
>
>I don't see that. As I recall, it's proof by contradiction;
>assume a program which accomplishes the goal, feed
>the code of this program to itself, etc., ad absurdum. QED
>
>Whereas diagonalization consists of constructing a list,
>then constructing a new object not in the list, etc.
>
>Can anyone reconcile this?

The word "diagonalization" gets used a little informally -
in some sense the idea behind the two proofs, or part
of the structure of the two proofs, is the same.

In the proof of the uncountability of the reals we
start with a sequence x_1, x_2, ... of reals.
Say x_j[n] is the n-th digit in the decimal expansion
of x_j. Then x_j[j] is a "diagonal" element of a
certain "matrix", and the proof proceeds by constructing
a real number x such that x[j] is _not_ equal to x_j[j].

Note the "not".

Here's another proof by "diagonalization" that's just
one notch more abstract. If A is a set then P(A)
is the power set of A; that is, P(A) is the set of
all subsets of A.

Thm 1. If A is a set then there is no function
mapping A _onto_ P(A).

In other words, if f : A -> P(A) is any function
then there exists S in P(A) (ie S is a subset of A)
such that S is not equal to f(a) for any a in A.

Proof: Suppose f : A -> P(A). Define S, a subset
of A, by

S = {x in A such that x is not an element of f(x)}.

(Note the "not" there...)

Then for any a in A, S is not equal to f(a).
Suppose on the other hand that S = f(a)
for some particular a in A. Now, either
a is an element of S or a is not an element
of S. But if a is an element of S then the
definition of S shows that a is not an element
of S. And if a is not an element of S then the
definition of S shows that a _is_ an element
of S.

So both a in S and a not in S are impossible.
Contradiction, QED.

Let''s rephrase the theorem and the proof to make it look
more like the diagonal argument showing the reals are
uncountable. If A is a set then 2^A is the set of all
function mapping A into the two-element set {0,1}.
Since there _is_ an obvious one-to-one correspondence
between P(A) and 2^A, Theorem 1 is the same as saying
that there is no function mapping A onto 2^A. And that's
the same as this:

Thm 2. Suppose A is a set, and suppose that for every
a in A we are given a function x_a, which maps A into
{0,1}. (So x_a(b) is 0 or 1 for every a, b in S.) Then
there exists x, a function mapping A into {0,1},
such that x is not equal to x_a for any a in A.

Proof: Define x : A -> {0,1} by

x(a) = 1 - x_a(a) (for all a in A).

The point to that funny formula 1 - x_a(a)
is just that x(a) is _not_ equal to x_a(a)
(because 1 - 0 = 1 <> 0 and 1 - 1 = 0 <> 1.)

Since x(a) is not equal to x_a(a), x is not the
same as x_a. QED.

Note that x_a(a) is the "diagonal" element of
our array of functions {x_a}, and the key is
constructing x so x(a) <> x_a(a). Exactly
like the x[j] <> x_x[j] in the proof of uncountability
of the reals.

So Theorem 2 really is a diagonalization argument;
the proof is almost exactly the same as the proof
of uncountability of the reals. But the proof of
Theorem 1 is really the same as the proof of Theorem 2,
just in different notation. So Theorem 1 gets called
a diagonal argument as well.

Now look at the "Sketch of Proof" at

http://en.wikipedia.org/wiki/Halting_problem

and the comments that follow.

David C. Ullrich

"Understanding Godel isn't about following his formal proof.
That would make a mockery of everything Godel was up to."
(John Jones, "My talk about Godel to the post-grads."
in sci.logic.)

[Cue shameless advertising]

There's something about the aptness of extending the idea of
diagonalization from "diagonalizing out of a list" to the sorts of
constructions involved in constructing a standard Gödel sentence (or
in proving the unsolvability of the halting problem) in my
Introduction to Gödel's Theorems [www.godelbook.net], at p. 130, cf.
p. 307.

RichD says...

>I heard someone say recently, "The proof of the Turing
>machine halting problem is an example of diagonalization."
>
>I don't see that. As I recall, it's proof by contradiction;
>assume a program which accomplishes the goal, feed
>the code of this program to itself, etc., ad absurdum. QED
>
>Whereas diagonalization consists of constructing a list,
>then constructing a new object not in the list, etc.
>
>Can anyone reconcile this?

You can express the unsolvability of the halting problem
as a theorem that is proved by diagonalization:

Pick some standard way to assign a unique integer to every Turing
machine program that takes exactly one input. We will say that
the integer assigned to a Turing machine M is the "code" of M.
Say that a pair <n,x> of integers is a "non-halting pair" if
the Turing machine with code n does not halt on input x.

Theorem 1: If <n_1,x_1>, <n_2,x_2>, ... is any computable list
of non-halting pairs, then there is a non-halting pair <n,x>
that is not on that list.

Proof: Let M(x) be the program that checks to see if <x,x> is
on the list, and if so, halts. If <x,x> is not on the list, then
M(x) runs forever. Let n be the code of M. Then <n,n> is a
non-halting pair, but it is not on the list.

--
Daryl McCullough
Ithaca, NY

On Aug 8, 11:09*am, RichD <r_delaney2...@yahoo.com> wrote:
> I heard someone say recently, "The proof of the Turing
> machine halting problem is an example of diagonalization."
>
> I don't see that. *As I recall, it's proof by contradiction;
> assume a program which accomplishes the goal, feed
> the code of this program to itself, etc., ad absurdum. *QED
>
> Whereas diagonalization consists of constructing a list,
> then constructing a new object not in the list, etc.
>
> Can anyone reconcile this?
>
> --
> Rich

Diagonalization is a very general tecnique aiming at showing thet a
certain set S does not exist: e.g. a countable set of all reals
(Cantor), a bijection between A and P(A) (Cantor), a recursively
enumerable set of all arithmetical truths (Gödel), an arithmetically
definable set of all arithmetical truths (Tarski), etc.

The tecnique can be seen as a reductio of the assumption that S exists
and it typically proceeds by constructing a diagonal object D that
should be in S if S existed but that, by construction, cannot be in
S.

This is sometimes put as the indefinite extensibility of any set T
'purporting' to be S; then it's shown that there is a (diagonal)
function f that for any T gives an object d such that d is in T if T=S
and it's shown that d is actually not in T. You may or may not require
that f be computable.

Now consider the usual proof of Turing's theorem. Assume there is a
Turing machine H that computes the halting problem for any Turing
machine. Then we can use H to construct a double input matrix M that
for any pair (m, n), where m is a code (a Gödel number) of a Turing
machine and n is a natural, displays 1 if m terminates on n and 0
otherwise.

Now H must be in M coded (say) by h. We give h to H (h acting as a
code for (h, h)) in order to fill in the corresponding square in M. To
decide the halting problem for this specific input, H has to compute
what H does when fed h, that is, it has to compute whether its current
computation terminates; the ensuing circularity prevents H from giving
an output and forces us to leave the corresponding square in M blank.

So, under the assumption that H exists, we've produced a computation
(h, h) whose behavior is not represented in M, which contradicts the
assumption.

Since M can be regarded as a set, (h, h) is an object that should be a
member of M (if H existed) but is not such; thus the procedure fits
with the general diagonal procedure described above.

Regards

On 8 Aug, 16:30, LauLuna <laureanol...@yahoo.es> wrote:
> On Aug 8, 11:09*am, RichD <r_delaney2...@yahoo.com> wrote:
>
> > I heard someone say recently, "The proof of the Turing
> > machine halting problem is an example of diagonalization."
>
> > I don't see that. *As I recall, it's proof by contradiction;
> > assume a program which accomplishes the goal, feed
> > the code of this program to itself, etc., ad absurdum. *QED
>
> > Whereas diagonalization consists of constructing a list,
> > then constructing a new object not in the list, etc.
>
> > Can anyone reconcile this?
>
> > --
> > Rich
>
> Diagonalization is a very general tecnique aiming at showing thet a
> certain set S does not exist: e.g. a countable set of all reals
> (Cantor), a bijection between A and P(A) (Cantor), a recursively
> enumerable set of all arithmetical truths (Gödel), an arithmetically
> definable set of all arithmetical truths (Tarski), etc.
>
> The tecnique can be seen as a reductio of the assumption that S exists
> and it typically proceeds by constructing a diagonal object D that
> should be in S if S existed but that, by construction, cannot be in
> S.


And this is where there are most of the objections.

Below again a simple argument to show that from the very same
construction we could induce the exact opposite result:

1: The diagonal differs from the 1st entry in the 1st place;
2: The diagonal differs from the 2nd entry in the 2nd place;
...
n: The diagonal differs from the n-th entry in the n-th place;

It seems straightforward to induce that, at the limit, the difference
between the diagonal and the limit entry tends to zero.

-LV


> This is sometimes put as the indefinite extensibility of any set T
> 'purporting' to be S; then it's shown that there is a (diagonal)
> function f that for any T gives an object d such that d is in T if T=S
> and it's shown that d is actually not in T. You may or may not require
> that f be computable.
>
> Now consider the usual proof of Turing's theorem. Assume there is a
> Turing machine H that computes the halting problem for any Turing
> machine. Then we can use H to construct a double input matrix M that
> for any pair (m, n), where m is a code (a Gödel number) of a Turing
> machine and n is a natural, displays 1 if m terminates on n and 0
> otherwise.
>
> Now H must be in M coded (say) by h. We give h to H (h acting as a
> code for (h, h)) in order to fill in the corresponding square in M. To
> decide the halting problem for this specific input, H has to compute
> what H does when fed h, that is, it has to compute whether its current
> computation terminates; the ensuing circularity prevents H from giving
> an output and forces us to leave the corresponding square in M blank.
>
> So, under the assumption that H exists, we've produced a computation
> (h, h) whose behavior is not represented in M, which contradicts the
> assumption.
>
> Since M can be regarded as a set, (h, h) is an object that should be a
> member of M (if H existed) but is not such; thus the procedure fits
> with the general diagonal procedure described above.
>
> Regards

On Aug 8, 9:39*am, ju...@diegidio.name wrote:

> Below again a simple argument to show that from the very same
> construction we could induce the exact opposite result:
>
> 1: The diagonal differs from the 1st entry in the 1st place;
> 2: The diagonal differs from the 2nd entry in the 2nd place;
> ...
> n: The diagonal differs from the n-th entry in the n-th place;
>
> It seems straightforward to induce that, at the limit, the difference
> between the diagonal and the limit entry tends to zero.

WHAT limit? You need to DEFINE "limit" in terms of some topology,
metric, ordering, or whatever. We don't just use the word "limit"
without the context of the EXACT sense of a limit as it has been
DEFINED.

Moreover, the anti-diagonal differes from every entry in the list.
That's all that is required to show that the anti-diagonal is not on
the list.

MoeBlee

julio@diegidio.name writes:

> Below again a simple argument to show that from the very same
> construction we could induce the exact opposite result:
>
> 1: The diagonal differs from the 1st entry in the 1st place;
> 2: The diagonal differs from the 2nd entry in the 2nd place;
> ...
> n: The diagonal differs from the n-th entry in the n-th place;
>
> It seems straightforward to induce that, at the limit, the difference
> between the diagonal and the limit entry tends to zero.

Wonderful. I wonder how many people will rush in to the rescue, asking
"What limit entry?" or exclaiming most ferociously "There is no limit
entry!". Surely you can anticipate this response just as well as the
next man. The obvious question, then, is why bother? Why not come up
with some novel rubbish?

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

On 8 Aug, 17:44, Aatu Koskensilta <aatu.koskensi...@uta.fi> wrote:
> ju...@diegidio.name writes:
> > Below again a simple argument to show that from the very same
> > construction we could induce the exact opposite result:
>
> > 1: The diagonal differs from the 1st entry in the 1st place;
> > 2: The diagonal differs from the 2nd entry in the 2nd place;
> > ...
> > n: The diagonal differs from the n-th entry in the n-th place;
>
> > It seems straightforward to induce that, at the limit, the difference
> > between the diagonal and the limit entry tends to zero.
>
> Wonderful. I wonder how many people will rush in to the rescue, asking
> "What limit entry?" or exclaiming most ferociously "There is no limit
> entry!". Surely you can anticipate this response just as well as the
> next man. The obvious question, then, is why bother? Why not come up
> with some novel rubbish?


Because I cannot get what is wrong with it.

The "limit" is of course induction.

-LV


> --
> Aatu Koskensilta (aatu.koskensi...@uta.fi)
>
> "Wovon man nicht sprechen kann, darüber muss man schweigen"
> *- Ludwig Wittgenstein, Tractatus Logico-Philosophicus

julio@diegidio.name writes:

> The "limit" is of course induction.

Alas, that makes no sense whatsoever. But I see someone has already
rushed in to the rescue, asking "WHAT limit?" so you're in safe
hands. I'll make a hasty retreat myself.

--
Aatu Koskensilta (aatu.koskensilta@uta.fi)

"Wovon man nicht sprechen kann, darüber muss man schweigen"
- Ludwig Wittgenstein, Tractatus Logico-Philosophicus