6

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.

Arthur MILCHIOR
  • 1,561
  • 10
  • 19
  • 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 Jun 20 '14 at 12:40
  • Corrected, I should have used the word "execution", and it's now explained. – Arthur MILCHIOR Jun 20 '14 at 12:48
  • 2
    I think it is trivial that every recursively enumerable set is in S. Why do you have any difficulty proving it? – domotorp Jun 20 '14 at 17:39
  • @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 Jun 20 '14 at 17:49
  • 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. – Ludovic Patey Jun 22 '14 at 21:31
  • @Turingoid: Indeed. – domotorp Jun 23 '14 at 03:12
  • 1
    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 Jun 23 '14 at 03:17
  • (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 Jul 17 '14 at 14:55
  • (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 Jul 17 '14 at 20:11

1 Answers1

2

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.

Community
  • 1
David G
  • 532
  • 5
  • 13