[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: The Halting Problem

To: [email protected]
Subject: Re: The Halting Problem
From: Matt Blaze <[email protected]>
Date: Wed, 12 May 93 18:33:47 EDT
Cc: [email protected], [email protected]
In-Reply-To: Your message of Wed, 12 May 93 13:47:25. <9305122047.AA09694@banff>


>>From [email protected] 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
>[email protected]
>
>

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

References:
- Re: The Halting Problem
  - From: [email protected]

Prev by Date: Re: The Halting Problem
Next by Date: Re: CALLER ID?
Prev by thread: Re: The Halting Problem
Next by thread: Re: The Halting Problem
Index(es):
- Date
- Thread