[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The Halting Problem



>From [email protected] Wed May 12 13:26:04 1993

>I don't see how determining that a particular string is an encrypted
>message reduces to the halting problem. 

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.


Paul E. Baclace
[email protected]