1993-05-12 - Re: The Halting Problem
Header Data
From: peb@PROCASE.COM
To: mab@crypto.com
Message Hash: 21e177047e11aa11aed462d8f754e672af7b5735de5a639c458bc941d881704a
Message ID: <9305122047.AA09694@banff>
Reply To: N/A
UTC Datetime: 1993-05-12 20:47:56 UTC
Raw Date: Wed, 12 May 93 13:47:56 PDT
Raw message
From: peb@PROCASE.COM
Date: Wed, 12 May 93 13:47:56 PDT
To: mab@crypto.com
Subject: Re: The Halting Problem
Message-ID: <9305122047.AA09694@banff>
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
Thread
Return to May 1993
- Return to “Marc Horowitz <marc@GZA.COM>”
- Return to “Matt Blaze <mab@crypto.com>”
Return to “peb@PROCASE.COM”
- 1993-05-12 (Wed, 12 May 93 13:47:56 PDT) - Re: The Halting Problem - peb@PROCASE.COM
- 1993-05-12 (Wed, 12 May 93 14:49:10 PDT) - Re: The Halting Problem - Marc Horowitz <marc@GZA.COM>
- 1993-05-12 (Wed, 12 May 93 15:46:01 PDT) - Re: The Halting Problem - Matt Blaze <mab@crypto.com>