Solution to the halting Problem?

[Peter Olcott]

What are you referring to as "a single valid counter-example"? A single

algorithm that can be proven to halt or not halt given arbitrary input?
That isn't what the halting problem means.

Any method to refute the following definition of the Halting Problem:

No program can ever be written to determine whether any
arbitrary program will halt

The logic of the proof is still there, it just has one more link in its
chain.

WillHalt can be constructed
=> WillHalt that returns its result can be constructed
=> The LoopIfHalts function can be constructed based on the
result-returning WillHalt
=> The LoopIfHaltsOnItself function can be constructed
=> LoopIfHaltsOnItself can be applied to itself
=> Contradiction.

Here, I'll go down in history for having just extended the standard
proof to deal with your idea.

Stewart.

bool WillHalt() and LoopIfHalts() only prove that solving the Halting Problem
with bool WillHalt() is impossible. This has been taken to mean that solving the
Halting Problem is impossible. Since void WillHalt() does not get caught in the
double-bind of bool WillHalt(), void WillHalt() solves the Halting Problem.

 

[Peter Olcott]

Ugh, I just posted a long message in another thread, claimed it was going to
be my last, and here I am typing another. I just couldn't let this slide.

That is not the reason that the Halting Problem is a problem. It is a
problem because the analyzing program cannot process specific,
specially-designed input sources that contain logic taken from its own
source because, for those sources, the analyzer cannot produce a result that
avoids a contradiction of the result that would be produced by the stolen,
embedded logic if it were executed. That stolen logic may be modified
slightly to produce return values, but as long as the logic produces the
same result, the problem remains.

The logic does not produce the same result. I cut this from my updated website.
(3) The version of the halt analyzer that returns the result back to its caller and the version of the halt analyzer that does not
return its result back to its caller must determine the same result. They must determine the same result because they both use the
same method, and they both operate on the same data. Since we already know that the first one must fail, therefore the second one
must also fail.

The thing to remember here is that the calling program and the program being analyzed are the same program. If returning a value to
the calling program changes its behavior, then it also changes the behavior of the program being analyzed, because they are the same
program.

If the result is returned to the program being analyzed, and this result changes the behavior of the program being analyzed,
therefore that result of the analysis must also change. If the result is NOT returned to the program being analyzed, then the
behavior of this program is NOT changed, and the result of the analysis is conclusive.

 

[Owen Jacobson]

There is no way to put this nicely: you are completely, 100% incorrect.
The nature of a formal proof is such that a single counterexample
disproves it.

It would be like trying to prove that no cars run by taking one car
and driving it into a tree, so that it does not run. What about all the
cars that were not driven into trees? Don't all these other cars prove
that cars run?

If the thesis was "All cars run correctly." then finding a single broken
car disproves the thesis, even in the presence of an infinite number of
similar, working cars. The halting problem is similar: "There is[0] an
algorithm that can determine if any given algorithm will halt, that will
also itself halt for all possible inputs."[1]

I am not claiming that every implementation of a Halt() analyzer always
works correctly. If I was claiming this then finding a single instance of
a Halt analyzer that does not work correctly would refute my claim.
I am claiming that the Halt analyzer that is implemented according to
my method would work correctly all the time. As proof of this, this
method would correctly process the original Halting Problem, and
determine that it would halt. I will post this example later on.

Ah, but all halt analyzers are equivalent[1]. If you can algorithmically
determine that an algorithm will halt, you _can always_ pass that
information on to another algorithm. The fact that you can choose not to
doesn't impact the fact that you also can. Once it's *possible* to relay
that information to another algorithm, even if you choose not to, the
original proof holds.

Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.

Under the assumption that "any computation that can be carried out
by mechanical means can be carried out by some Turing Machine."
I don't think that it says anywhere in the literature that a solution to
the Halting Problem that can not be implemented as a Turing Machine
doesn't count.

Solving the halting problem by extending the machine past
Turing-equivalent capabilities is uninteresting, as being able to solve
the halting problem for Turing machines is a normal feature of a
more-powerful computing paradigm, for reasons that have been covered
elsewhere. Truly "protected" memory, where it is an error (actually a
final state) to read from, is not a feature of Turing-equivalent machines.

Not at all. The algorithms that test the return value of the Halt analyzer
are no longer in the set of possible algorithms. They become syntactically
incorrect once the Halt analyzer is changed from returning bool, to returning
void (nothing).

(Below I refer to the compound noun 'subjects'; I mean the subject
algorithm M combined with the subject input x.)

Any algorithm that can tell a hypothetical user/observer if the subject
algorithm with the subject input will halt must, by definition, at some
point during its execution contain information about whether the
subjects halt or not. Agreed?

