Re: The Halting Problem is merely an erroneously formed question



On 2/12/2012 11:37 AM, Patricia Shanahan wrote:
Peter Olcott wrote:
On 2/12/2012 9:46 AM, Patricia Shanahan wrote:
Peter Olcott wrote:
On 2/12/2012 9:06 AM, Patricia Shanahan wrote:
I am not leaving out the input data. This is the input data:

if ( TheProgramHalts( String SourceCode ) )
Loop Forever;
else
Exit;

No, I meant the input data for the of SourceCode whose halting we are
testing. Remember SourceCode may represent a TM that halts for some
initial tape contents but halts for others.

// Converted the syntax from declaration to invocation
//
if ( TheProgramHalts( SourceCode ) )
Loop Forever;
else
Exit;

The Halting Problem is essentially that there can not possibly exist any possible implementation of the above referenced: bool TheProgramHalts(String SourceCode) that provides the correct Boolean result when the above program is provided as input to this bool TheProgramHalts(String SourceCode) halt analyzer.

YOU GOT IT!


Although the conclusion is true, it is only true because the above program forms invalid input to the halt analyzer.

It is a correctly formed halting question with an exact true/false
answer. There is no problem with the question unless you start out by
assuming that the TM we are testing is a valid halting decider.

Take another look at the earlier examples I posted of testing TMs that
always return true or always return false. I demonstrated there that
even when the TM we are testing gets the question wrong, another TM,
given the same question reports the correct true/false answer. That
would be impossible if the question had no right answer.

Patricia

No that is incorrect. In the case of the above example input, every instance of any TM gets the wrong answer.

No, remember we use a different test case for each TM under test. Each
test case has a unique correct answer. The test machine in question
either halts or does not halt, and many TMs give the correct answer for
each test case.

For example, the test case we would give a TM that always returns true
would be:

"if ( TheProgramHalts( SourceCode ) )
Loop Forever;
else
Exit;

boolean TheProgramHalts (string SourceCode)
return true;"

The correct answer for that particular program is false.

Of course, the actual construction avoids having to store a literal
containing the entire program text inside the program text. I'm skipping
over all those details for clarity and simplicity - you should be able
to find them on-line or in any text book covering decidability. The
point is that each TM is asked about a different test case, containing a
different implementation of TheProgramHalts.

A TM that always reports true, gets it wrong and a TM that always reports false also gets it wrong.

A TM that always reports true gets some questions wrong, including the
one we use to test it, but gets others right, including the one we use
to test the TM that always reports false.

Similarly, the TM that reports false gets some questions wrong,
including the one we use to test it, but gets others right, including
the example above.

Patricia

if ( TheProgramHalts( SourceCode ) )
Loop Forever;
else
Exit;

My analysis is based on the infinite set of every possible Halt Analyzer against the single instance of input listed above.

Within this infinite set of Halt Analyzers (possible implementations of bool TheProgramHalts( String SourceCode ) ) there does not exist a single element that can provide the correct Boolean {true, false} result for the above single instance of input.

The only reason that none of these Halt Analyzers can provide the correct Boolean {true, false} result for this single instance of input, is that this input is invalid for every element of this infinite set of Halt Analyzers.

Since {true, false} form the exhaustive enumeration of every possible Boolean result and no element from this complete set of all possible results forms a correct answer, the question posed to this infinite set of Halt Analyzers pertaining to whether or not the above program halts is ill-formed.


.



Relevant Pages