Re: Disproof of the Halting Problem's Conclusion

From: Sander Bruggink (bruggink.at.phil.uu.nl_at_no.spam.please)
Date: 07/21/04 

Date: Wed, 21 Jul 2004 11:49:26 +0200

Peter Olcott wrote:
> Find me anywhere where it specifically states that the Halting Problem
> is specifically limited to Turing Machines. It may seem to say this many
> places, yet this is not what it is saying.

So, what you're saying is: you have already found places where the
problem is restricted to Turing machines, but you just don't believe
them. Instead, you believe the definition of a non-scientific website.

> 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.

This has already been pointed out to you: the proof holds in the same
form for any Turing-complete language, including, but not limited to:
Lambda Calculus, PCF, the language "WHILE", register machines, recursive
functions, combinatory logic, term rewriting systems, and all modern
programming languages (assuming infinite memory). All these formalisms
are equivalent in computing power.

Note that we are talking about *computing* *functions*. We are
specifically not intereseted in user input during the computation. Users
are strange objects about which it is impossible to prove theorems.

> 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.
>
> If my requirement of a screen, and protected memory can not be
> discarded, then I disprove both the Halting Problem, and the
> Turing Thesis.

No. The Church-Turing thesis is a *definition*, not a *theorem*. You can
either agree with it or not. But you can't "disprove" it.

groente
-- Sander

Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... > is specifically limited to Turing Machines. ... > states that the solution set of the Halting Problem is limited to Turing ... Your requirement of a screen and protected memory completely ignores the ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... >> is specifically limited to Turing Machines. ... >> states that the solution set of the Halting Problem is limited to Turing ... > Your requirement of a screen and protected memory completely ignores the ...
    (sci.logic)
  • Re: Can computing relative to an oracle machine create a contradiction?
    ... Is it true that computing relative to a given oracle machine can ... An oracle O which is capable of deciding whether a given Turing ... of the same proofs that apply to Turing machines. ... can decide the halting problem for Turing + O machines will have its ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... > Find me anywhere where it specifically states that the Halting Problem ... > is specifically limited to Turing Machines. ... Argh. ... > states that the solution set of the Halting Problem is limited to Turing ...
    (sci.logic)
  • Re: Yet another Attempt at Disproving the Halting Problem
    ... >analyzer that always returns a correct result back to the program being ... You haven't refuted Turing, you've changed the ... "solve the halting problem", you are free to do so. ... So your approach to producing a pink elephant is to build a dark ...
    (comp.theory)