Re: Basis for bypassing the Halting Problem ?



On 2/9/2012 7:38 AM, Patricia Shanahan wrote:
Peter Olcott wrote:
On 2/8/2012 10:29 PM, Patricia Shanahan wrote:
Peter Olcott wrote:
On 2/8/2012 9:09 PM, Patricia Shanahan wrote:
On 2/8/2012 6:52 PM, Peter Olcott wrote:
On 2/8/2012 8:36 PM, Patricia Shanahan wrote:
On 2/8/2012 6:23 PM, Peter Olcott wrote:
...
The answer will be encrypted differently from run to run such that any
TM simulator would never know what the answer means. This prevents any
TM simulator from creating the Halting Problem.

Remember your TM is being run by a UTM, and the UTM has total control
over your TM's only input, the state of the tape at the start of the run.

Patricia

Sure, but, it still has no way to know what the output means, thus no
way to create the Halting Problem.
The encryption method is specified with encrypted input.

What encrypted input?

Patricia

A string of characters would specify the method used to encrypt the output.

What happens if the UTM that is setting up the tape and running your
machine uses the same string of characters every time?

Patricia
It still has no way to know the meaning of the output, thus no way to create the Halting Problem.
Also if we do not require the tape to be completely erased after every invocation, then the TM can encrypt its output differently every time.

But the UTM running your TM has the option of creating a new tape before
setting up fixed data for anything other than the description of the TM
computation it wants analyzed. Indeed, I see no reason for it to do
anything else.

Under those conditions, I presume the set of final states representing
"it halts" would be a decidable set, there exists a TM that decides it,
and there exists at least one TM computation that your machine gets wrong.

You still don't seem to be getting the point that it does not matter
whether it is possible to identify that machine. It is enough that it
can be proved to exist.

Here's another way of looking at it. Provided someone, somewhere, can
interpret the results, the answer must be a computable function of the
final state of your TM.

Call your TM "M1". There exits a TM, M2, that computes a clear
true/false answer to the question "Does this computation halt" from the
result of running M1 on the description of the computation. Now consider
a TM, M3, that takes a description of a TM computation as input, runs M1
on it, runs M2 with the final state of the M1 run as input, accepts or
rejects its input based on the M2 result.

M3 would be a conventional decider, and the diagonal proof can be
applied to it. Since M3 cannot exist, neither can M1.

Patricia

The decryption only occurs within the mind of the human.

.



Relevant Pages

  • Re: Basis for bypassing the Halting Problem ?
    ... TM simulator would never know what the answer means. ... TM simulator from creating the Halting Problem. ... Also if we do not require the tape to be completely erased after every invocation, then the TM can encrypt its output differently every time. ... true/false answer to the question "Does this computation halt" from the ...
    (comp.theory)
  • Re: Basis for bypassing the Halting Problem ?
    ... TM simulator would never know what the answer means. ... TM simulator from creating the Halting Problem. ... A string of characters would specify the method used to encrypt the output. ... Also if we do not require the tape to be completely erased after every invocation, then the TM can encrypt its output differently every time. ...
    (comp.theory)
  • Re: Basis for bypassing the Halting Problem ?
    ... TM simulator would never know what the answer means. ... TM simulator from creating the Halting Problem. ... The encryption method is specified with encrypted input. ... A string of characters would specify the method used to encrypt the output. ...
    (comp.theory)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... >> Then you suggestion is outside of the scope of the Halting Problem. ... >> It like a stock market analyst that is not allowed to look at stocks, ... You are asking it to analyze ... > the simulator will return the correct value for all inputs. ...
    (comp.theory)
  • Re: Foundation for a Formal Refutation of the Original Halting Problem?
    ... >> Then you suggestion is outside of the scope of the Halting Problem. ... >> It like a stock market analyst that is not allowed to look at stocks, ... You are asking it to analyze ... > the simulator will return the correct value for all inputs. ...
    (sci.logic)