Existe-t-il un langage fini indécidable de mots finis?

10

Y at - il un besoin pour être infini indécidable? $L\subseteq \Sigma^*$

Je veux dire que si nous choisissons une langue être une version finie bornée de , c'est-à-dire , ( ), avec . Est-il possible que soit un langage indécidable? $L'$ $L\subseteq \Sigma^*$ $|L'|\leq N$ $N \in \mathbb{N}$ $L' \subset L$ $L'$

Je vois qu'il y a un problème de "Comment choisir les mots qui pour lequel nous devons établir une règle pour choisir quels seraient les premiers éléments de , une sorte d'étoile de Kleene "finie" opération. Le but est de trouver un langage indécidable sans avoir besoin d'un ensemble infini, mais je ne le vois pas. $N$ $\in$ $L' "$ $N$ $L'$

Note éditée:

Bien que j'aie choisi une réponse, de nombreuses réponses et tous les commentaires sont importants.

formal-languages computability undecidability Hernan_eche
la source

Il semble y avoir (au moins) trois questions ici. Veuillez vous concentrer sur l'un et éditer les autres.

Raphael

J'ai supprimé les références à l'ensemble de puissance car il n'est pas pertinent ici;

P (S)

$\mathcal{P}(S)$ est fini si et seulement si

S

$S$ est fini.

Raphael

@Raphael C'est bon, mais je mentionne le jeu de puissance car parfois je lis "il n'y a pas de surjection de sur , donc il doit exister un langage indécidable." $\mathbb{N}$ $\mathcal{P}(\mathbb{N})$ Je voudrais comprendre pourquoi cela n'a pas fonctionné avec un ensemble fini , avec avec fini, au lieu d' avoir besoin de , c'est pourquoi je mets

