[316] in Cypherpunks
Re: The Halting Problem
daemon@ATHENA.MIT.EDU (Marc Horowitz)
Wed May 12 18:11:28 1993
To: peb@PROCASE.COM
Cc: mab@crypto.com, cypherpunks@toad.com
In-Reply-To: Your message of "Wed, 12 May 1993 13:47:25 PDT."
Date: Wed, 12 May 1993 17:49:02 -0400
From: Marc Horowitz <marc@GZA.COM>
>> Consider that the cyphertext is a program for an abstract machine
>> called the cyphercracker which returns TRUE if a message is encoded
>> otherwise FALSE. Such a system for determining message-ness could
>> take an arbitrary amount of cpu time and no amount of static
>> analysis could determine the return value quicker.
Nope. Such a system will take no more than O(2^n) time, where n is
the number of bits in the key. You can never do worse than
brute-force. Now, you still might not be able to determine if a
message is encoded, since maybe I was just encoding true random noise
from a radioactive source. And you might have false positives, too,
esp. with one-time pads. But it will always halt. The failure modes
have nothing to do with the halting problem, they have to do with the
fact that is-encoded(message) cannot be formally defined.
Marc
