The Halting Problem

[peb at PROCASE.COM]

>From mab at crypto.com 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
peb at procase.com