Rudy's Blog

Buy Rudy's books! Click covers for info.                 Blog text and images copyright (C) Rudy Rucker 2018.


Lazy Eight and the Turing Oracle

Suppose the eighth dimension is normally curled around into a Planck-length circle, but that some perturbation or magic spell unrolls it to infinite length. And suppose as well that it’s psychically possible to overview the whole infinite expanse of the eighth dimension in a finite amount of time. Also suppose that all the eighth-dimensional lines meet at a point.

I will use the phrase “lazy eight” to speak of this change. It combines: eighth dimension, infinity as ∞, and the fact that infinity is “right here” in the eighth dimension as an ubiquitous lazy-man’s enlightenment. So we have an infinite extra dimension at every point. Yet the infinite expanse is accessible; you can reach any location along it in some fixed time.

It’s like you took the vanishing point of a painting and made it be at every point in space. The point at infinity is present everywhere. It’s like being with God. The accessible point at infinity acts as an entanglement channel that connects every point with every other point in synchronicity.

New topic.

I’ve been thinking about Alan Turing’s halting problem. The halting problem is this: Find an oracle such that given any arbitrary computation C, the oracle will in a finite amount of time tell you if a computation C is going to halt or run forever. And we can refer to such an oracle as a Turing Oracle. Turing proved that no computation can act as a Turing Oracle. That is, no computation can serve as an oracle that can tell you whether or not an arbitrary computation will run forever.

Perhaps there could be a Turing Oracle, but its operation would have to involve something other than normal computation-like physics. One option I’ve been thinking of is lazy eight, which I mentioned above.

If lazy eight gives you infinite consciousness, then you could in fact solve the halting problem, as all the infinite searches could be done in finite time. We could in fact have a fixed-time Turing Oracle that always gives you that yes or no answer within some fixed time, say one second. Call this a Strong Turing Oracle.

In Accelerando, Charles Stross boldly writes, “New discoveries this decade include … experimental implementations of a Turing Oracle using quantum entanglement circuits: a device that can determine whether a given functional expression can be evaluated in finite time.”

But Stross doesn’t really delve into what the implications would be. So now I ask you, what would it be like to have a Strong Turing Oracle in hand?

Given any mathematical statement S, I could decide whether S is a provable theorem. I fix on a particular axioms system for mathematics and I define a computation ProofSearch(S) that searches through all possible proofs from these axioms, looking for a proof of S. And I’d feed the ProofSearch(S) computation to my Turing Oracle. If the Oracle tells me that ProofSearch(S) halts, I know that S is provable. If the Oracle tells me that ProofSearch(S) runs forever, I know that S isn’t provable.

Given any possible story S, I can decide if this a story I would ever write. I create an AI model of how I think and write. And I define a computation RuWriteSearch(S) that searches through all possible “creative processes” carried out by the AI model, looking for a process that terminates with writing the story S. And I’d feed the RuWriteSearch(S) computation to my Turing Oracle. If the Oracle tells me that RuWriteSearch(S) halts, I know that S is a story I might write. If the Oracle tells me that RuWriteSearch(S) runs forever, I know that S isn’t a story I would write.

Given any possible scientific theory S, I can decide if this a theory we might adopt. Again I create an AI model of human scientific thought, feed a ScienceSearch(S) computation to the Turing Oracle, and discover whether or not S is a possible future theory or is out of the question.

Lazy eight and the ability to do an infinite search in a fixed amount of time leads to a Strong Turing Oracle. Could the implication run the other way? Could the discovery of the Turing Oracle lead to lazy eight? I mean science-fictionally speaking.

New topic.

Note that having a Turing Oracle is much weaker than having a Truth Machine computer TM such that if S is any sentence in number theory TM(S) outputs a True or False to tell us whether S is true. The Turing Oracle only decides provability, not truth.

We can’t solve the truth question with a single infinite search because arbitrary sentences of number theory have alternating quantifiers that set off nested searches within searches. Perhaps if you had a transfinite time line to work with you could do this, that is, if you could fold together infinitely many infinite searches.

Suppose I let the variables x and y range over the integers. If you had infinity times infinity seconds to play in, you could check the truth of “(for all x)(there is a y)P(x,y)”. You set off a fresh infinite search for each value of x. As it nests deeper the ordinals would stack up. Is that what Gentzen was talking about when he spoke of the ordinal epsilon-zero in the context of proof theory? I never really studied that work.

What would it be like, SF-wise to have a truth machine. The War Against the Rull. Our Flooping Federated Galactic Goobs have a Turing Oracle, but the Rull have a Truth Machine! Looks like the home team is in for it! But wait…

3 Responses to “Lazy Eight and the Turing Oracle”

  1. Steve H Says:

    Hmmmm…..argh…..whoa. I just grew another wrinkle on my brain trying to visualize that. Suppose there was an interface of some kind that let you perceive the lazy-8 state without actually having to unroll spacetime? Maybe that’s what psychics are doing?

  2. John Reynolds Says:

    I am a bit confused. First of all, it is my understanidng that there is actually a hierarchy of Turing Oracles, so that if one has an Oracle for the Halting Problem on a Turing Machine, that Oracle cannot solve its own Halting Problem; an Oracle at the next level of the Hhierarchy is needed for that purpose.

    Secondly, it seems to me that the Truth Machine is indeed much more powerful than any Turing Oracle (at any finite level of the Turing Oracle hierarchy); however, this is only true if we fix the number of bits in the axioms of the formal system wherein the Turing Oracle examines possible proofs. Am I mistaken in this belief? If we allow the size of the Axiomatic System to be unbounded then isn’t the Turing Oracle able to establish the truth of any proposition of Number Theory just as well as the Truth Machine?

    Of course, the problem is that human mathematical ingenuity is only able to create axiomatic systems of limited length, and the indefinite extension of this ability is presumably what a Truth Machine provides. Am I correct?

    ==John R

  3. Rudy Says:

    John, this is a tricky topic, you might look at the Appendix to my Lifebox tome for more info. I’ll make one response now, but it would not be fruitful to try and work all this out in a comment thread, so I probably won’t respond on this topic again.

    A turing oracle tells you if a given computation will halt or, which is equivalent, if a given S is provable from a given theory T. The complexity of the theory T doesn’t matter nor does the size of the axioms, you’re mistaken in thinking that makes a difference. Any normal mathematical theory’s axioms can be listed by a Turing machines, so the notion of provability can be formulated in terms of TMs as well.

    It is however true, that if you add a new “Turing Oracle” primitive to your language, you can get a richer set of theories and a new type of Turing machine that’s allowed to consult the Turing oracle, so, as you say, you get into a regress that goes on as long as you like.

    Finally, a Truth Machine is, as I say, a much stronger concept than a Turing Oracle. Due to undecidability, there will be sentences that are true but not provable or disprovable.


Rudy's Blog is powered by WordPress