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