Existem provas não construtivas da existência de “pequenas” máquinas de Turing / NFAs?

Depois de ler uma pergunta relacionada , sobre provas não-construtivas de algoritmos, fiquei pensando se existem métodos para mostrar a existência de máquinas de computação "pequenas" (digamos, em termos de estado) sem realmente construí-la.

Formalmente:

suponha que recebamos alguma linguagem e conserte algum modelo de computação (NFAs / turing machine / etc.).$L\subseteq \Sigma^*$

Existem quaisquer resultados de existência não-construtivas que mostram um máquina -state para G existe, mas sem a capacidade de encontrar (em p o l y ( n , | Σ | ) tempo) é?$n$$L$$poly(n,|\Sigma|)$

Por exemplo, existe alguma linguagem regular para a qual podemos mostrar n s c ( L ) ≤ n, mas não sabemos como construir um autômato n- state?$L$$nsc(L)\leq n$$n$

( é a complexidade não determinística do estado de L , ou seja, o número de estados no NFA mínimo que aceita L ).$nsc(L)$$L$$L$

Edição: depois de alguma discussão com Marzio (obrigado!) Acho que posso formular melhor a pergunta da seguinte maneira:

Existe uma linguagem e um modelo de computação para o qual o seguinte se aplica:$L$

1. Sabemos como construir uma máquina que calcula que possui m estados.$L$$m$

2. Temos uma prova de que -states máquina para L existe (onde n < < m ), mas de qualquer não podemos encontrá-lo em tudo ou levaria tempo exponencial para calcular isso.$n$$L$$n << m$

Apenas um comentário estendido com um exemplo trivial; você pode escolher o idioma de um elemento:

$L_k$$k$$k$

$k$$L_k$$\leq 2*k(\log k+2)$

$\mathtt{MOD_p} = \{a^{ip} \mid i \geq 0\}$$p$$O(\log p)$

$O(\log^{2+o(1)}p)$$\mathtt{MOD_p}$

REF: Seção 4.2 de (Ambainis e Yakaryilmaz, 2015) .

Outra solução é usar o lema de Higman :

Um idioma fechado em subpalavras é regular.

$u$$v$$u$$v$

Portanto, escolha qualquer linguagem L, seu fechamento de subpalavras é regular, mas não é de todo construtível, pois L é arbitrário.