Re: Basis for bypassing the Halting Problem ?



On 2/6/2012 5:29 AM, Peter Olcott wrote:
On 2/5/2012 11:03 PM, Joshua Cranmer wrote:
On 2/5/2012 9:40 PM, Peter Olcott wrote:
What I am proposing is to {add one element to Q and to transition to
this element} only upon recognizing an instance of what would otherwise
be the Halting Problem. The Halting Problem can no longer be formed
because the state that must be modified to create the Halting Problem
does not yet exist.

Turing machines are not self-modifying code, so you cannot tell it to
"add a state."

I have not seen this in specific restriction within any of their
specifications.

If this restriction is in their specification, then it would seem to
form a lack of correspondence to actual hardware machines, thus making
them less than an ideal model of computation.

Considering that Turing machines can't model random access efficiently, nitpicking on a "limited" model because it isn't self-modifying is rather pointless.

The use of Turing machines is because they are a very simple model of computation that can emulate all known models of computation. Indeed, a self-modifying Turing machine can be emulated with a Turing machine, via use of the Recursion Theorem (which says, informally, that "get the description of this Turing machine" is a possible operation).

Now, that said, this still does not run around the Halting problem for two reasons:
1. "Detect an instance" is impossible, as proving that the languages of two Turing machines is equivalent is undecidable.
2. Ultimately, you still get into the boolean state of either you accept it or you do not. The state of "runs forever" is not desirable (indeed, the Halting problem is recognizable but not decidable). Such a program would still be "defeatable" using the standard diagonalization argument.

--
Beware of bugs in the above code; I have only proved it correct, not tried it. -- Donald E. Knuth
.



Relevant Pages

  • Re: Disproof of the Halting Problems Conclusion
    ... >>WillHaltthat permit LoopIfHaltsto function does not refute this ... Your method is founded on the idea that LoopIfHalts ... > There are two programs in the Halting Problem: ... Turing Machines or something equivalent ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... >>WillHaltthat permit LoopIfHaltsto function does not refute this ... Your method is founded on the idea that LoopIfHalts ... > There are two programs in the Halting Problem: ... Turing Machines or something equivalent ...
    (sci.logic)
  • Re: Disproof of the Halting Problems Conclusion
    ... A simple exposition of the Halting Problem has ... Not unless you can find a flaw in the original proof. ... > necessity to return the result of the halt analyzer to its caller. ... nothing to do with Turing machines or Turing complete programming ...
    (comp.theory)
  • Re: Disproof of the Halting Problems Conclusion
    ... A simple exposition of the Halting Problem has ... Not unless you can find a flaw in the original proof. ... > necessity to return the result of the halt analyzer to its caller. ... nothing to do with Turing machines or Turing complete programming ...
    (sci.logic)
  • Re: The proof that I was referring to is on the website
    ... >> I can directly contradict a widely held definition of the Halting Problem. ... Mathematical equations neither halt nor fail to halt. ... halt function to choose to refrain from providing a result. ... >> the purely mathematical proof in its application to Turing Machines. ...
    (comp.theory)