# Jumping (Busy) Beaver variant

Is the following Busy Beaver variant known?

A Universal Turing machine $J$, feeded with a description of a deterministic Turing machine $M_i$, starts simulating $M_i$ on inputs $x_j = 1,2,3,...$ for $|x_j|^i$ steps until $M_i(x_j)$ accepts; then $J$ outputs $x_j$ (if $M_i$ doesn't halt in $|x_j|^i$ steps $J$ continues with the next $x_j$). In other words:

$$J(M_i) = min\{ x \mid M_i(x) \text{ halts and accept in less than } |x|^i \text{ steps}\}$$

Fancifully, $J(M_i)$ - when defined - represents how high the polynomial-time Turing machine $M_i$ can "jump". So, for every $n$, we can define the Jumping Beaver as the Turing machine $M$ of size $n$ that achieve the highest jump $j(n) = max \{ J(M) \mid |M| = n\}$ .

But in a similar way we can define $J'$ that "measures" the jumps of a nondeterministic Turing machine $N_i$ ($J'$ simulates all branches of $N_i$ on input $x$ for at most $|x|^i$ steps).

Do nondeterministic jumping beavers perform better than deterministic jumping beavers? I.e. does $j'(n) > j(n)$ hold? (for some values of $n$ or infinitely often)

What about the limit $\lim_{n \to \infty}j'(n)/j(n)$?

Note: the enumeration of the deterministic Turing machines $M_i$ is different from the enumeration of the nondeterministic $N_i$ (due to the nondeterministic transitions), so, to make $J$ and $J'$ directly comparable, we can follow this alternative approach: $J$ simulates $M_i$ on input $x_j \# 0^{|x_j|}$; $J'$ can take as input a deterministic Turing machine $M_i$, too but simulates it on inputs $x_j \# y$ for all $y \in \{0,1\}^{|x_j|}$ and stops its search if at least one computation accepts. In this setting that seems equivalent to the formulation above (indeed $J'$ seems to capture all the power of NP), it is easy to see that $j(n) = j'(n)$.

• finding this formulation hard to parse. (a) $J(M_i)$ is presumably undecidable. it doesnt seem to limit the total number of inputs tested. (b) PTime machines are those running in time $O(n^k)$, $k$ constant which can hide a multiplicative constant which this formulation doesnt seem to take into account. (c) ofc there is a rough sense in which all undecidable problems are equivalently hard/interchangeable....
– vzn
Jul 3 '14 at 15:18
• @vzn: a) Yes, $J$ is undecidable; b) $M_i$ on input $x$ is simulated by $J$ for $|x|^i$ steps ($i$ does not depend on the input), so every $M_i$ implicitly behaves like a PTIME machine and the union of all the languages recognized by the $M_i$s is equal to $P$; c) here I would like to know if deterministic and nondeterministic polynomial-time deciders have different "power" when the "power" is measured by the first input they recognize (a "high jump"). Jul 3 '14 at 16:00
• ok. still not following exactly & feel formulation could be reworked substantially for clarity. think there is prob a conceptually much simpler/more natural way to attack BB from the pov of allowing nondeterminism, eg, taking the max # of steps of any accepting path of the nondeterministic machines as representative for that machine/input. (agreed the extension in general is interesting/ worthwhile.) more ideas in Theoretical Computer Science Chat
– vzn
Jul 3 '14 at 16:29