5
$\begingroup$

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?

$\endgroup$
  • $\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-Turkistany Dec 23 '18 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 '18 at 14:28
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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