Re: Basis for bypassing the Halting Problem ?



On 2/10/2012 10:26 AM, Patricia Shanahan wrote:
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



I think that you were proposing that the TM simulator would guess, and if it guessed wrong then another TM simulator that guessed the other (true, false) answer would be right. That seemed to me what you were saying.


.



Relevant Pages

  • Re: Auto-update protocol
    ... to transfer even with a single client and no interference. ... shared secret/public key is the only way to do the encryption. ... successfully decryption is the authentication. ... you can get using a generic farm server, but TFTP does not have any ...
    (comp.arch.embedded)
  • Re: Securing data to a process principal
    ... encryption key first time for the user - and use it later). ... secret. ... I need the decryption to ... You MAY think that instead of a filter driver you can simply ...
    (microsoft.public.platformsdk.security)
  • Re: embedded keys - there has to be a less vulnerable approach
    ... the database would be run on top of an encrypting file system ... > The use of an asymmetrical encryption algorithm does not seem to offer ... because the encryption and decryption ... > a hostile attacker is not a member of that small knowledgeable elite. ...
    (comp.security.misc)
  • embedded keys - there has to be a less vulnerable approach
    ... the database would be run on top of an encrypting file system ... The use of an asymmetrical encryption algorithm does not seem to offer ... because the encryption and decryption ... You have a table with customer names and addresses. ...
    (comp.security.misc)
  • Re: How to Facilitate and Use Data Protection on DOM (WinCE 6.0)
    ... encryption on and off, while still having the filter load. ... Decryption in my file system filter seems to work fine but the 2nd ... FS filter is NOT APPLIED to Removable USB ... Hard Disk as well as the Removable USB media. ...
    (microsoft.public.windowsce.platbuilder)