Décidabilité ... J'ai des doutes :)

[Pechou]

Bonjour à tous !

Je vous fais part de deux problèmes que j'ai résolu, mais j'aimerais avoir des confirmations que ce que j'ai fais est bon, je m'excuse auparavant si certains termes ne sont pas bien choisis mais j'étudie aux Etats Unis et je n'ai pas trouvé toutes les traductions françaises :


Considérons le langage contenant un seul mot S avec :

S = 0 si dieu existe
S = 1 si dieu n'existe pas

Ce langage est-il décidable et si oui, comment le démontrer et si non pourquoi ?

Voici ma réponse :

Ce langage est en fait le langage simple L = {0;1}. On peut facilement décrire ce langage à l'aide d'un automate fini déterministe. C'est donc un langage régulier, il est donc décidable.

Deuxième problème :

Considérons K, K est un automate défini déterministe et L(K) = 'N'importe qu'elle lettre de l'alphabet de K' * (<= opération * ). Montrer que cet ensemble est décidable

Réponse :

Je montre simplement que le langage régulier L1 = 'n'importe quel symbole dans son alphabet' est bien régulier et que les langages réguliers sont clos sous l'opération * donc L est régulier et par extension décidable ?

Qu'en pensez vous ?

[Doraki]

Pour la première question, on a dit que L contenait qu'un seul mot (S).
Alors après pourquoi tu dis que L en contient 2 !?

Pour la 2ème question, le langage reconnu par un automate est régulier, donc décidable.

[Pechou]

Oui tu as raison ...

Dans ce cas, je peux dire que comme le langage ne contient qu'une chaine finie => reconnu par un automate => Décidable

et que Soit dieux existe, soit il n'existe pas donc dans tous les cas décidables ? :id:

[Doraki]

Ben ça dépend de la religion de ton prof, mais le consensus sur la question (depuis Kant), c'est que l'existence de Dieu (et donc le langage L) est indécidable.

[jeancam]

Ben ça dépend de la religion de ton prof, mais le consensus sur la question (depuis Kant), c'est que l'existence de Dieu (et donc le langage L) est indécidable.

il me parrait déja difficilement définissable.

[Pechou]

J'ai peut être oublié de dire que je parle d'un point de vue strictement mathématique ! :briques: