From: Marc Horowitz <marc@GZA.COM>
Date: Wed, 12 May 93 14:49:10 PDT
To: peb@PROCASE.COM
Subject: Re: The Halting Problem
In-Reply-To: <9305122047.AA09694@banff>
Message-ID: <9305122149.AA11140@dun-dun-noodles.aktis.com>
MIME-Version: 1.0
Content-Type: text/plain


>> 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