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

<p>The bottom line is that for fixed <span class="math-container">$n$</span>, the resulting <span class="math-container">$n_0$</span> will be a constant.</p>

CC BY-SA 4.0
2018-12-23T14:05:12.390Z
2018-12-23T16:51:38.657Z
2018-12-23T16:51:38.657Z
Aryeh
<p>From calculus, we know that if someone has a continuous function <span class="math-container">$f$</span>, it is enough to know <span class="math-container">$f$</span>'s values on the rationals in order to know <span class="math-container">$f$</span> on the entire line. In some sense, a "countable amount of information" is sufficient to describe a continuous function completely.<br>
Is there a similar notion for computable functions (or Turing machines)? i.e.:<br>
Let <span class="math-container">$T : \{0,1\}^* \rightarrow \{0,1\}$</span> be a Turing machine and let <span class="math-container">$\{0,1\}^{n_0}$</span> be the set of all binary string of lengh <span class="math-container">$n_0$</span>. Describing <span class="math-container">$T$</span> on <span class="math-container">$\{0,1\}^{n_0}$</span> trivially requires <span class="math-container">$2^{n_0}$</span> values. Can we impose conditions on <span class="math-container">$T$</span>, which will reduce <span class="math-container">$2^{n_0}$</span> (like continuity in the continuous domain)? Can we hope for non-trivial such conditions? </p>

CC BY-SA 4.0
2018-12-23T14:05:04.540Z
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
CC BY-SA 4.0
2018-12-23T14:28:17.007Z
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 http://jeffe.cs.illinois.edu/teaching/497/13-circuits.pdf
Avi Tal
<cc.complexity-theory><computability><turing-machines><boolean-functions><it.information-theory>
Minimal information needed for determine some function
ll ed
# Minimal information needed for determine some function

(Asked by: username_0 on 2018-12-23)

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?

**Tags:** cc.complexity-theory, computability, turing-machines, boolean-functions, it.information-theory
> **Comments:**
> **username_1**: If we use circuit complexity as a measure of information then Shannon showed that most boolean n-ary functions have exponential circuit complexity.  
> **username_2**: 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 http://jeffe.cs.illinois.edu/teaching/497/13-circuits.pdf  

---

## 1 answers

### Answer by username_3 on 2018-12-23. Score: 2

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.


---

