<p>Claim: $S\subseteq NEXP$.</p>

<p>To prove it, take $L\in S$. It follows that there exists a machine $K$ s.t. $L=S(K)$. I imagine $K$ to be a Turing machine because I am more familiar with them. Now $n\in L$ iff there exists some computation of $K$ on empty input of length $n$. So we can verify whether $n\in L$ by non-deterministically guessing first $n$ steps of $K$ on empty input and verifying whether $K$ halts after this $n$ steps. $\square$</p>

<p>Considering that the problem of verifying whether a non-deterministic TM makes at most $n$ steps on empty inpuit on some computation is NEXP-complete (<a href="https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems/3298#3298">NEXP-complete problems</a>), I would guess that $S$ contains arbitrary hard NEXP problems.</p>

CC BY-SA 3.0
2014-07-18T06:34:07.730Z
thank you a lot, it know seems obvious, and it,s really helpful !
Arthur MILCHIOR
CC BY-SA 3.0
2014-07-16T16:14:42.383Z
2014-07-16T18:54:55.883Z
2017-04-13T12:32:28.053Z
David G
<p>Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever.</p>

<p>The Machine have no input. A configuration of a Minsky Machine is the triplet (a state, value of counter 1, value of counter 2). (There is a similar notion of configuration for every machine).  The initial configuration is (state0, 0, 0)</p>

<p>Its computation is a list of successive configuration, that halts in an halting state. The lenght of the computation $s$ is the size of the list, and is denoted by $|s|$.</p>

<p>Let $H(K)$ be the set of computation of this machine that halts.  Then let $S(K)$ be the set of the length of those computation, that is $S(K)=\{|s|\mid s\in H(K)\}$.  It is similar to the "spectral theory" notion <a href="http://en.wikipedia.org/wiki/Spectrum_of_a_theory" rel="nofollow">http://en.wikipedia.org/wiki/Spectrum_of_a_theory</a> . That is, we forgot everything from a set apart a number.</p>

<p>Finally, let $\mathcal S$ be the set of $S(K)$ for every machine $K$. $\mathcal S=\{S(K)\mid K\}$.
Is there anything we can say about $\mathcal S$ ? Trivially, I can say that it contains only computable sets. It contains every finite set; but between those information, I'm lost. </p>

<p>In an intuitive sense, I'm interested by finding the most complex set of $\mathcal S$.</p>

<p>I should  emphasize that this problem is very different from the $\#P$ class, since: 1) the machine doesn't have any input. 2) I'm not interested in the number of halting path.</p>

