FANDOM


Warning: I'm going to use concepts from computability theory which I'm not going to describe in great detail (mainly Turing degrees), so if interested, I recommend first of all checking out what the idea behind Turing degree is, and for other things feel free to ask in comments.

So, I have recently been wondering, is it possible to have a function \(F\) which is, in fundamental way, inbetween all computable functions and the busy beaver function (for simplicity, let it be \(S(n)\)).

Turns out, as expected, that the answer depends on what we precisely mean with "fundamentally between". There is quite intuitive notion for this, but I'd rather go about making it more formal.

First, I want my function to be above all computable functions. Two most obvious formalizations for this intuitive notion are:

  • \(F\) dominates all computable functions, which means that for any computable function \(f\) and sufficiently large \(n\) we have \(F(n)>f(n)\).
  • \(F\) isn't bounded by any any computable function, i.e. no computable function \(f\) satisfies, for all \(n\), \(F(n)<f(n)\). Equivalently, \(F\) isn't dominated by any computable function.

Of course, first one implies the second.

Next we want \(F\) to be below \(S\). But thing like \(F(n)=S(n)-1\) isn't at all satisfactory, because we can still reach \(S\) with \(F\). We actually want \(S\) to not only be above \(F\), we would like it beyond all recursive extensions of \(F\). More formally, again I had two ideas:

  • \(S\) dominates all functions computable with \(F\).
  • \(S\) is not bounded by any function computable with \(F\).

Again, first implies second.

Optimally, we want \(F\) to dominate computable functions and \(S\) to dominate all \(F\)-computable functions. This, however, is impossible. There is a theorem, called Martin's domination theorem, which says that, if we have Turing degrees \(A,B\) then there is a \(A\)-computable function which dominates all \(B\)-computable functions if and only if \(A\) is high above \(B\), i.e. \(A'\geq_T B' '\) (the proof uses the fact that \(B' '\) is Turing-equivalent to set of machines which \(B\)-compute total functions).

So if the optimal scenario held, we would need to have that \(F'\geq_T 0' '\) and \(S'\geq_T F' '\geq_T 0' ' '\). But \(S\equiv_T 0'\) and \(0' '\not\geq_T 0' ' '\). So it's impossible.

Other cases, however, can hold. First I'll construct a function \(F\) which isn't bounded by computable function and \(S\) dominates all \(F\)-computable functions. For this, let's take \(A\) to be any undecidable recursively enumerable set which is not array nonrecursive ("array nonrecursive" means that for every function \(f\leq_\text{wtt}0'\) (weak truth-table reductions), there is an \(A\)-computable function \(g\) which is not dominated by \(f\)) (construction can be seen here). Because \(A\) is r.e. there exists a total computable function \(a\) such that elements of \(A\) form the range of \(a\). Now I define \(F(n)\) as: the least number such that, for every \(m\leq n\), if \(m\) is in \(A\), then there is \(k\leq F(n)\) such that \(a(k)=m\). Less formally, if \(a\) sees that \(m\in A\), then it sees so with at most \(F(n)\) entries.

Now, assume that there exists an \(F\)-computable function \(f\) which infinitely many times outgrows \(S\). We will show that \(f\) is array nonrecursive, contrary to assumption. First, by \(0'(n)\) denote function analoguous to \(F(n)\), except using \(0'\) and not \(A\). We can compute \(0'(n)\) given \(S(n)\), because \(n\)th machine, in a fixed reasonable enumeration, has at most \(n\) states, and \(S\) is increasing. For every \(n\) for which \(f(n)>S(n)\) we have \(f(n)>0'(n)\).

Now, there is a theorem, proof of which I don't understand fully, which says that the above is enough for the degree to be array nonrecursive, you can find the proof here. The idea is that if, to compute function \(g\leq_\text{wtt}0'\) we need at most \(h(n)\) oracle queries to \(0'\) for computable \(h\) (which exists by definition of wtt-reducibility), then we can "approximate" \(0'\) by using the fact that \(f(h(n+1))>0'(h(n))\) for infinitely many \(n\), and for these we can exceed \(g(n)\). Thanks to this, we reach a contradiction with choice of \(A\). So \(S\) eventually dominates \(f\) for every \(f\) which is \(F\)-computable.

Now suppose \(F\) was bounded by some computable function \(f\), so that \(f(n)>F(n)\) for all \(n\). If we know that \(a\) doesn't take value \(n\) for first \(f(n)\), then surely it doesn't for first \(F(n)\), so, by definition of \(F\), it means that \(a\) will never take value \(n\), so \(n\not\in A\). So we can decide membership in \(A\) by computing first \(f(n)\) values of \(a\) and looking for \(n\) there. This however stands in contradiction with choice of \(A\) to be nonrecursive. So indeed \(F\) isn't bounded by any computable function.

Another case which is of interest is a function which dominates all recursive functions, but no recursive extension of it can bound \(S\). For this, choose any set \(A\) which is recursively enumerable, Turing-incomplete and has high degree (i.e. \(A'\equiv_T 0' '\)) (such degree exists, again, priority methods). By Martin's domination theorem, there exists an \(A\)-computable function \(F\) which dominates all computable functions. Suppose that some recursive extension \(f\) of this function bounds \(S\). Then we know that if \(n\)-state Turing machine works for more than \(f(n)\) steps, then it cannot halt (by definition of \(S\)). So we can decide the halting problem, which is a contradiction, because we assumed \(A\) cannot decide \(0'\).

Fourth case, a function which isn't bounded by computable function and doesn't recursively bound \(S\), follows as a possibility from either of the above two.

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.