Re: Can you find anything wrong with this solution to the Halting Problem?
From: Peter Olcott (olcott_at_worldnet.att.net)
Date: 07/12/04
- Next message: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Previous message: Sander Bruggink: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- In reply to: The Ghost In The Machine: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Next in thread: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Reply: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Messages sorted by: [ date ] [ thread ]
Date: Mon, 12 Jul 2004 10:00:47 GMT
> [1] WillHalt() will be algorithmically computed (as opposed
> to magically determined or looked at by a competent -- or
> for that matter totally incompetent -- software engineer).
> Use whatever algorithm model makes sense; there are several
> and they are all equivalent:
>
> - infinite-tape classic Turing machine
> - infinite-tape modified Turing machine, with accepter/rejecter states
> - multiple-tape modified Turing machine (e.g., various pushdown
> automata)
> - infinite-register infinite-size no-memory assembly/machine language
> - infinite-register finite-size no-memory assembly/machine language
> - finite-register finite-size infinite-memory assembly/machine
language
> - anything else that make sense and is equivalent to the above.
>
> [2] WillHalt() will accept as input a public encryption key, and
> will test that the key actually does encrypt (as opposed to
> being an identity transform). This key will be from RSA.
> [3] The output from WillHalt() will be encrypted by the input key.
> [4] WillHalt's() parameters will be encrypted by the *private* key
> (this is the responsibility of the user); WillHalt will be
> required to decrypt them prior to processing.
> [5] WillHalt() can return one of the following values.
> "Yes" -- the program will halt on the given input, eventually.
> (It might take until after the death of the Universe, of course,
> but that counts. :-) )
> "No" -- the program will never halt.
> "Unknown" -- the program cannot be determined to halt given the
> current theory (e.g., the Collatz Conjecture).
> "SelfRef" -- the program contains an implementation of WillHalt().
> (It need not be the same implementation as this version of
> WillHalt().)
> "BadInput" -- the input could not be properly decoded or is not a
> valid machine spec.
That line-of-reasoning has already been addressed.
All that you came up with is another way that the proof
can not be refuted, and it isn't even really another way.
This was one of my initial ideas.
The key is randomly generated by a hardware random
(not pseudo random) number generator. See the original
posting for the details. Since it is a purely random mapping
between meaning and symbol, even an infinite amount
of time would not make it able to be decoded. You either
know the key, or you are bound to fail.
- Next message: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Previous message: Sander Bruggink: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- In reply to: The Ghost In The Machine: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Next in thread: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Reply: Kenneth Doyle: "Re: Can you find anything wrong with this solution to the Halting Problem?"
- Messages sorted by: [ date ] [ thread ]
Relevant Pages
|
