Re: Basis for bypassing the Halting Problem ?

• From: Patricia Shanahan <pats@xxxxxxx>
• Date: Tue, 07 Feb 2012 12:40:29 -0800

Peter Olcott wrote:
On 2/6/2012 11:30 PM, Patricia Shanahan wrote:
On 2/6/2012 5:20 PM, Peter Olcott wrote:
...
Here is an alternative:
The Turing Machine provides its result as a secret key that is unknown
to anyone except the human that is executing the Turing Machine. If the
secret key is divulged to anyone, besides this human, then the results
can not be relied upon. It seems that the Halting Problem can no longer
be constructed within the context of this basis.

Remember that it is not necessary to actually write a program whose
halting the TM cannot decide. The objective is merely to prove that it
exists.

If there is any algorithm that some human could apply to determine
whether the TM says "halts" or "does not halt", then there is at least
one variation on the diagonal program that applies the right test to the
final state of the decider-candidate. That program halts if, and only
if, the decider-candidate ends in a state the human would interpret as
saying it does not halt.

Patricia

The TM reports a random string of random length that only the human user can interpret.

So what? Remember it is not necessary to identify a TM whose halting the
decider mis-predicts. It is sufficient to prove that such a TM exists.

Suppose the proposed decider is machine M1. Consider a diagonal program
that uses M1 in the normal way, but instead of using its result directly
it calls an arbitrary TM M2 with the final state of M1 as input, and
halts if, and only if, M2 terminates rejecting its input.

If the set of states that represent halting is a decidable language,
there exits a TM that, if used as M2, will lead to a program that halts
if, and and only if, M1 says it does not halt. That means there is a
program whose halting M1 mis-predicts, and M1 is not a halting problem
decider.

If the set of final states of M1 that represent acceptance of its input
do not form a decidable language then M1 is simply not a decider at all,
for any language.

Patricia
.