From: Matt Blaze <mab@crypto.com>
Date: Wed, 12 May 93 15:46:01 PDT
To: peb@procase.com
Subject: Re: The Halting Problem
In-Reply-To: <9305122047.AA09694@banff>
Message-ID: <9305122233.AA08689@crypto.com>
MIME-Version: 1.0
Content-Type: text/plain



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

Well, that formulation is a bit fuzzy, but I think you've got your reduction
technique backwards.  To reduce something to the halting problem, you
need to show that you could use a machne that solves your problem to solve
halting, not the other way around.

-matt