Re: Basis for bypassing the Halting Problem ?



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
.



Relevant Pages

  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (sci.math)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (sci.logic)
  • Re: Rados Sigma and the Halting Problem for Programs
    ... AD> computer language that does not contrive a logic paradox ... Halting Theorem may be proven without recourse to reductio ... computation halts, and is bottom, i.e. _|_ if the computation diverges ... Assume that from a Turing Machine M we can construct a Turing Machine ...
    (comp.theory)
  • Re: Validating Natural Language Statements (and Mathematical Propositions)
    ... decider neither true nor false is correct." ... I am talking about the specific subset of Turing Machines that can not ... The specific subset of Turing Machines that cannot decide the halting ... TM halts on that input. ...
    (sci.logic)
  • THE HALTING PROBLEM IS BASED ON AN ERROR SHIFTING FROM TMs TO 3GL FUNCTION CALLS
    ... There IS NO "self-reference form of the halting problem". ... HALT or NOT. ... A TM DECIDER OUTPUTS ITS DECISION THEN HALTS. ...
    (sci.logic)