I had a feeling in yesterday’s blog entry that I was missing something so on I emailed the young computation-wizard Scott Aaronson. Scott has a number of interesting avatars on the Web, such as his blog, and his “Complexity Zoo” now in wiki format. Scott was actually helpful enough to reach through the second-to-last draft of my Mathematicians in Love to find logical holes in it, by the way. His articles can be a bit abstruse, but I’m planing to study “Quantum Computing for High-School Students” next time I feel really smart!

Anyway, yesterday I asked Scott about his thoughts on the Turing Oracle, as I half-remembered a conversation I’d had with him about it in San Jose last year.

Scott answered:

It looks like you've covered the “stoner” implications of a halting oracle about as well as I could have. (“Sure, you could instantly find any mathematical proof, create an AI model of a human being that best matches his or her observed behavior, and indeed, simulate the entire physics of the known universe, but what could you REALLY do?” )

Unless you had a more specific question, I'll confine myself to one remark, which is that you could already get plenty of zany implications with an oracle for NP-complete problems (forget about the halting problem!). See my paper “NP-complete Problems and Physical Reality” for more about this point.

I answered:

“Stoner” implications! Harrumph. Possibly the fact that my previous blog entry was about Wm. Burroughs fosters this impression…

What I REALLY want is a way to finish my new novel without having to write it.

You you give me hope in your remark that with a Turing Oracle, I could create an AI model of myself that best matches my observed behavior. Aha!

Mulling this over today, I get the following line of thought. The weakest kind of Turing Oracle form it tells me in some finite but unbounded-in-advance amount of time whether or not a given computation C will halt. In a stronger form, there is some fixed finite amount of time such that the oracle always returns its answer within that amount of time.

Now let’s postulate a still stronger magic tool, a Turing Evaluator or TE. There is a fixed finite amount of time such that within that amount of time TE me (a) whether a given computation C will halt and, (b) what was the final output of C, in the case that C does halts.

A Turing Evaluator tells me more than whether the computation C halts, it gives me a short-cut for finding out what C does.

Another way to express what a Turing Evaluator does: Whenever I want to search through the integers for a special integer Special_N having some property, then TE will quickly tell me the value of the smallest such Special_N, and if there is no such integer it’ll tell me that as well.

There’s a well-known method for coding up pairs or triples or n-tuples of integers as single integers, so I can in fact be searching for several integers at once.

Suppose I’m given finite string of integer variables u, v, … z and a property Good(u, v, … z). I want to find if there are any specific values Nu, Nv, … Nz which satisfy Good. I can use my Turing Evaluator to discover in some fixed amount of time whether or not this is the case, and if it is the case, my Turing Evaluator will return examples in the form of Special_Nu, Special_Nv, … , Special_Nz.

So now I see how to use my Turing Evaluator to write my seventeenth novel Ru_17 (also called Postsingular) as follows.

(i) Code up my first sixteen novels as constant numbers cRu_1, … , cRu_16.

(ii) Establish a system for listing possible neural-net-based AI programs for simulating my writing a novel, list the variable code numbers as FakeRu_1, FakeRu_2, … FakeRu_x, …

(ii) Let y be a variable integer that might code up my next novel.

Define a predicate Good such that Good(Ru_1, …, Ru_16, FakeRu_x, y) means that FakeRu_x codes an algorithm such that, FakeRu_x generates the known novels Ru_1, …, Ru_16, as its first sixteen “novels,” and FakeRu_x generates y as its seventeenth “novel.”

So I apply my Turing Evaluator and get specialFakeRu_x and Special_y, which I can then mail in to David Hartwell at Tor as Ru_17, a.k.a. Postsingular.

Sure, Rudy, sure.

Meanwhile, I’ve finally, sob, finally finished revising Chapters 1-3, and figuring out the outline for Chapters 4 and 5, so now I can continue generating Ru_17 the hard way.

Um … write today? Hell with that. It’s 100 degrees here. I’m heading for Cruz.

This entry was posted on Thursday, June 22nd, 2006 at 8:24 am and is filed under Rudy's Blog. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.