Re: Alan Turing's Halting Problem is Incorrect (FINAL PART)

From: Chris Menzel (cmenzel_at_remove-this.tamu.edu)
Date: 07/11/04 

Date: 11 Jul 2004 01:18:32 GMT

On 10 Jul 2004 04:36:12 -0500, Acme Diagnostics
<LFinezapthis@partpostmark.net> said:
> Chris Menzel <cmenzel@remove-this.tamu.edu> wrote:
> >On 7 Jul 2004 13:05:04 -0500, Acme Diagnostics <LFinezapthis@partpostmark.net>
> >> "Peter Olcott" <olcott@worldnet.att.net> wrote:
>
> >Larry, the Halting Problem applies to "real" computers as much as Turing
> >machines, and can be formulated in terms of actual programming
> >languages.
>
> I'm specifically interested in the C program at this U. of Maryland
> CS dept. page, also repeated on some other sites:
>
> http://www.csee.umbc.edu/~squire/cs451_l26.html
>
> Is diagonal.c a good demonstration of the Halting Problem on
> real computers?

I'd put it a bit differently: it's a good demonstration of the
unsolvability of the Halting Problem for a real programming language.
The Halting Problem isn't really about computers, at least not directly,
but about the class of questions we are capable of answering
algorithmically. Of course, this has *implications* for computers --
since there is no algorithm for solving the Halting Problem, no
computer, real or imagined, can be programmed to solve it.

> >Fortunately, there are many excellent, reader-friendly alternatives on
> >the web, notably, the Stanford Encyclopedia of Philosophy article on
> >computability:
> >
> > http://plato.stanford.edu/entries/computability
> >
> >The Wikipedia entry is also quite good, with lots of links to related
> >concepts:
> >
> > http://en.wikipedia.org/wiki/Halting_problem
> >
> >And, of course, there are many fine texts that cover the problem in
> >detail.
>
> I only have one question:
>
> Is there any *linkable* proof of the Halting Problem for *real
> computers* that does not contrive a logic paradox to make the proof?

I'm afraid I don't really understand the question. First, as noted, the
emphasis on "real computers" here is a red herring. Second, there is
nothing contrived about the proof, and in particular there is no logical
paradox. A paradox is an argument in which a contradiction follows from
premises that we find intuitively true. Genuine paradoxes are
disturbing, as they show that one has a false belief, as true premises
cannot entail a contradiction. The proof of the unsolvability of the
Halting Problem also involves an argument to a contradiction -- it is,
in fact, an instance of the general *method* of proof by contradiction,
a.k.a. "reductio ad absurdum", a ubiquitous form of reasoning used
throughout the history of mathematics: Infer not-A, if the assumption
that A is true leads to a logical absurdity. Thus, for instance, in the
usual proof that sqrt(2) is irrational, we assume that it is not, i.e.,
that there are relatively prime integers m,n such that sqrt(2) = m/n.
We then deduce a contradiction (e.g., that m and n are not relatively
prime after all), and conclude that our assumption was false. And in
the case of the Halting Problem: Assume you've got a program H that can
tell you if an arbitrary program P halts on input I. On that
assumption, it follows that you can construct a program (Diagonal.c)
that halts on a certain input (viz., Diagonal.c itself) iff H says it
doesn't halt on that input. So our assumption that there is such a
program as H must be false. The difference between this and a genuine
paradox, then, is that the assumption from which the contradiction
follows does not have any particular intuitive hold on us ahead of time;
whether there is such a program as H just seems like an open question,
which the proof then answers. Hence, the argument in the proof is no
genuine paradox.

Chris Menzel

Relevant Pages

  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... >unsolvability of the Halting Problem for a real programming language. ... with computers. ... A paradox is an argument in which a contradiction follows from ...
    (sci.logic)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... I have no interest in the Halting Problem on Turing ... computers, only on real ones. ... contrive the same logical paradox to make the counterexample? ... being invested and competitive in the one theoretical logic context. ...
    (sci.logic)
  • Re: A modern view of the halting problem
    ... Turing did basically introduce turning machines as a formal way ... Entscheidungsproblem could be recast as the halting problem, ... And of course the results have no special relationship to computers. ... the halting problem is something of a triviality (just like ...
    (alt.lang.asm)
  • Re: A modern view of the halting problem
    ... The generalized proof of undecideability (the generic problem posed by ... the halting problem) does *not* apply to humans. ... Machines* (an abstract model which models all real computers, ... on the claim that a disassembler cannot differentiate code and data, ...
    (alt.lang.asm)
  • Re: Alan Turings Halting Problem is Incorrect (FINAL PART)
    ... the Halting Problem applies to "real" computers as much as Turing ... on what they can compute is obviously inherited by real machines. ...
    (sci.logic)
Loading