If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed?

This is not the Halting Problem. Also from what I understand this does
not form an analytical impossibility.

No, it's not "the halting problem," it's just an algorithm expressed in C.
But if you've solved the halting problem, you should be able to tell me if
that algorithm will halt.

[0] This is a grotesque generalization and should really read 'all
Turing-complete machines can simulate all other Turing-complete machines'.
However, in the real world there are lots of examples of computers
simulating other computers -- I'm doing some experiments using Bochs, for
instance, which simulates an Intel computer.

[1] If two algorithms produce the same outputs for all inputs, then the
two algorithms are equivalent. They could well be completely different,
internally, but they do the same thing.

[2] I know he's never going to back down on this. This is for fun, not to
try to convince anyone of anything.

 

[Owen Jacobson]

On Thu, 22 Jul 2004 23:08:34 -0400, "David Hilsee"

I suggest you stop here; Olcott is a classic usenet crackpot who
doesn't understand logic. See:

http://www.google.co.uk/groups?safe..._usubject=FastString&as_uauthors=Peter Olcott

Wonder what'd happen if we locked him and Scott Nudds in a room together...

 

[Owen Jacobson]

http://www.netaxs.com/people/nerp/automata/halting2.html This is how the
Halting Problem is defined. The only reason that the Halting Problem is
a problem is that your are required to analyze the same program that is
calling your program.

Wait a moment there, old son. You've said something inconsistent.

Quote (Olcott):
"I don't think that it says anywhere in the literature that a solution to
the Halting Problem that can not be implemented as a Turing Machine
doesn't count."
Message <[email protected]>

