Re: Basis for bypassing the Halting Problem ?

"Joshua Cranmer" <Pidgeot18@xxxxxxxxxxxxxxx> wrote in message
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.


Relevant Pages

  • Re: =?iso-8859-1?q?Re:_Kolmorgorov_Complexity_and_Kim_=D8yhus?=
    ... >>>of the string. ... >> universal computing device, say an universal Turing machine, which IS ... K.C. is defined to require an universal computer, ... >These are different forms of potential compression. ...
  • Re: Recursive language which is not context-sensitive
    ... language which is not context-sensitive: ... sensitive Grammar G and build up a turing machine T which accepts the ... down the 37th context sensitive grammar. ... is just a garbage string? ...
  • Re: Turing Machines and Minds (Was: The Demise of Computationalism?)
    ... number of symbols (since a UTM requires the TM that it emulates to be ... particular Turing Machine that you've placed in front of me?" ... to AIT "information". ... when the input string is the same length as the output string. ...
  • Re: Disproof of the Halting Problems Conclusion
    ... this would be the same text in which Lintz proves that the Halting ... >> language version of the Halting Problem on which it makes sense to talk ... it does not define what a Turing machine is. ... refer to a string, but then talks about "Turing machine M". ...
  • Re: The Halting Problem is based on an ill-formed Question
    ... It's more analogous to asking someone a question IN A LANGUAGE THEY ... set a Turing Machine that knows every natural language on the planet, ... In the cell you would have 0 and in the cell you would ... What does this TM do when given as an input string?? ...