Set G to a non-recursive language, such as the universal language lu, and an undecidable problem (does a given tm accept a given input) is now decidable in no time flat. Still, undecidable problems remain.
Establish a standard for encoding oracled tms. For instance, state 1 is the start state, and state 2 is the oracle query state, and state 3 is the oracle answer state. With these assumptions, any tm with oracle G can be encoded in the usual way. If you don't want to use the oracle, don't ever move to state 2.
A universal tm can now be constructed. It simulates the tm that is encoded at the start of the tape, acting on the word that follows. A separate track maintains the current state, the position of the simulated head, and the location of the end of the simulated tape. If the simulated tm falls into state 2, the universal tm gathers the word to the right of the simulated head, copies it to the right of its work area, and falls into state 2. It then passes the result, 0 or 1, back to the simulated tm and moves it to state 3. Thus the oracle in the universal tm is invoked whenever the simulation requires an oracle.
As you recall, lu is not recursive, and its complement is not re. The same proof applies here. The universal language, with respect to G, is not recursive, and its complement is not re.
Subsequent theorems, such as the halting problem and rice's theorem, apply. The proofs are based on lu, and are exactly the same, so I won't include them here. The conclusion: no oracled tm is powerful enough to answer questions about other tms with the same oracle.
Given an ntm m1 that uses the oracle G, and recognizes l1 in polynomial time, construct an ntm m2 that recognizes the same language, without using the oracle. It follows the state transitions of m1, except for state 2, which moves to new territory. It evaluates the remainder of the input as a boolean expression, using its traditional, nondeterministic logic. It writes a 0 or a 1 accordingly, and moves to state 3, as though the oracle had been called.
What is the execution time on m2? It can have no more than p regular transitions, courtesy of m1, and no more than p calls to the oracle, which must be handled manually. Each of these calls evaluates an input no larger than p. The resulting bound on execution time, for m2, is a power of p, which is still a polynomial.
Let m3 be a deterministic tm with an oracle G, which does the following. Given a word w, consider the execution of m2 on w. Write a sequence of snapshots, and convert this into a boolean expression. This is an instance of satisfiability, so feed it to the oracle, and report success or failure. Thus m3 accepts the language of m1, in deterministic polynomial time, and p = np, at least for the oracle G.
This generalizes to any np hard problem. For instance, G could be the language of true qbes. With G as oracle, p = np, using the same proof.
In fact, with G as the language of qbes, ps = pt. If m1 is a p space machine, convert it into m2 which recognizes the same language without the oracle. As shown earlier, we can evaluate a qbe in polynomial space, so m2 is a p space machine. Given w, turn the execution of m2 on w into a qbe, another polynomial transformation, and feed the result to the oracle. This can be done in polynomial time, whence ps = pt.
Remember that tms can be encoded, and sorted, without regard to G. (State 2 always invokes the oracle, and moves to state 3, no matter the language of G.) Let m1 m2 m3 m4 etc be an an enumeration of deterministic oracled tms.
Place these machines on a list, so that each one appears infinitely often, for example, m1 m2 m1 m3 m1 m2 m1 m4 m1 m2 etc. When I write listj, I'm refering to the jth tm on this list. Thus listj = m1 whenever j is odd, and listj = m2 whenever j is 2 mod 4, and so on.
We're going to build the language of G by simulating the machines on this list, which in turn call upon the oracle, which tests whether a word is in G. This may look like circular reasoning, but it's going to work out. Sort of like schedule D, which refers to the 1040 form, which refers to schedule D.
We're going to build two lists, Gy and Gn, words that are and are not in G. In the end, G = Gy, but maintaining Gn will help us keep the books.
For each j in sequence, 1 2 3 4 5 etc, run listj on 0j, for jlog(j) steps. The result of this simulation will either place a word of length j in Gy, or it will place a word of length j or longer in Gn. (In rare cases it will do neither.) Thus the words of Gy, and of G, are ordered by length. This makes G a recursive language.
The simulation is straightforward, until the simulated machine calls upon the oracle. Let w be the word to the right of the (simulated) head, the word that may or may not lie in G. Let |w| be the length of w. What we do depends on |w| and j.
If |w| ≥ j, w will not be part of G. The simulation writes a 0, moves right, and enters state 3. Add w to Gn, so that it never appears in G.
If |w| < j, we know which words belong to G. Test w against Gy and write a 0 or a 1 accordingly.
If 0j was not accepted in the time allotted, place a word of length j in G. (Thus G includes at most one word of each length.) Any word will do - so why not choose the least word, in binary. However, make sure you don't select a word from Gn.
It is possible that all words of length j are in Gn, but only for small values of j. Consider the worst case. Each step in each of the previous j-1 simulations adds a different word of length j to Gn. That's the sum of ilog(i), as i runs from 1 to j-1. Each summand is below jlog(j), and there are less than j of these, giving j×jlog(j. Although this increases faster than any polynomial, it is still dominated by 2j. Beyond some j, there are plenty of words to choose from, and we can always find something to add to Gy, that is not forbidden by Gn.
Let the language l contain 0j iff G has a word of length j. This will be np, but not p.
Build an ntm with oracle G that accepts l. Given 0j, crank out any word of length j, nondeterministically, and feed it to the oracle. The machine tries all words in parallel, so it finds the word that lies in G, if there is one, and returns success. This is easily accomplished in polynomial time.
Now suppose deterministic tm listk recognizes l in time p. Each tm appears infinitely often in our list, so we can ratchet k up to a high number. Go beyond the point where the words of Gn might prevent a word from being added to Gy (as described above). Then go higher, so that klog(k) exceeds p(k).
Is 0k in l? Suppose listk accepts 0k, hence it accepts 0k in time p(k), which is below the bound klog(k). There should be no word of length k in G, hence 0k is not in l.
Conversely, assume listk does not accept 0k. This throws a word of length k into Gy, and into G, hence 0k should be part of l.
We have reached a contradiction, hence l is in np, but not in p.
It all depends on the oracle. Some oracles collapse np onto p; others force np > p.
This branch of mathematics is quite theoretical, and I think I'm going to leave it be for now. We thought, at the outset, that it might shed some light on p = np, but as we saw above, that depends on the oracle, so this isn't likely to help. Perhaps wizards have more to offer. A wizard is like an oracle, but different. I hope to bring them online in the near future.
I also plan to bring an assortment of np complete problems online. There are many, representing every branch of mathematics. Wherever you look, you'll find problems that are easily tackled by nondeterminism, but very difficult to solve if you aren't granted a "lucky guess".