Quote (http://www.netaxs.com/people/nerp/automata/halting2.html):
"Theorem. Turing machine WillHalt(M,w) does not exist."
^^^^^^^^^^^^^^
There's a commonly-accepted definition of the halting problem, used in
computer science. Your own link touches on it: there is no Turing machine
or Turing-equivalent machine that can determine if arbitrary programs (and
inputs) for that machine will halt. Proving that a machine more capable
than a Turing machine (which might hypothetically exist; we'll call it an
Oracle machine because it can compute things that a Turing machine can't)
can solve the halting problem is uninteresting with regards to the halting
problem as originally defined.

 

[Peter Olcott]

Ah, but all halt analyzers are equivalent[1]. If you can algorithmically

determine that an algorithm will halt, you _can always_ pass that
information on to another algorithm. The fact that you can choose not to
doesn't impact the fact that you also can. Once it's *possible* to relay
that information to another algorithm, even if you choose not to, the
original proof holds.

Yet only holds for the corrupted version, it does not hold for the uncorrupted
version. The uncorrupted version can even correctly determine that the corrupted
version will definitely halt. This would ONLY form a valid refutation if the
last statement was not true. Since the last statement is true, this attempt at refutation
is analogous to saying I can prove that your program never worked by merely
smashing the computer that it is running on.

Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.

Under the assumption that "any computation that can be carried out
by mechanical means can be carried out by some Turing Machine."
I don't think that it says anywhere in the literature that a solution to
the Halting Problem that can not be implemented as a Turing Machine
doesn't count.

Solving the halting problem by extending the machine past
Turing-equivalent capabilities is uninteresting, as being able to solve

I am not solving the Halting Problem with an imaginary magic machine.
The only capabilities that I am adding are already available in current
hardware. If this solves the Halting Problem, and the original definition
dos not, then I have refuted both the Halting Problem, and the Church-Turing
thesis. Some people have claimed that these additional capabilities are
merely alternate forms of a valid Turing Machine. All they really amount to
are special forms of memory.

the halting problem for Turing machines is a normal feature of a
more-powerful computing paradigm, for reasons that have been covered
elsewhere. Truly "protected" memory, where it is an error (actually a
final state) to read from, is not a feature of Turing-equivalent machines.


(Below I refer to the compound noun 'subjects'; I mean the subject
algorithm M combined with the subject input x.)

Any algorithm that can tell a hypothetical user/observer if the subject
algorithm with the subject input will halt must, by definition, at some
point during its execution contain information about whether the
subjects halt or not. Agreed?
YES.

If it contains that information, it *is* *always* possible to write the
exact same algorithm to the point where that information is present, and
then deviate. Up until the point where they deviate, they are the same
algorithm. At the point of deviation, both contain absolute information
about whether subjects halt. Agreed?
NO.
http://home.att.net/~olcott/halting/index.html#objection03


No, it's not "the halting problem," it's just an algorithm expressed in C.
But if you've solved the halting problem, you should be able to tell me if
that algorithm will halt.

I have not solved every definition of the Halting Problem.
I have only solved the original definition of the Halting Problem.

[0] This is a grotesque generalization and should really read 'all
Turing-complete machines can simulate all other Turing-complete machines'.
However, in the real world there are lots of examples of computers
simulating other computers -- I'm doing some experiments using Bochs, for
instance, which simulates an Intel computer.

[1] If two algorithms produce the same outputs for all inputs, then the
two algorithms are equivalent. They could well be completely different,
internally, but they do the same thing.

[2] I know he's never going to back down on this. This is for fun, not to
try to convince anyone of anything.

 

[Peter Olcott]

Quote (http://www.netaxs.com/people/nerp/automata/halting2.html):

"Theorem. Turing machine WillHalt(M,w) does not exist."
^^^^^^^^^^^^^^
There's a commonly-accepted definition of the halting problem, used in
computer science. Your own link touches on it: there is no Turing machine
or Turing-equivalent machine that can determine if arbitrary programs (and
inputs) for that machine will halt. Proving that a machine more capable
than a Turing machine (which might hypothetically exist; we'll call it an
Oracle machine because it can compute things that a Turing machine can't)
can solve the halting problem is uninteresting with regards to the halting
problem as originally defined.

The NIST standard definition of the Halting Problem does not mention TM's
No program can ever be written to determine whether any arbitrary program will halt
http://www.nist.gov/dads/HTML/haltingProblem.html

It is clear that I am not talking about an imaginary magical oracle machine.
Protected memory, ROM memory, and write only memory already exist
in the real world.

 

[Peter Olcott]

The above paragraph doesn't make sense to me.

The Halting Problem is defined such that the halt analyzer returns
its result back to the program being analyzed, and this program
being analyzed changes its behavior based on this returned result,
which in turn changes the result of the analysis, which changes the
behavior ad infinitum... Merely refraining from returning the result
breaks this otherwise endless chain.

--

 

[Owen Jacobson]

Recall that all computers[0] can simulate all other computers, as well.
So, while your algorithm may be writing to 'the screen' using 'protected
memory', it may be operating in a simulated environment where those two
operations are implemented by simply storing the displayed information for
later retrieval. This does not change your algoritm one iota: a
simulation has *at least* the same characteristics and capabilities of the
original. This simulation could be on any equally-powerful computer.

This is still an important point. No algorithm can determine whether it's
running on a computing machine or a simulation of a computing machine, and
a simulated computing machine can perform extra operations based on the
simulated algorithm without disturbing its operation.

NO.
http://home.att.net/~olcott/halting/index.html#objection03

Non-sequitor. You've answered "Do you agree that it must be possible to
return that information to another algorithm?" I'm asking "Do you agree
that it's possible to write other algorithms that, up to the point where
the information about whether the subjects halt exists, are identical?"

Identical means performing the exact same series of operations on the
inputs, starting from the same state. If you examined what the machine
had already done, and what state it was in *at the point where this
information becomes available*, you would not be able to tell which of
yours or some other algorithm you were examining. Agreed?

I have not solved every definition of the Halting Problem.
I have only solved the original definition of the Halting Problem.

This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate.

 

[Peter Olcott]

Non-sequitor. You've answered "Do you agree that it must be possible to
return that information to another algorithm?" I'm asking "Do you agree
that it's possible to write other algorithms that, up to the point where
the information about whether the subjects halt exists, are identical?"

This answer might not directly apply to your example but since it has
been correct in the previous fifty or more similar cases I will provide it
anyway.

In the specific case of the Halting Problem if the only thing that is changed
is the way that the result is output (returned to the caller, or output to the
screen) just this single difference can change the value of the output itself.

Line 01) void LoopIfHalts(string SourceCode, string InputData)
Line 02) {
Line 03) if (WillHalt(SourceCode, InputData) == TRUE)
Line 04) while (TRUE) // loop forever
Line 05) ;
Line 06) else
Line 07) return; // FALSE or UNKNOWN
Line 08) }

Even though the only thing that is changed is the method of output,
the two function invocations have different return values.
(1) bool WillHalt(LoopIfHalts, LoopIfHalts)
(2) void WillHalt(LoopIfHalts, LoopIfHalts)

If the value is returned from the WillHalt() function to the LoopIfHalts() function
(which is also the program being analyzed), then LoopIfHalts() changes its behavior,
(see line 03) thus changing the result of the analysis. If the value is NOT returned
to the LoopIfHalts() function (which is also the program being analyzed), then
LoopIfHalts() can NOT change its behavior, and the result of the analysis is conclusive
rather than undecidable.

