# How many Turing Machines are there that run in time $t$ or in space $s$ on inputs of length $k$?

I think half the battle in answering this question lies in formulating it precisely! A search engine doesn't turn up much, so I was wondering if this is a well-known or well-studied question.

My thoughts: I think the most straightforward way to formulate this question is as in my title: Given constants $t,s,k \in \mathbb{N}$, how many TMs are there that run in $t$ steps or fewer on all inputs of size $k$, and how many TMs are there that use $s$ tape squares or fewer on all inputs of size $k$? This seems like the most direct and simple way to ask the question, but we might want to restate it in a different way -- for example, given a function $p(k)$, how many TMs are there that run in time $p(k)$ on inputs of size $k$ for all $k$ (or how "dense" are these TMs)? This seems harder to me.

We should probably fix a tape alphabet (or a Godel numbering??). We could consider two TMs with different but isomorphic state diagrams to be the same or different, either way.

The immediate problem is that there are an infinite number: Take any TM that satisfies the criteria and add "dead states". I can think of two ways to deal with this. The first (which I don't like) is to add an additional parameter: how many TMs whose description has length $\leq L$ satisfy the criteria? The second (which I prefer) is to consider two TMs equivalent on inputs of size $\leq k$ if, for all such inputs, the TMs have exactly the same behavior (enter the same states and write/move on the tape identically). Then we would restrict to the minimal TM in each equivalence class, or just ask how many equivalence classes satisfy the criteria.

Edit: As pointed out by Vor in the comments, the problem with the second approach is that it's basically the same as a circuit at that point. So how about the first one? Or is there a nicer way to formalize this question?

Any references/literature, thoughts, or answers would be very interesting and appreciated!

• If you pick $\Sigma = \{0,1\}$, you have $2^{(2^k)}$ distinct boolean functions $\{0,1\}^k \rightarrow \{0,1\}$. So if k<=t you get at least $2^{(2^k)}$ distinct TMs ... and perhaps they're enough to stop counting other variations/parametrizations :-). – Vor Mar 5 '13 at 18:46
• @Vor, I see why there are that many boolean functions, but why do they all run in time $O(k)$ ... hmm, I guess because we just construct a different DFA for each one and make it the state diagram of our TM? OK, so to make the question interesting I should think about redefining or adding new constraints. – usul Mar 5 '13 at 19:04
• it might be easier to ask about languages instead of TMs and in that case this question actually relates to open questions of complexity class separations, in other words there probably ways to formulate this that is equivalent to asking P=?NP etc. another interesting idea might be to consider the velocity of TMs ie the ratio of $t(n)/s(n)$... also, this topic can be empirically studied somewhat for "small" languages... – vzn Jun 7 '14 at 16:07

Given $k$, consider the set of $\mathcal{M}_k = \{ M_i \mid i \in \mathbb{N} \}$ with $M_i$ defined by

if |x| = k
accept
else
simulate TM i on x


The set $\mathcal{M}_k$ is a subset of the Turing machines you want to count for all $s,t$. Since it is infinite, the set you want to count is infinite, too.

As far as I can tell, this result is stable against all restrictions you impose as long as you don't restrict the set of all feasible Turing machines to be finite.

• What about adding the following equivalence: two machines are equivalent "mod k" if they behave in the same way on inputs of size k (possibly modulo bisimulation). Now it makes sense to ask for the size of the -equivalence classes- mod k. – cody May 7 '13 at 14:56
• @cody Those classes are all infinite, too. Change in my construction the else branch to count to i on the tape; reject and you get an infinite set of acceptors for $\Sigma^k$; the same construction basically works for all (decidable) languages. – Raphael May 7 '13 at 17:07
• I'm sorry, I'm confused, it seems to me everything in your 'else' branch is irrelevant "mod k", as it specifies behavior in the case where |x| is -not- k. – cody May 7 '13 at 20:10
• @cody: Yes, and no. All of the described machines accept the same subset of $\Sigma^k$, so they are equivalent modulo $k$ (if I understand correctly what you wanted). However, there are infinitely many such else branches, so the equivalence class contains infinitely many elements. And, so far my claim, that is true for all equivalence classes, as a similar construction always works. (Essentially, the statement is: every language is accepted by infinitely many TMs. Or even: for every TM, there are infinitely many output-equivalent others.) – Raphael May 7 '13 at 23:28
• so my proposal is to identify all TMs that behave differently outside of $\Sigma^k$. In that case it's still clear that there are infinitely many classes of machines that accept the same language in $\Sigma^k$. However it's not clear that there are infinitely many of those that work in bounded space and time. – cody May 8 '13 at 22:17

Your question is closely related to the busy beaver problem. It asks for the maximum number of symbols an $n$-state Turing machine with 2 output symbols that always halts writes before halting. The function of $n$ defined this way is not computable.

• sure, there is some connection, but I am mainly interested in the question for some computable function $t(k)$ ... I don't see how to use BB in that case. – usul Mar 7 '13 at 16:07

you ask some questions and formulate some interesting ideas that generally nearly relate to open questions about complexity class separations. for example P=?NP can be reformulated as asking about "how many" NP(-hard) languages can be executed in P time. however there are probably not too many theoretical (or otherwise) results in this area. there are some theoretical papers that do give bounds on both time/space complexity of SAT that would touch on your question. however maybe the closest research to this is empirical analysis of TMs, which is hinted at in the other answer by vonbrand eg with busy beaver research.

there is similar but relatively rare research that looks at empirically-generated TMs with "clocks" eg P-time etc. here is one such ref from 2013. it enumerates TMs with P-time clocks and looks at/for fractal patterns in the resulting/generated "time-space diagrams" (also called "computational tableaus"). another approach is to look at "small finite" samples eg limiting $t, s, k$ (and also other parameters like enumerated TM states).