CC BY-SA 3.0
2014-06-20T12:40:24.437Z
What is formally a "simulation"? Is $H(K)$ the set of initial counter values for which $K$ halts (in this case do you consider the two initial values of the counters, or only the value of one counter and the second is equal to zero) ? Or is the machine $K$ started with both counters equal to zero (similar to a TM on a blank tape).
Marzio De Biasi
CC BY-SA 3.0
2014-06-20T12:48:41.303Z
Corrected, I should have used the word "execution", and it's now explained.
Arthur MILCHIOR
CC BY-SA 3.0
2014-06-20T17:39:47.920Z
I think it is trivial that every recursively enumerable set is in S. Why do you have any difficulty proving it?
domotorp
CC BY-SA 3.0
2014-06-20T17:49:37.137Z
@domotorp Because I didn't even try to prove it; I would be surprised that every recursively enumerable set are in $\mathcal S$. Even if I don't have prove that it is false either. If it's trivial and you can explain me why, then that would answer my question, and it would be good news for me :)
Arthur MILCHIOR
CC BY-SA 3.0
2014-06-22T21:31:32.963Z
@domotorp It seems to me that, given a machine K and a number n, it is easy to decide whether n is in S(K) or not: just check every computation of length n. Therefore S(K) must be decidable and S must contain only decidable sets. Or maybe I misunderstood the problem.
Ludovic Patey
CC BY-SA 3.0
2014-06-23T03:12:36.193Z
@Turingoid: Indeed.
domotorp
CC BY-SA 3.0
2014-06-23T03:17:19.570Z
Here is a proof sketch in the direction of what domotorp suggested. Let $M$ be a total TM such that $T_M(x) = M(x) + |M(x)| + |x|$. Then the image of $M$ is contained in $\mathcal{S}$. Basically, construct a machine $K$ that, on empty input, branches nondeterministically to all finite strings $y$, computes $M(y)$, and then runs for exactly $M(y) - |T_M(y)| - |y|$ additional steps. (If there's no problem with this construction, then it follows from Turingoid's comment that the image of any such $M$ must be computable.)
Joshua Grochow
CC BY-SA 3.0
2014-07-17T14:55:46.553Z
(similar to MDBs comment) think this is not clearly defined as stated, the sentence starting "Let H(k)..."  has no verb and does not define a set of anything in words. maybe it is a set of initial starting conditions? shouldnt have to guess :(
vzn
CC BY-SA 3.0
2014-07-17T20:11:04.723Z
(post edit) the sentence "Let H(K) be the set of computation of this machine that halts" now has a verb but still does not define anything specifically. is it a set of "starting tapes"? ie the _language?_
vzn
<nondeterminism><counter-automata>
Halting time of non deterministic machine
Arthur MILCHIOR
# Halting time of non deterministic machine

(Asked by: username_0 on 2014-06-20)

Let $K$ be a non deterministic machine. I use Minsky Machine (2 counter automaton) for practical reason in my research, but it could be a turing machine, a register machine, whatever.

The Machine have no input. A configuration of a Minsky Machine is the triplet (a state, value of counter 1, value of counter 2). (There is a similar notion of configuration for every machine). The initial configuration is (state0, 0, 0)

Its computation is a list of successive configuration, that halts in an halting state. The lenght of the computation $s$ is the size of the list, and is denoted by $|s|$.

Let $H(K)$ be the set of computation of this machine that halts. Then let $S(K)$ be the set of the length of those computation, that is $S(K)=\{|s|\mid s\in H(K)\}$. It is similar to the "spectral theory" notion <http://en.wikipedia.org/wiki/Spectrum_of_a_theory> . That is, we forgot everything from a set apart a number.

Finally, let $\mathcal S$ be the set of $S(K)$ for every machine $K$. $\mathcal S=\{S(K)\mid K\}$.
Is there anything we can say about $\mathcal S$ ? Trivially, I can say that it contains only computable sets. It contains every finite set; but between those information, I'm lost.

In an intuitive sense, I'm interested by finding the most complex set of $\mathcal S$.

I should emphasize that this problem is very different from the $\#P$ class, since: 1) the machine doesn't have any input. 2) I'm not interested in the number of halting path.

**Tags:** nondeterminism, counter-automata
> **Comments:**
> **username_1**: What is formally a "simulation"? Is $H(K)$ the set of initial counter values for which $K$ halts (in this case do you consider the two initial values of the counters, or only the value of one counter and the second is equal to zero) ? Or is the machine $K$ started with both counters equal to zero (similar to a TM on a blank tape).  
> **username_0**: Corrected, I should have used the word "execution", and it's now explained.  
> **username_2**: I think it is trivial that every recursively enumerable set is in S. Why do you have any difficulty proving it?  
> **username_0**: @domotorp Because I didn't even try to prove it; I would be surprised that every recursively enumerable set are in $\mathcal S$. Even if I don't have prove that it is false either. If it's trivial and you can explain me why, then that would answer my question, and it would be good news for me :)  
> **username_3**: @domotorp It seems to me that, given a machine K and a number n, it is easy to decide whether n is in S(K) or not: just check every computation of length n. Therefore S(K) must be decidable and S must contain only decidable sets. Or maybe I misunderstood the problem.  
> **username_2**: @Turingoid: Indeed.  
> **username_4**: Here is a proof sketch in the direction of what domotorp suggested. Let $M$ be a total TM such that $T_M(x) = M(x) + |M(x)| + |x|$. Then the image of $M$ is contained in $\mathcal{S}$. Basically, construct a machine $K$ that, on empty input, branches nondeterministically to all finite strings $y$, computes $M(y)$, and then runs for exactly $M(y) - |T_M(y)| - |y|$ additional steps. (If there's no problem with this construction, then it follows from Turingoid's comment that the image of any such $M$ must be computable.)  
> **username_5**: (similar to MDBs comment) think this is not clearly defined as stated, the sentence starting "Let H(k)..."  has no verb and does not define a set of anything in words. maybe it is a set of initial starting conditions? shouldnt have to guess :(  
> **username_5**: (post edit) the sentence "Let H(K) be the set of computation of this machine that halts" now has a verb but still does not define anything specifically. is it a set of "starting tapes"? ie the _language?_  

---

## 1 answers

### Answer by username_6 on 2014-07-16. Score: 2 | Accepted answer

Claim: $S\subseteq NEXP$.

To prove it, take $L\in S$. It follows that there exists a machine $K$ s.t. $L=S(K)$. I imagine $K$ to be a Turing machine because I am more familiar with them. Now $n\in L$ iff there exists some computation of $K$ on empty input of length $n$. So we can verify whether $n\in L$ by non-deterministically guessing first $n$ steps of $K$ on empty input and verifying whether $K$ halts after this $n$ steps. $\square$

Considering that the problem of verifying whether a non-deterministic TM makes at most $n$ steps on empty inpuit on some computation is NEXP-complete ([NEXP-complete problems](https://cstheory.stackexchange.com/questions/3297/nexp-complete-problems/3298#3298)), I would guess that $S$ contains arbitrary hard NEXP problems.

> **Comments:**
> **username_0**: thank you a lot, it know seems obvious, and it,s really helpful !  

---

