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)$.

  • $\begingroup$ 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.... $\endgroup$
    – vzn
    Jul 3 '14 at 15:18
  • $\begingroup$ @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"). $\endgroup$ Jul 3 '14 at 16:00
  • $\begingroup$ 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 $\endgroup$
    – vzn
    Jul 3 '14 at 16:29

the halting problem does not seem to be studied much for nondeterministic TMs (there is no single obvious way to extend the halting problem to NTMs) and most problems associated with undecidability seem to be defined in terms of non-NTMs (ie DTMs). however here is one generalization that could be related to your question.

  • A Parameterized Halting Problem Yijia Chen and Jorg Flum

    The parameterized problem p-Halt takes as input a nondeterministic Turing machine M and a natural number n, the size of M being the parameter. It asks whether every accepting run of M on empty input tape takes more than n steps. This problem is in the class XPuni, the class “uniform XP,” if there is an algorithm deciding it, which for fixed machine M runs in time polynomial in n. It turns out that various open problems of different areas of theoretical computer science are related or even equivalent to p-Halt ∈ XPuni. Thus this statement forms a bridge which allows to derive equivalences between statements of differ- ent areas (proof theory, complexity theory, descriptive complexity, . . . ) which at first glance seem to be unrelated. As our presentation shows, various of these equivalences may be obtained by the same method.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.