This is a mathematical question, where these differences in wording have
specific meanings. Be very careful, and *always* choose the right words.
What you actually have is "an attempted refutation of Turing's proof that
no algorithm can determine whether any arbitrary algorithm and its input
will halt." Verbose, but much more accurate.

I like this better: I have proven that:

No program can ever be written to determine whether any arbitrary
program will halt

Is not proven.

 

[Karl Heinz Buchegger]

Ah so the user is a slave to the program? I don't buy it.

It doesn't matter what you buy or what you don't buy.
After all the proof doesn't even need to run on a computer.
Forget the physical implementation on a computer, it is not
important in algorithm theory (and BTW cannot be done). The proof
works in a thinking model without the need for actual hardware
like video screens or memory.

I know that this seems like a valid refutation. I also know that it is
not a valid refutation. If this was a valid refutation then it could be
claimed that no program has ever worked, because someone could
always come along and destroy the computer, thus making it not
work.

We are not talking about programs, we are talking about algorithms!

 

[Karl Heinz Buchegger]

Except that the statement below has now been refuted:

No program can ever be written to determine whether
any arbitrary program will halt

Not it has not.

The proof worked the following way:
"Under the assumption that such a function can be written
it has been shown that it cannot be written."

If you modify the proof, you end up with:
"Under the assumption that such a function can be written,
it can be written."

Not a very interesting statement.

 

[Karl Heinz Buchegger]

I never said anything like that. You must be confusing
me with someone else.

Could be.
In this case I apologize.

 

[Karl Heinz Buchegger]

I like this better: I have proven that:

No program can ever be written to determine whether any arbitrary
program will halt

Is not proven.

No, you have not.
There exists a proof for the above sentence. You have prooven something
else. Nobody knows what it is exactly that you have prooven, but it
is definitily not what you think it is. The original proof uses
only accepted methods from prooving theory and thus is without
doubt. Just modifying the proof and hence destroying it, doesn't
make it invalid. It would be a different thing if you can show a flaw
in the *unmodified* proof.

 

[Andrew Heath]

It is my goal to destroy this proof. As long as I can refute this statement:

No program can ever be written to determine whether any arbitrary
program will halt

I have correctly refuted the original Halting Problem proof. The mistake all
along is that returning the result to the caller was NEVER REQUIRED.

Oh so I'm never allowed to actually try and find out if WillHalt()
succeeds or not. Any sort of indication from WillHalt() that it has
succeeded, be it through a return value or printing to a console or
catching fire, is to still return a result. But you say no result is
required, so how will I know there is a result?

 

[Stewart Gordon]

Peter Olcott wrote:

http://www.netaxs.com/people/nerp/automata/halting2.html This is how
the Halting Problem is defined. The only reason that the Halting
Problem is a problem is that your are required to analyze the same
program that is calling your program.

The only thing I can find on that page relating to a function calling
WillHalt on itself is that LoopIfHaltsOnItself(LoopIfHaltsOnItself)
calls WillHalt(LoopIfHaltsOnItself, LoopIfHaltsOnItself). But
LoopIfHaltsOnItself itself doesn't depend on itself at all.

Indeed, the standard proof doesn't require that any function be defined
recursively, as

function Program(input):
if (WillHalt(Program, input)) ...
...

Maybe this is needed for the concept of a 'general solution'. But that
page doesn't seem to state in its definitions whether recursive
functions are allowed. But if they are, then the proof is even easier
than the contortions the standard proof goes through. Just look at this:

function Program(input):
if (WillHalt(Program, input))
while true do {}

Stewart.

 

[Peter Olcott]

Oh so I'm never allowed to actually try and find out if WillHalt()
succeeds or not. Any sort of indication from WillHalt() that it has
succeeded, be it through a return value or printing to a console or
catching fire, is to still return a result. But you say no result is
required, so how will I know there is a result?

I said returning the result to the caller, which means returning the result
to the calling function.

 

[Peter Olcott]

Peter Olcott wrote:

Maybe this is needed for the concept of a 'general solution'. But that
page doesn't seem to state in its definitions whether recursive
functions are allowed. But if they are, then the proof is even easier
than the contortions the standard proof goes through. Just look at this:

function Program(input):
if (WillHalt(Program, input))
while true do {}

Stewart.

That can't work because WillHalt() does not reurn a value to the calling
function.

 

[Andrew Koenig]

That can't work because WillHalt() does not reurn a value to the calling
function.

If it does not return a value to the calling function, then in what sense
can it be said to be determining whether Program(input) will halt?

 

[Stewart Gordon]

Peter Olcott wrote:

That can't work because WillHalt() does not reurn a value to the calling
function.

I'm still waiting to see your example of a function that can't possibly
be modified to return its result.

Stewart.