Adakah bukti non-konstruktif tentang keberadaan mesin Turing / NFA “kecil”?

Setelah membaca pertanyaan terkait , tentang bukti keberadaan algoritma yang tidak konstruktif, saya bertanya-tanya apakah ada metode untuk menunjukkan keberadaan mesin komputasi "kecil" (katakanlah, bijaksana) tanpa benar-benar membangunnya.

Secara formal:

misalkan kita diberi beberapa bahasa dan memperbaiki beberapa model perhitungan (NFA / mesin turing / dll.).$L\subseteq \Sigma^*$

Apakah ada hasil keberadaan non-konstruktif menunjukkan mesin -state untuk L ada, tetapi tanpa kemampuan untuk menemukan (di p o l y ( n , | Σ | ) waktu) itu?$n$$L$$poly(n,|\Sigma|)$

Sebagai contoh, apakah ada bahasa biasa yang dapat kita perlihatkan n s c ( L ) ≤ n tetapi kita tidak tahu bagaimana membuat otomat n- state untuk?$L$$nsc(L)\leq n$$n$

( adalah kompleksitas keadaan non-deterministik L , yaitu jumlah negara dalam NFA minimal yang menerima L ).$nsc(L)$$L$$L$

EDIT: setelah beberapa diskusi dengan Marzio (terima kasih!) Saya pikir saya bisa merumuskan pertanyaan dengan lebih baik sebagai berikut:

Apakah ada bahasa dan model perhitungan yang digunakan sebagai berikut:$L$

1. Kami tahu cara membuat mesin yang menghitung yang memiliki status m .$L$$m$

2. Kami memiliki bukti bahwa mesin -states untuk L ada (di mana n < < m ), tapi entah kita tidak dapat menemukannya sama sekali atau itu akan mengambil waktu eksponensial untuk menghitung itu.$n$$L$$n << m$

Hanya komentar yang diperluas dengan contoh sepele; Anda dapat memilih bahasa satu elemen:

$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: Bagian 4.2 dari (Ambainis dan Yakaryilmaz, 2015) .

Solusi lain adalah dengan menggunakan lemma Higman :

Bahasa yang ditutup dengan kata-kata biasa.

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

Jadi ambillah bahasa apa pun L, penutupan subwordnya teratur tetapi sama sekali tidak konstruktif karena L bersifat arbitrer.