# Minimal information needed for determine some function

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?

• If we use circuit complexity as a measure of information then Shannon showed that most boolean n-ary functions have exponential circuit complexity. – Mohammad Al-Turkistany Dec 23 '18 at 14:05
• 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 – Avi Tal Dec 23 '18 at 14:28

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.