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$
$\endgroup$
2
-
$\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$– Mohammad Al-TurkistanyDec 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 TalDec 23, 2018 at 14:28
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
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.
