Ben Laurie wrote:
Such a machine cannot exist. Proof:
Let O be an oracle such that any encrypted message, E can be decrypted by O. That is, if E=Enc(M), then O(E)=M. Now, encrypt a message I as follows.
Let S be the set of all bitstrings. Let, C, the set of all ciphers, be the set of all finitely denumerable primitive recursive injections of S into itself. Let O, our oracle, associate with each M in C a map M', from range(M) onto S, such that for x,y in S and y = M(x), x = M'(y).
If bit 0 of I (I_0) is 1, then choose E_0 s.t. the MS bit of O(E_0)=0 If bit 0 of I is 0, then choose E_0 s.t. the MS bit of O(E_0)=1
Then for each subsequent bit, proceed as follows:
If I_n is 1, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 0. If I_n is 0, then choose E_n s.t. O(E_n||E_{n-1}||...E_0) has an MS bit that is 1.
Then the encrpytion of I is X=E_N||E_{N-1}...||E_0, and, by construction, O(X) != I.
Bzzzzzzzzzzzzzzzt. While we may without loss of generalization view O as acting on bitstrings, by encoding the ciphers and their inverses, neither the domain nor range of O is going to be the set of all bitstrings. Ergo, we can not simply "choose" things based on the application of O to bitstrings we arbitrarily construct. Your proof can be fixed, of course, but I think you'll find that it boils down to the usual diagonal argument that we can find a function on the integers which is not primitive recursive, by ordering the countable set of primitive recursive functions, and defining a new function that is for an input of N, something other than the output of the Nth function for N. As long as we restrict the ciphers to a countable set of "reasonable" computer programs which halt for all inputs and don't have neverending descriptions, the oracle exists, and your proof does not.
Cheers,
Cheers, -- Eric Michael Cordian 0+ O:.T:.O:. Mathematical Munitions Division "Do What Thou Wilt Shall Be The Whole Of The Law"