6
$\begingroup$

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.

Improve this question
$\endgroup$
9
  • $\begingroup$ 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). $\endgroup$
    – Marzio De Biasi
    Commented Jun 20, 2014 at 12:40
  • $\begingroup$ Corrected, I should have used the word "execution", and it's now explained. $\endgroup$
    – Arthur MILCHIOR
    Commented Jun 20, 2014 at 12:48
  • 2
    $\begingroup$ I think it is trivial that every recursively enumerable set is in S. Why do you have any difficulty proving it? $\endgroup$
    – domotorp
    Commented Jun 20, 2014 at 17:39
  • 3
    $\begingroup$ @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. $\endgroup$
    – Ludovic Patey
    Commented Jun 22, 2014 at 21:31
  • 1
    $\begingroup$ 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.) $\endgroup$
    – Joshua Grochow
    Commented Jun 23, 2014 at 3:17

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$
1
  • $\begingroup$ thank you a lot, it know seems obvious, and it,s really helpful ! $\endgroup$
    – Arthur MILCHIOR
    Commented Jul 18, 2014 at 6:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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