Re: Basis for bypassing the Halting Problem ?




"Joshua Cranmer" <Pidgeot18@xxxxxxxxxxxxxxx> wrote in message
news:jgqb7p$d2p$2@xxxxxxxxxxxxxxxx
On 2/6/2012 7:20 PM, Peter Olcott wrote:
The Turing Machine provides its result as a secret key that is unknown
to anyone except the human that is executing the Turing Machine. If the
secret key is divulged to anyone, besides this human, then the results
can not be relied upon. It seems that the Halting Problem can no longer
be constructed within the context of this basis.

I suspected, after one of my prior responses, that this was something that
you were trying to do.

The Turing machine is useful since it encapsulates everything that all
more powerful models of computations we know of can do while remaining
remarkably simple. This means, in particular, that various apparent
sources of nondeterminism in computational models can be reduced to a
deterministic, framework; from this, we can make stronger guarantees.

In particular, we can determine static properties of the Turing machine
(but not its language), deterministically, without having to run it. Your
goal has been to try to construct a model which produces a "hidden" result
if the input is the Halting problem. However, it is statically knowable
what the Turing machine must eventually output [1], so it's impossible to
have this kind of "hidden" result.

[1] At the very least, we can analyze the machine to know what its types
of output must be as a machine. It is possible that there exists no
strings which could exercise these states in the language, but we could
still obtain a plausible superset of the possible outputs.
--
Beware of bugs in the above code; I have only proved it correct, not tried
it. -- Donald E. Knuth

The result would be a totally random string of arbitrary length, and only
the human user would know what this string means.


.