From calculus, we know that if someone has a continuous function $f$, it is enough to know $f$'s values on the rationals in order to know $f$ on the entire line. In some sense, a "countable amount of information" is sufficient to describe a continuous function completely.
Is there a similar notion for computable functions (or Turing machines)? i.e.:
Let $T : \{0,1\}^* \rightarrow \{0,1\}$ be a Turing machine and let $\{0,1\}^{n_0}$ be the set of all binary string of lengh $n_0$. Describing $T$ on $\{0,1\}^{n_0}$ trivially requires $2^{n_0}$ values. Can we impose conditions on $T$, which will reduce $2^{n_0}$ (like continuity in the continuous domain)? Can we hope for non-trivial such conditions?

  • $\begingroup$ If we use circuit complexity as a measure of information then Shannon showed that most boolean n-ary functions have exponential circuit complexity. $\endgroup$ Dec 23, 2018 at 14:05
  • $\begingroup$ There is a constant c such that every n-ary boolean function has circuit complexity at most 2^n/(c*n). Theorem 5, p.3 in jeffe.cs.illinois.edu/teaching/497/13-circuits.pdf $\endgroup$
    – Avi Tal
    Dec 23, 2018 at 14:28

1 Answer 1


A natural condition is to bound the number of states of $T$ --- say, at most $n$. The set $\mathcal{C}_n$ of all TM's on at most $n$ states is finite --- in fact, of cardinality $2^{O(n)}$. It is well-known that finite classes have a finite teaching dimension, http://www.cs.columbia.edu/~djhsu/coms6998-f17/student-work/scribe-notes/teaching_dimension.pdf of size $d_n=O(|\mathcal{C}_n|)$ --- meaning that for each $M\in\mathcal{C}_n$, some set of at most $d_n$ labeled strings uniquely identifies $M$. Taking the union of these "teaching sets" over all $M\in\mathcal{C}_n$ gives you a finite set $S\subset\Sigma^*$, which belongs to $\Sigma^{\le n_0}$ for some $n_0$. Now you required that all of the examples be of the same length, but other than that, this satisfies your criteria.

The bottom line is that for fixed $n$, the resulting $n_0$ will be a constant.


Your Answer

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

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