Re: Disproof of the Halting Problem's Conclusion
From: Mitch Harris (harrisq_at_tcs.inf.tu-dresden.de)
Date: 07/21/04
- Next message: Sander Bruggink: "Re: Disproof of the Halting Problem's Conclusion"
- Previous message: Mitch Harris: "Re: Disproof of the Halting Problem's Conclusion"
- In reply to: Peter Olcott: "Re: Disproof of the Halting Problem's Conclusion"
- Next in thread: Sander Bruggink: "Re: Disproof of the Halting Problem's Conclusion"
- Messages sorted by: [ date ] [ thread ]
Date: Wed, 21 Jul 2004 11:15:01 +0200
Peter Olcott wrote:
>
> Find me anywhere where it specifically states that the Halting Problem
> is specifically limited to Turing Machines.
Argh. Many different machine models have a "Halting
problem". For the sake of (an attempt at) rational
discussion, pick a model. The canonical model that is
thought of when the term "Halting Problem" is mentioned is
TMs. When you accuse others of appeal to authority, they're
just using the canonical model (and the canonical proofs).
> It may seem to say this many
> places, yet this is not what it is saying. Find me a place that specifically
> states that the solution set of the Halting Problem is limited to Turing
> Machines, and any other machine that can determine if any program
> will halt or not does not count.
Argh. Just stick to the usual definitions. If you change
something you have to be very explicit so that everybody
else knows what world you live in. That's how math works.
> The only reason that it seems to be limited to Turning Machines,
> is that the problem was defined long before there were any real
> machines.
Argh. That's irrelevant. It's a math problem.
> The historical basis has often been maintained. Most
> importantly, is the Church-Turing (my book ignores Church)
> thesis. It is not supposed to make any difference. TM's are
> supposed to be able to represent anything at all that is computable.
Argh. "Thesis" is a fancy way of saying "well-informed
opinion". And not an opinion of the truth of a proposition
but an opinion as to how something should be defined. The CT
thesis just says that we should all just take TMs to be the
-best- model for computation. How does Church some in? Well,
Church's lambda calculus is another model for computation.
It turns out (this is a formal theorem that is provable)
that these two models (TM's and lambda calculus) can be
implemented in each other, and so have the same
"computation" power. There are a bunch of other models that
are inter-interpretable, and so this supports the CT thesis
(as an opinion) that TM's and lambda calulus at al. are
-all- the best (most appropriate?) models for computation.
> If my requirement of a screen, and protected memory can not be
> discarded, then I disprove both the Halting Problem,
Argh. No, you'll have come up with a new computation model,
(not Turing complete) on which...crap who knows at this
point...for which one has a decision procedure.
> and the Turing Thesis.
Argh. You may have come up with a -new- model that we could
all agree on is a better model for computation. But you
can't -prove- the CT thesis because it is not something that
is true or false.
-- Mitch Harris (remove q to reply)
- Next message: Sander Bruggink: "Re: Disproof of the Halting Problem's Conclusion"
- Previous message: Mitch Harris: "Re: Disproof of the Halting Problem's Conclusion"
- In reply to: Peter Olcott: "Re: Disproof of the Halting Problem's Conclusion"
- Next in thread: Sander Bruggink: "Re: Disproof of the Halting Problem's Conclusion"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
