The Halting Problem

[Matt Blaze]

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

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