Re: What is the Result from Invoking this Halt Function?

From: peter_douglass (baisly_at_gis.net)
Date: 08/31/04 

Date: Tue, 31 Aug 2004 03:05:41 GMT

"Isaac To" <iketo2@netscape.net> wrote in message
 news:87brgwk7yl.fsf@sinken.local.csis.hku.hk...

> >>>>> "peter" == peter douglass <baisly@gis.net> writes:

> peter> Um. We aren't looking at "refutations". We are looking at
> peter> proofs of Halting Theorems that are not tied specifically
> peter> to vanilla Turing Machines.

> The proof itself *is* tied to vanilla Turing Machines.

You write "The" proof. I think this can be criticized on several
grounds. First, for the Halting Theorem for Turing Machines, there
are several proofs. They may be "equivalent" in some sense, but
nonetheless, these proofs have different "qualities" about them.
Second, there are Halting Theorems for other classes of machines
besides Turing Machines. Some of the machines for which there
are Halting Theorems are Turing Equivalent, but many are not.

> There are other variants of the proof which tries
> to extend the proof to other settings.

Yes

> But they are not particularly "useful", in the sense that
> they never prove something that is not already known---

It seems to me that a proof may be useful, even if the
result is in some sense "known". The result may not
be known to a wide audience. Furthermore, the proof may
be more or less "elegent", or more or less "tuned" to
a particular frame of mind.

> ---just because it is possible to reduce the halting
> problem in the vanilla Turing Machine setting into
> the halting problem in the new setting.

Not always. TMs are an abstract theoretical construct, and
we can consider other abstract theoretical constructs,
which may not be Turing equivalent. A proof
of a Halting Theorem for *these* machines cannot
be reduced the case of vanilla Turing Machines.

It might be useful to consider the analogy with
Godel incompleteness. One might be tempted to
"fix" a logical system in which arithemetic is embedded,
by adding new axioms. That doesn't work, however.
Similarly, with the Halting Problem. We can say that
*any* set of machines with a certain set of properties,
*no matter how powerful those machines may be* has
the property that no machine in that set solves the
halting problem for that set.

You may not find this "useful". I think it is a
matter of taste.

--PeterD

Relevant Pages