FANDOM


Super-oracle

The first step in my extension is defining a super-oracle: an oracle that can diagonalize over any number of normal oracles. If the TM comes in the ASK status, the super-oracle does the following things:

  • It counts the number of non-blank symbols. Call it x.
  • It simultates TM#x.
  • If TM#x halts, the super-oracle sets the turing machine in state YES. If it doesn't halt, the super-oracle sets the turing machine in state NO.

Numbering for TM#x: First the 1 state 0 oracle TMs, then 2 state 0 oracle TMs, 1 state 1 oracle TMs, 3 state 0 oracle TMs, 2 state 1 oracle TMs, 1 state 2 oracle TMs, etc.

Next would be a TM with 1 oracle and 1 super-oracle, this BB function has grow rate \(\omega^{CK}_{\omega+1}\)

We can also have a TM with 2 super-oracles, this BB function has grow rate \(\omega^{CK}_{\omega2}\)

The limit of this idea is \(\omega^{CK}_{\omega^2}\)

Higher level oracles

We can also define a hyper-oracle that diagonalizes over super-oracles. The hyper-oracle is a level 3 oracle. We can continue with higher level oracles, the limit of this idea is \(\omega^{CK}_{\omega^\omega}\)

Oracle tape

We can have an additional tape which can write oracles. We have two tapes, two heads and two rulesets. This BB function has grow rate \(\omega^{CK}_{\omega}\), but we can diagonalize over it using an oracle. That oracle can also be an oracle tape. Similiar, we can extend to n tapes, the limit of this idea is \(\omega^{CK}_{\omega^2}\).

Putting these things together

In this variant, the oracles on the oracle tape also have a counter. The counter counts the number of times that the head reads the oracle. The number on the counter is the level of the oracle.

I think this function has grow rate \(\omega^{CK}_{\omega^{CK}_1}\) with 1 oracle tape and \(\alpha \mapsto \omega^{CK}_{\alpha}\) with n oracle tapes

Ad blocker interference detected!


Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.