L^{'}

$L'$

| L^{'} | \leq N

$|L'|\leq N$

N

$N$

N

$\mathbb{N}$

P (S)

$\mathcal{P}(S)$

Hernan_eche

1

Autant que je sache, l'existence de langages indécidables ne découle pas immédiatement de l'inexistence d'une telle surjection; vous avez besoin de quelques petits morceaux de plus. Eh bien, cela ferait une autre merveilleuse question! Pourquoi n'allez-vous pas le demander? À partir de celui-là, vous devriez voir pourquoi l'argument ne s'applique pas aux langages finis.

Raphael

3

Le langage fini est décidable, période, fin de l'histoire. Il existe un certain nombre d'algorithmes pour cela. Si vous insistez sur le modèle classique de la machine de Turing, cela peut aussi être fait de cette façon, mais avec moins de perspicacité. Pas besoin d'invoquer des automates à états finis ou des langages normaux ou tout autre modèle d'automate, car ils sont en fait exagérés sans aucune clarté supplémentaire vis-à-vis des machines de Turing.

David Lewis

15

Oui, il faut que soit infini pour être indécidable. $L$

Pour résumer les réponses de Raphaël et de Sam, vous devriez considérer «décidable» comme des choses qu'un programme informatique peut résoudre. Le programme requis est très simple, il suffit de sortir "Oui" pour les éléments en , ou sinon, dire non. $L$

Ainsi, plus est «complexe» , plus le programme que vous devez écrire est long. En d'autres termes, plus le programme est long, vous pouvez vérifier plus de choses ... Donc, si quelqu'un donne un langage qui est fini, disons , vous pouvez écrire le programme suivant: $L$ $L$ $L=\{ a_1, a_2, \ldots, a_n\}$

if INPUT = $a_1$ output Yes;
if INPUT = $a_2$ output Yes;
...
if INPUT = $a_n$ output Yes;
output No;

Maintenant, si quelqu'un vous donne un plus grand (mais fini), vous écrirez simplement un programme plus long. C'est toujours vrai, et tout fini aura son propre programme. Le seul cas "intéressant" est ce qui se passe lorsque est infini - votre programme ne peut pas être infini. $L$ $L$ $L$

La question de la « indécidabilité » est encore plus intéressante: ses (ces infinis) « s qui ont aucun programme qui fonctionne correctement pour eux. Nous savons que de tels langages doivent exister car il y a bien plus de langages (infinis) que le nombre de programmes de longueur finie (mais illimitée). $L$ $L$

A sonné.
la source

+1 Ceci est une réponse très claire, j'aimerais que vous développiez un point, vous avez dit "si quelqu'un vous donne un plus grand (mais fini), vous écrirez simplement un programme plus long" * mais je pense que le opposé, étant donné un ** fixe ** ensemble fini de programmes , si vous ne pouvez pas écrire un programme plus je pense que certains imputs un ensemble fini de, sera sur OUI, et d' autres non . Comme , alors certaines des entrées correspondront aux fonctions d'indicateur mais * la plupart $L$ $P$ $|P|=K$ $\in L$ $\mathcal{P}(P) \gt K$ $\in L$ $P$ ne le seront pas!, Car langues possibles

2^{K}

$2^K$

> K

$\gt K$ programmes possibles, il y aura alors des problèmes indécidables. Ai-je tort? Pourquoi?

Hernan_eche

1

en effet, si vous limitez la taille du programme à alors il y a au plus différents programmes qui classent correctement au plus différentes langues (infinies ou non). Donc, pour cet ensemble spécifique de programmes, il existe des langages indécidables et même finis. Mais c'est une affirmation plus faible, car vous ne considérez qu'un ensemble limité de programmes (par exemple, , vous n'avez que 2 programmes possibles; bien sûr, ils ne pourront pas faire grand-chose et échoueront dans presque toutes les langues )

| P | = k

$|P|=k$

O (2^{k})

$O(2^k)$

O (2^{k})

$O(2^k)$

| P | = 1

$|P|=1$

L

$L$

Ran G.

merci, je sais que c'est une affirmation plus faible, mais il est audacieux qu'il puisse y avoir des langues indécidables finies et infinies, et je pense que ce cas spécial doit être inclus dans votre réponse, le parte "Oui, il faut que L soit infini dans pour être indécidable. " ne semble pas être un besoin sous certaines conditions.

Hernan_eche

6

Pas exactement. Le terme "indécidable" a une signification spécifique: non décidable par une machine de Turing standard. Ainsi, pour être undecidable, doit être infini. Ce que vous voulez, ce n'est pas un terme différent, à savoir "non décidable par ". Appelez ce dernier indécidable. Alors là pour tout fini , il n'est pas nécessaire que soit infini pour être indécidable. Ne confondez pas (ou abusez) et indécidable

L

$L$ undecidable

P

$P$

P

$P$

P

$P$

L

$L$

P

$P$ undecidable

P

$P$

Ran G.

10

Je ne suis pas sûr de bien comprendre la question, mais chaque langue finie est régulière. Il n'y a pas de langues régulières indécidables et donc pas de langues finies indécidables. Toutes ces déclarations sont bien connues et des preuves peuvent être trouvées dans Hopcroft et Ullman .

Sam Jones
la source

8

Si votre langue est finie, vous pouvez effectuer une recherche de table sur une table codée en dur contenant tous les mots en . C'est gênant à écrire comme machine Turing, mais dans d'autres modèles équivalents, c'est assez clair. $L'$ $L'$

En fait, les automates finis sont suffisants. Construisez un automate pour comme suit: $L'$

Pour chaque , créez une chaîne linéaire d'états qui accepte . $w \in L'$ $w$
Créez un nouvel état initial . $q_0$
Connectez aux états initiaux de tous les automates construits en 1. avec -transitions. $q_0$ $\varepsilon$

L'automate ainsi construit accepte évidemment . Par conséquent, est régulier et donc calculable (par ). $L'$ $L'$ $\mathrm{REG} \subsetneq \mathrm{RE}$

Notez que le raisonnement s'applique à la co-finie , c'est-à-dire ; vous codez en dur les éléments qui ne sont pas dans . $L'$ $\big|\overline{L'}\big| < \infty$ $L'$

Raphael
la source

2

Pour être intéressant du tout (dans le but de réfléchir à la calculabilité), un problème de décision doit avoir une infinité de réponses «oui» et une infinité de réponses «non». De tels problèmes de décision correspondent exactement aux langues qui contiennent une infinité de chaînes sur leur alphabet et excluent également une infinité de chaînes sur leur alphabet.

Tout le reste est trivialement capable d'être encodé dans seulement une quantité finie d'informations (au pire simplement une grande liste de chaînes dans ou non dans le langage), et donc calculable par de simples DFA / expressions régulières. J'espère qu'il devrait être évident que pour toute liste finie de chaînes, vous pouvez immédiatement écrire une expression régulière qui fait simplement OU toutes les chaînes.

Un esprit de mon professeur de théorie du calcul était que le problème de "Dieu existe-t-il?" est calculable - il est calculé soit par une machine qui accepte immédiatement, soit par une machine qui rejette immédiatement; nous ne savons simplement pas lequel!

Ben
la source

Existe-t-il un langage fini indécidable de mots finis?

Réponses: