<p>Only an extended comment with a trivial example; you can pick the one-element language:</p>

<p>$$L_k = \{ M \mid  \sigma(M) = \Sigma(k) \}$$</p>

<p>i.e. $L_k$ contains the first (in lexicographical order) <a href="http://en.wikipedia.org/wiki/Busy_beaver">busy beaver</a> Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).</p>

<p>For every $k$ the language $L_k$ is regular ... but we have no idea on how to  build the small DFA that recognizes it (though it has only $\leq 2*k(\log k+2)$ states) :-)</p>

CC BY-SA 3.0
2014-04-15T23:08:56.797Z
While I agree it works, I was looking for existence showing techniques for explicitly given language L.
R B
CC BY-SA 3.0
2014-05-01T11:26:12.250Z
What is an "explicitly given language"?
Jeffε
CC BY-SA 3.0
2014-04-15T22:36:19.513Z
2014-04-15T22:36:19.513Z
Marzio De Biasi
<p>Another solution is to use <em>Higman's lemma</em>: </p>

<blockquote>
  <p>A language closed under subwords is  regular. </p>
  
  <p>With $u$ a subword of $v$ if we can obtain $u$ by removing some letter in $v$.</p>
</blockquote>

<p>So take any language L, its subword closure is regular but is not at all constructible since L is arbitrary. </p>

CC BY-SA 3.0
2016-10-03T04:40:42.983Z
2016-10-03T04:40:42.983Z
C.P.
<p>The language  $ \mathtt{MOD_p} = \{a^{ip} \mid i \geq 0\} $ (for some prime number $p$) can be recognized by a $ O(\log p) $-state bounded-error quantum finite automata (QFAs) but the proof is non-constructive. </p>

<p>The best known constructively obtained number of states is $ O(\log^{2+o(1)}p) $ for bounded-error QFAs recognizing $ \mathtt{MOD_p} $.</p>

<p>REF: Section 4.2 of <a href="http://arxiv.org/pdf/1507.01988v1.pdf" rel="nofollow">(Ambainis and Yakaryilmaz, 2015)</a>.</p>

CC BY-SA 3.0
2016-09-22T07:23:14.850Z
2016-09-22T07:23:14.850Z
Abuzer Yakaryilmaz
<p>After reading a <a href="https://cstheory.stackexchange.com/questions/12162/are-there-non-constructive-algorithm-existence-proofs">related question</a>, about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of &quot;small&quot; (say, state-wise) computation machines without actually building it.</p>
<p>Formally:</p>
<p>suppose we are given some language <span class="math-container">$L\subseteq \Sigma^*$</span> and fix some computation model (NFAs / turing machine/ etc.).</p>
<p>Are there any non-constructive existence results showing a <span class="math-container">$n$</span>-state machine for <span class="math-container">$L$</span> exists, but without the ability of finding (in <span class="math-container">$poly(n,|\Sigma|)$</span> time) it?</p>
<p>For example, is there any regular language <span class="math-container">$L$</span> for which we can show <span class="math-container">$nsc(L)\leq n$</span> but we don't know how to build a <span class="math-container">$n$</span>-state automaton for?</p>
<p>(<span class="math-container">$nsc(L)$</span> is the non-deterministic state complexity of <span class="math-container">$L$</span>, i.e. the number of states in the minimal NFA that accepts <span class="math-container">$L$</span>).</p>
<hr />
<p>EDIT: after some discussion with Marzio (thanks !) I think I can better formulate the question as follows:</p>
<blockquote>
<p>Is there a language <span class="math-container">$L$</span> and a computation model for which the following holds:</p>
<ol>
<li><p>We know how to build a machine that compute <span class="math-container">$L$</span> that has <span class="math-container">$m$</span> states.</p>
</li>
<li><p>We have a proof that <span class="math-container">$n$</span>-states machine for <span class="math-container">$L$</span>  exists (where <span class="math-container">$n &lt;&lt; m$</span>), but either we can't find it at all or it'd take exponential time to compute it.</p>
</li>
</ol>
</blockquote>

CC BY-SA 3.0
2014-04-16T02:32:21.210Z
what is nsc(L)? the question seems related to compression/Kolmogorov complexity which asks to find small(est) machines to represent strings...
vzn
CC BY-SA 3.0
2014-04-16T03:16:05.327Z
nsc(L) is the non deterministic state complexity of L (the number of states in the smallest NFA that accepts L).
R B
CC BY-SA 3.0
2014-04-16T04:11:12.657Z
another idea/angle, maybe there are some "small" circuit classes (another computation model) for which it is proven they can calculate certain functions but the actual construction is tricky? SJ [recently mentioned](http://cstheory.stackexchange.com/questions/21995/kolmogorovs-conjecture-that-p-has-linear-size-circuits) Barrington thm that width 5 branching programs can compute majority...?
vzn
CC BY-SA 3.0
2014-04-16T05:02:25.133Z
@vzn The proof of Barrington's theorem give an easy procedure to convert formulas into branching programs.
Sasho Nikolov
CC BY-SA 3.0
2014-04-16T10:24:41.987Z
@R B: A classical example is a probabilistic construction by [Valiant](http://www.sciencedirect.com/science/article/pii/0196677484900166) (1984) of a small monotone formula for Majority. Similar are the construction of a deterministic circuit from a randomized one by Adleman (1978) as well as constructions based on the Isolation Lemma by Mulmuley-Vazirani-Vazirani (1987), and others. @vzn: Barrington's construction is indeed elementary - tricky (very!) is his "non-sequential" *view* at branching programs.
Stasys
CC BY-SA 3.0
2014-04-16T15:27:55.967Z
the defn of "nonconstructive" can be tricky, but apparently nobody has actually _built/exhibited_ width 5 branching programs for majority & (re SJs point) their behavior/function is not better or more directly understood/explained except via the Barrington thm construction. (for example a better understanding might lead to an inductive/recursive statement/formulation of their construction.) to me that is verging on "nonconstructive"...
vzn
CC BY-SA 3.0
2014-04-17T00:34:39.133Z
A clarification: what do you mean with "exhaustive search of a Turing machine"? Human search?  For example, in my answer, an exhaustive and *automated* search for an $L_k$ decider could be done only if we know the value of $\Sigma(k)$ or if we know a larger busy beaver or if we have an oracle for the halting problem or ....)
Marzio De Biasi
CC BY-SA 3.0
2014-04-17T00:36:03.213Z
@MarzioDeBiasi - please let me know if this makes sense:

In exponential time we can enumerate all of the $k$ states TM and find the busy beaver's machine. After which (now that we have the encoding) we can simply create a DFA for it, right?

i.e. the reason we have no idea how to build the DFA at the moment is that we don't actually know the encoding of the TM of $L_k$.
R B
CC BY-SA 3.0
2014-04-17T06:52:41.307Z
@RB: no, we cannot find the TM for $L_k$ with an automated procedure because the propert "M is a busy beaver of size k is undecidable"; we need to use an oracle for HALT (or know a larger busy beaver). In general deciding if a Turing machine computes a nontrivial language is undecidable, so if exhaustive search means automated exhaustive search you must put some restrictions on the model.
Marzio De Biasi
CC BY-SA 3.0
2014-04-17T14:04:00.233Z
@MarzioDeBiasi - then it's even further than what I meant to ask for.

I'm looking for a language $L$ for which we know how to build a machine for. Say with m states.

Now I'm asking if there's a way of showing a smaller, n-state machine exists for the same language, but without being able to find it.

Your answer gives a case where "n-state machine exist, but we don't know how to build any machine for it".
I'm looking for a "n-state machine exist, but we can only build a m >> n states machine".

Does it make sense? How'd you formulate it in the question?
Thanks !
R B
CC BY-SA 3.0
2014-04-17T15:49:59.313Z
@RB: ok, you can find more interesting examples from resource bounded Kolmogorov complexity (in particular the time-bounded complexity). For example, given a string $x$, what is the smallest machine that runs in time $O(2^n)$ that prints $x$? In this case we can easily build a TM that prints $x$, but finding the smallest one requires to scan all the TMs $|M|<|x|$ (the time bound makes it computable). When I have more time, I'll expand my answer.
Marzio De Biasi
CC BY-SA 3.0
2014-04-17T23:41:21.253Z
@MarzioDeBiasi - That sounds good, but can we actually show an existence of a much smaller machine than the one we know how to build?

Assume the trivial machine takes $m$ states, can we show that only $m$-states are needed for it?

This is what I was aiming for - showing existence of a small machine where we know how to build a large one.
R B
CC BY-SA 3.0
2014-04-17T23:55:51.653Z
@RB: most strings are incompressible (i.e. you need a TM larger than $|x|$ to print $x$) ... but at least some of them are highly compressible :-); take for example the binary representation of a number for which the prime factorization represenation is smaller: e.g. $n = 4^{5*6}*7^{8*9}$
Marzio De Biasi
CC BY-SA 3.0
2014-04-18T04:38:21.730Z
@Stasys I think the examples you mentioned make for good answers. I was also thinking of Ajtai's probabilistic construction of depth 3 circuits for approximate majority. But then I realized Viola has given a uniform construction.
Sasho Nikolov
CC BY-SA 3.0
2014-05-03T15:54:37.157Z
Regarding the revised question, what does "exponential time" mean?  For instance, what if the language is finite?
András Salamon
CC BY-SA 3.0
2014-05-03T16:53:42.240Z
@AndrásSalamon - suppose that the language $L$ is finite, and we have a $m$-states NFA for it, but a $n$-states NFA exists.
Then in time $2^{O(m)}$ we can find the automaton in brute force manner (enumerate all $n$ state NFAs and check if it's equivalent to our $m$ states automaton), which is not what I'm after.
R B
<cc.complexity-theory><automata-theory><turing-machines>
Are there non-constructive proofs of existence of "small" Turing machines / NFAs?
R B
# Are there non-constructive proofs of existence of "small" Turing machines / NFAs?

(Asked by: username_0 on 2014-04-15)

After reading a [related question](https://cstheory.stackexchange.com/questions/12162/are-there-non-constructive-algorithm-existence-proofs), about non-constructive existence proofs of algorithms, I was wondering if there are methods of showing existence of "small" (say, state-wise) computation machines without actually building it.

Formally:

suppose we are given some language $L\subseteq \Sigma^\*$ and fix some computation model (NFAs / turing machine/ etc.).

Are there any non-constructive existence results showing a $n$-state machine for $L$ exists, but without the ability of finding (in $poly(n,|\Sigma|)$ time) it?

For example, is there any regular language $L$ for which we can show $nsc(L)\leq n$ but we don't know how to build a $n$-state automaton for?

($nsc(L)$ is the non-deterministic state complexity of $L$, i.e. the number of states in the minimal NFA that accepts $L$).

---

EDIT: after some discussion with Marzio (thanks !) I think I can better formulate the question as follows:

> Is there a language $L$ and a computation model for which the following holds:
>
> 1. We know how to build a machine that compute $L$ that has $m$ states.
> 2. We have a proof that $n$-states machine for $L$ exists (where $n << m$), but either we can't find it at all or it'd take exponential time to compute it.

**Tags:** cc.complexity-theory, automata-theory, turing-machines
> **Comments:**
> **username_1**: what is nsc(L)? the question seems related to compression/Kolmogorov complexity which asks to find small(est) machines to represent strings...  
> **username_0**: nsc(L) is the non deterministic state complexity of L (the number of states in the smallest NFA that accepts L).  
> **username_1**: another idea/angle, maybe there are some "small" circuit classes (another computation model) for which it is proven they can calculate certain functions but the actual construction is tricky? SJ [recently mentioned](http://cstheory.stackexchange.com/questions/21995/kolmogorovs-conjecture-that-p-has-linear-size-circuits) Barrington thm that width 5 branching programs can compute majority...?  
> **username_2**: @vzn The proof of Barrington's theorem give an easy procedure to convert formulas into branching programs.  
> **username_3**: @R B: A classical example is a probabilistic construction by [Valiant](http://www.sciencedirect.com/science/article/pii/0196677484900166) (1984) of a small monotone formula for Majority. Similar are the construction of a deterministic circuit from a randomized one by Adleman (1978) as well as constructions based on the Isolation Lemma by Mulmuley-Vazirani-Vazirani (1987), and others. @vzn: Barrington's construction is indeed elementary - tricky (very!) is his "non-sequential" *view* at branching programs.  
> **username_1**: the defn of "nonconstructive" can be tricky, but apparently nobody has actually _built/exhibited_ width 5 branching programs for majority & (re SJs point) their behavior/function is not better or more directly understood/explained except via the Barrington thm construction. (for example a better understanding might lead to an inductive/recursive statement/formulation of their construction.) to me that is verging on "nonconstructive"...  
> **username_4**: A clarification: what do you mean with "exhaustive search of a Turing machine"? Human search?  For example, in my answer, an exhaustive and *automated* search for an $L_k$ decider could be done only if we know the value of $\Sigma(k)$ or if we know a larger busy beaver or if we have an oracle for the halting problem or ....)  
> **username_0**: @MarzioDeBiasi - please let me know if this makes sense:  In exponential time we can enumerate all of the $k$ states TM and find the busy beaver's machine. After which (now that we have the encoding) we can simply create a DFA for it, right?  i.e. the reason we have no idea how to build the DFA at the moment is that we don't actually know the encoding of the TM of $L_k$.  
> **username_4**: @RB: no, we cannot find the TM for $L_k$ with an automated procedure because the propert "M is a busy beaver of size k is undecidable"; we need to use an oracle for HALT (or know a larger busy beaver). In general deciding if a Turing machine computes a nontrivial language is undecidable, so if exhaustive search means automated exhaustive search you must put some restrictions on the model.  
> **username_0**: @MarzioDeBiasi - then it's even further than what I meant to ask for.  I'm looking for a language $L$ for which we know how to build a machine for. Say with m states.  Now I'm asking if there's a way of showing a smaller, n-state machine exists for the same language, but without being able to find it.  Your answer gives a case where "n-state machine exist, but we don't know how to build any machine for it". I'm looking for a "n-state machine exist, but we can only build a m >> n states machine".  Does it make sense? How'd you formulate it in the question? Thanks !  
> **username_4**: @RB: ok, you can find more interesting examples from resource bounded Kolmogorov complexity (in particular the time-bounded complexity). For example, given a string $x$, what is the smallest machine that runs in time $O(2^n)$ that prints $x$? In this case we can easily build a TM that prints $x$, but finding the smallest one requires to scan all the TMs $|M|<|x|$ (the time bound makes it computable). When I have more time, I'll expand my answer.  
> **username_0**: @MarzioDeBiasi - That sounds good, but can we actually show an existence of a much smaller machine than the one we know how to build?  Assume the trivial machine takes $m$ states, can we show that only $m$-states are needed for it?  This is what I was aiming for - showing existence of a small machine where we know how to build a large one.  
> **username_4**: @RB: most strings are incompressible (i.e. you need a TM larger than $|x|$ to print $x$) ... but at least some of them are highly compressible :-); take for example the binary representation of a number for which the prime factorization represenation is smaller: e.g. $n = 4^{5*6}*7^{8*9}$  
> **username_2**: @Stasys I think the examples you mentioned make for good answers. I was also thinking of Ajtai's probabilistic construction of depth 3 circuits for approximate majority. But then I realized Viola has given a uniform construction.  
> **username_5**: Regarding the revised question, what does "exponential time" mean?  For instance, what if the language is finite?  
> **username_0**: @AndrásSalamon - suppose that the language $L$ is finite, and we have a $m$-states NFA for it, but a $n$-states NFA exists. Then in time $2^{O(m)}$ we can find the automaton in brute force manner (enumerate all $n$ state NFAs and check if it's equivalent to our $m$ states automaton), which is not what I'm after.  

---

## 3 answers

### Answer by username_4 on 2014-04-15. Score: 8

Only an extended comment with a trivial example; you can pick the one-element language:

$$L\_k = \{ M \mid \sigma(M) = \Sigma(k) \}$$

i.e. $L\_k$ contains the first (in lexicographical order) [busy beaver](http://en.wikipedia.org/wiki/Busy_beaver) Turing machine of size $k$ (the Turing machine of size $k$ that attains the largest number of 1s on its tape after halting).

For every $k$ the language $L\_k$ is regular ... but we have no idea on how to build the small DFA that recognizes it (though it has only $\leq 2\*k(\log k+2)$ states) :-)

> **Comments:**
> **username_0**: While I agree it works, I was looking for existence showing techniques for explicitly given language L.  
> **username_6**: What is an "explicitly given language"?  

---

### Answer by username_7 on 2016-10-03. Score: 3

Another solution is to use *Higman's lemma*:

> A language closed under subwords is regular.
>
> With $u$ a subword of $v$ if we can obtain $u$ by removing some letter in $v$.

So take any language L, its subword closure is regular but is not at all constructible since L is arbitrary.


---

### Answer by username_8 on 2016-09-22. Score: 3

The language $ \mathtt{MOD\_p} = \{a^{ip} \mid i \geq 0\} $ (for some prime number $p$) can be recognized by a $ O(\log p) $-state bounded-error quantum finite automata (QFAs) but the proof is non-constructive.

The best known constructively obtained number of states is $ O(\log^{2+o(1)}p) $ for bounded-error QFAs recognizing $ \mathtt{MOD\_p} $.

REF: Section 4.2 of [(Ambainis and Yakaryilmaz, 2015)](http://arxiv.org/pdf/1507.01988v1.pdf).


---

