[313] in Cypherpunks
Re: The Halting Problem
daemon@ATHENA.MIT.EDU (peb@PROCASE.COM)
Wed May 12 17:10:21 1993
Date: Wed, 12 May 93 13:47:25 PDT
From: peb@PROCASE.COM
To: mab@crypto.com
Cc: cypherpunks@toad.com
>From mab@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@procase.com
