Halting time of non deterministic machine 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.
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), I would guess that $S$ contains arbitrary hard NEXP problems.