<p>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. </p>

<ul>
<li><p><a href="http://basics.sjtu.edu.cn/~chen/papers/3hal-fel.pdf" rel="nofollow">A Parameterized Halting Problem</a> Yijia Chen and Jorg Flum</p>

<blockquote>
  <p>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.</p>
</blockquote></li>
</ul>

CC BY-SA 3.0
2014-07-04T03:40:52.583Z
2014-07-04T03:40:52.583Z
vzn
<p>Is the following <a href="http://en.wikipedia.org/wiki/Busy_beaver" rel="nofollow">Busy Beaver</a> variant known?</p>

<p>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:</p>

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

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

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

<blockquote>
  <p>Do nondeterministic jumping beavers perform better than deterministic jumping beavers? I.e. does $j'(n) &gt; j(n)$ hold? (for some values of $n$ or infinitely often)<br><br>
  What about the limit $\lim_{n \to \infty}j'(n)/j(n)$?</p>
</blockquote>

<p><br><em>Note</em>: 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 <em>seems</em> equivalent to the formulation above (indeed $J'$ <em>seems</em> to capture all the power of NP), it is easy to see that $j(n) = j'(n)$.</p>

CC BY-SA 3.0
2014-07-03T15:18:56.297Z
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
CC BY-SA 3.0
2014-07-03T16:00:19.623Z
@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").
Marzio De Biasi
CC BY-SA 3.0
2014-07-03T16:29:30.183Z
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 [chat]
vzn
<computability>
Jumping (Busy) Beaver variant
Marzio De Biasi
# Jumping (Busy) Beaver variant

(Asked by: username_0 on 2014-07-02)

Is the following [Busy Beaver](http://en.wikipedia.org/wiki/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)$.

**Tags:** computability
> **Comments:**
> **username_1**: 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....  
> **username_0**: @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").  
> **username_1**: 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 [chat]  

---

## 1 answers

### Answer by username_1 on 2014-07-04. Score: -2

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](http://basics.sjtu.edu.cn/~chen/papers/3hal-fel.pdf) 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.


---

