Re: Basis for bypassing the Halting Problem ?



On 2/10/2012 7:56 AM, Peter Olcott wrote:
On 2/9/2012 11:08 PM, Patricia Shanahan wrote:
Peter Olcott wrote:
On 2/9/2012 5:35 PM, Patricia Shanahan wrote:
On 2/9/2012 3:09 PM, Peter Olcott wrote:
...
The decryption only occurs within the mind of the human.


That may be your intent, but in order for a human to do the decryption
the meaning must a computable function of the final state of your
machine and whatever encryption key the UTM running your machine
chooses
to put on the tape.

For every computable function, there is at least one TM that computes
it, and that TM, composed with your TM, would form a conventional
halting decider.

Unless you reject the Church-Turing thesis, and hold that there are
effectively calculable mathematical functions that no computer program
in any existing language could ever compute? If so, we are too far
apart
in our assumptions for any chance of reaching agreement.

Patricia

Unless the computer program is a mind reader it can not discover
secrets held only within my mind.

The problem is thinking about *the* computer program. The real question
is whether there is *a* Turing machine that converts your machine's
output to a clear accept/reject answer.

Suppose your machine represents its answer as 0 for "halts", 1 for
"does not halt". It concatenates the result bit with a hash of its
input, to avoid always encrypting to a consistent pair of values. It
then encrypts with a key only you know.

In the universe of all Turing machines there is one decrypts its input
with the right algorithm and key 0, and accepts if and only if the first
bit of the answer is 0. There is another just like it, but using key 1.
Indeed, for each natural number n, there is one just like it except for
decrypting with key n.

Applying one of those machines to the output of your machine would
result in a conventional decider for the halting problem. That is, the
combined machine will accept a Turing machine computation if, and only
if, you would say that computation halts given the result of running
your machine on that input.

That machine is wrong about at least one Turing machine computation, so
the combination of your machine's calculation and your post-processing
is also not a halting problem decider.

I don't know which machine is the right post-processor, because I don't
even know the encryption algorithm, let alone the key. That does not
matter. If the calculation you apply to the result is a computable
function, some TM computes it.

Patricia

Even the Halt Analyzer can not decrypt its own answer, it can only
encrypt it.
Only the human can decrypt the answer because the decryption depends
upon information only held within the mind.
The best that any possible TM Simulator could do (from the set of all
possible TM simulators) is guess.

I don't think there is any point continuing this, because you are not
really reading and answering my articles. I dealt with the issue of a
hidden decryption algorithm and decryption key, in detail, in the quoted
material.

Patricia


.