conséquences de la complétude et de l'incomplétude

[Médiat]

Un langage formel est un ensemble L (qui peut-être infini) formé de chaînes (finies) formées à partir d'un alphabet (fini).

Il n'est pas interdit d'invisager des chaînes infinies sur des alphabets infinis (cf. les travaux de Barwise ou de Keisler).
-----

[invite4492c379]

Oui mais on sort du domaine des langages formels. Heureusement que ce n'est pas interdit
Néanmoins il faut qu'on me prouve qu'il existe un «langage» L' défini comme une suite de mots sur un alphabet dénombrable qui ne puisse pas être exprimé aussi par un langage L défini sur un alphabet fini.

[Médiat]

Oui mais on sort du domaine des langages formels.

Non, on sort, d'une certaine classe de langages formels, à nouveau je vous renvoie aux travaux de Barwise et Keisler, et d'une façon générale au langages (pour et ), alors que vous vous restreigniez aux langages .

PS : la notation habituelle est effectivement , alors qu'elle devrait être , puisqu'il s'agit de cardinaux et non d'ordinaux.

[Médiat]

Il faut bien sur lire et non alpeh_0

[Médiat]

Et encore le langage de la logique habituelle autorise les alphabets infinis (exemple : les symboles de constantes de ).

[invite4492c379]

L'alphabet reste fini, non ?

[invite4492c379]

Et encore le langage de la logique habituelle autorise les alphabets infinis (exemple : les symboles de constantes de ).

????
Je me place toujours hors sémantique quand je parle de langage formel (pour l'instant). Je n'ai jamais précisé que c'était interdit, loin de moi cette idée. J'ai juste précisé que dans l'étude des langages formels classiques que j'ai abordé , l'alphabet était toujours fini, que pour la définition classique (enseignée dans les années 90), on pouvait toujours ramener le cas «alphabet infini dénombrable» au cas «alphabet fini».
Maintenant heureusement que l'on cherche dans toutes les directions, tout comme on peut chercher dans la direction «que signifie la notation décimale infinie 0.99999...9 où le dernier 9 a pour rang ».

D'où ma question ... quel langage formel construit sur un alphabet dénombrable ne peut pas être exprimé par un langage formel construit sur un alphabet fini ?

[invite7863222222222]

L'alphabet reste fini, non ?

Pourquoi restreindre ? ca fait longtemps, voir une éternité qu'on pense les entiers comme un ensemble infini.

[invite4492c379]

La notation décimale est un langage formel construit sur un alphabet fini A={0,1,2,3,4,5,6,7,8,9}, tous les entiers ont une représentation décimale finie et chaque représentation décimale défini un unique entier. Le langage décrit est dénombrable.

[invite7863222222222]

Justement, je le vois plus construit uniquement sur l'alphabet {0}, la fonction successeur et la fonction "concaténation".

[invite4492c379]

dans ce cas la langage est différent, l'alphabet est toujours fini A={0,succ,')','('}, A est l'ensemble des terminaux et on a les règles de productions :

ENTIER := 0
ENTIER := succ'('ENTIER')'

[invite7863222222222]

Oui, il est toujours fini, mais le pgcd de tous algorithmes, c'est "succ", et donc à la place, il "suffit" de mettre {0, 1, ....}.

[invite4492c379]

On parle du langage (qui peut ne pas être fini) ou de l'alphabet (qui dans mes souvenirs et dans les définitions usuelles est fini) ?

[invite4492c379]

Juste pour être sûr que nous parlons tous de la même chose.

Un alphabet A est un ensemble fini quelconque (lettres).
Les mots (ou chaînes) sur un alphabet A sont toutes les suites finies d'éléments de A
Les mots sont souvent notés par la séquence sans séparateur de leurs lettres.

On note A^* l'ensemble des mots. Un langage L est un sous-ensemble de A^*.

On peut ensuite définir une grammaire qui est la donnée de deux alphabets (les terminaux et les non-terminaux), un ensemble d'axiomes et des règles de production. Il existe des langages formels engendrés par ces grammaires formelles.

On peut ensuite éventuellement réaliser ce langage en lui associant une sémantique.

[Médiat]

J'ai juste précisé que dans l'étude des langages formels classiques

Tout est là or cette précision n'apparaît pas dans votre première intervention, d'où ma réaction.

D'où ma question ... quel langage formel construit sur un alphabet dénombrable ne peut pas être exprimé par un langage formel construit sur un alphabet fini ?

Comment faites-vous avec un langage comprenant un nombre dénombrable de prédicats n-naires (par exemple), pour tout n entier ?

[invite4492c379]

Je parle d'alphabet ... qui reste fini; ensuite si on peut trouver des règles de dérivations pour produire ces prédicats ...
Je n'ai pas non plus dit que tout langage était exprimable par un langage formel (cf Chomski et sa hiérarchie).

[Médiat]

Je parle d'alphabet ... qui reste fini

Les prédicats faisant partie de l'alphabet, l'exemple que je donne n'est pas fini.

Je me répète, mais pourquoi ne vous renseignez-vous pas sur les travaux de Keisler ou de Barwise ?

[invite4492c379]

Les prédicats faisant partie de l'alphabet, l'exemple que je donne n'est pas fini.

Je me répète, mais pourquoi ne vous renseignez-vous pas sur les travaux de Keisler ou de Barwise ?

Les prédicats ne font pas partie de l'alphabet ou alors nous ne parlons pas du tout de la même chose. Je suis en train de lire ce document, par exemple.

[invite4492c379]

Mediat, sommes-nous au moins d'accord sur cela :

Juste pour être sûr que nous parlons tous de la même chose.

Un alphabet A est un ensemble fini quelconque (lettres).
Les mots (ou chaînes) sur un alphabet A sont toutes les suites finies d'éléments de A
Les mots sont souvent notés par la séquence sans séparateur de leurs lettres.

On note A^* l'ensemble des mots. Un langage L est un sous-ensemble de A^*.

On peut ensuite définir une grammaire qui est la donnée de deux alphabets (les terminaux et les non-terminaux), un ensemble d'axiomes et des règles de production. Il existe des langages formels engendrés par ces grammaires formelles.

On peut ensuite éventuellement réaliser ce langage en lui associant une sémantique.

?
Du moins sur ce que sont un alphabet,un langage,un langage formel ?

[invitef17c7c8d]

Les logiciens ont ce doux rêve de penser qu'ils réussiront à alphabétiser les mathématiques!
Je soupsonne Mediat d'être dans ce cas là.
C'est Hilbert qui a débuté cette entreprise, suite à la crise qu'a connu la géométrie avec la découverte de Riemann. Riemann renvoit dans ses cordes Euclide et ses axiomes. La géométrie perd après Riemann tout sens physique!

Mais entre nous, n'est-il pas horrible d'imaginer un monde où l'intelligibilité de la nature nous serait donner par les machines?!
Heureusement que le théorème de Godel est là pour nous dire que cette entreprise est impossible!

La démonstration d'un théorème basée sur les implications mécaniques d'une machine et celle basé sur des concepts géométriques, de symétries ou autres n'ont pas la même beauté!!

[Médiat]

Les logiciens ont ce doux rêve de penser qu'ils réussiront à alphabétiser les mathématiques!
Je soupsonne Mediat d'être dans ce cas là.

Je ne vous autorise pas à soupçonner quoi que ce soit sur ce que je pense, surtout de telles âneries.

[Médiat]

Mediat, sommes-nous au moins d'accord sur cela

Vous prenez comme définition que l'alphabet est fini, donc après ce n'est pas étonnant que vous affirmiez qu'un alphabet est fini, mais je vous assure que, même la logique classique autorise un alphabet infini. Vous trouverez cela en page 2 du document de Keisler que vous citez.

Comment faites-vous pour parler d'une infinité de prédicats si ceux-ci ne sont pas dans le langage ?

[Médiat]

Je ne vous autorise pas à soupçonner quoi que ce soit sur ce que je pense, surtout de telles âneries.

Pour information plus aucun logicien ne pense cela depuis 1931.

[invite4492c379]

Vous prenez comme définition que l'alphabet est fini, donc après ce n'est pas étonnant que vous affirmiez qu'un alphabet est fini, mais je vous assure que, même la logique classique autorise un alphabet infini. Vous trouverez cela en page 2 du document de Keisler que vous citez.

Comment faites-vous pour parler d'une infinité de prédicats si ceux-ci ne sont pas dans le langage ?

*Je* ne prends rien, il s'agit de la définition usuelle utilisée (et a priori enseignée), cela permet à tout le monde de parler de la même chose.
Je dis simplement que si on ne respecte pas cette définition on ne parle plus de langage formel. Je ne dis pas que l'on ne peut étendre la définition pour trouver autre chose, mais il ne s'agit plus de langages formels.

Dans le document, l'auteur utilise le terme vocabulary. Il le définit comme :

By a vocabulary, we mean a set L of constant symbols, and
relation and operation symbols with finitely many argument places.

Cela ne correspond en rien à ce que «usuellement» est nommé alphabet. Dans le cadre d'une grammaire formelle, je comprends cette définition comme l'ensemble des terminaux, non-terminaux, axiomes et règles de productions avec une réalisation précise dans le domaine de la logique.

Ce qui me pousse à penser cela est simplement la phrase :

The equality symbol is always available, but is not counted as
an element of the vocabulary L.

On emploierai un symbole qui n'est pas dans un des alphabets ? (un langage formel est toujours défini par deux alphabets).

Je dois certainement mal comprendre ce document ou la démarche, mais elle ne correspond pas aux définitions que l'on trouve dans l'enseignement des langages formels.

[invite7863222222222]

Photon dans l'enseignement on ne définit pas ce qu'est un langage formel, ce n'est que quand on a un niveau certain et que l'on fait de la logique qu'on s'intéresse à ce genre de chose.

Et quand on a ce niveau on peut tout à fait comprendre qu'on peut envisager des phrases avec un nombre infini de symboles. Je crois qu'on ne parle pas de la même chose car il n'y a rien de spécial dans ce que je dis.

[invite4492c379]

C'est un enseignement de fac ...niveau licence info des années 90 (de souvenir pour le niveau ...).
Je n'ai jamais dit que l'on ne pouvait pas considérer les alphabets démombrables, je dis simplement que «langage formel» a une définition. Si on l'étend on ne parle plus de la même chose et les propriétés peuvent différer. C'est comme dire que existe car on arrive à définir une fonction qui coïncide avec factorielle sur les entiers ...

[invite7863222222222]

Si tu prends un programme qui va exécuter une boucle, puis à un certain moment va prend le résultat temporaire de cette bouclet va chercher parmi un ensemble E, un programme qui va faire quelque chose avec ce résultat (pour simplifier mais ça pourraitetre traiter un autre nombre de la boucle) notamment encore la même chose quavant (aspect récursif).

Si les différentes boucles génèrent des résultats globalement croissant, et quon demande que les elements de E soit bijectif avec les nombres générés alors l'ensemble E est infini.

il suffit de considérer le système formel qui formalise ce que je viens de décrire, il me semble que les éléments de E, sont ce qu'on pourra appeler l'alphabet du système que j'ai décrit, si on exige un certain comportement global du système. La définition du sens des éléments de l'alphabet est donné par l'exigence de satisfaire ce comportement. On ne peut expliciter ces programmes avec un alphabet fini notamment car ces programmes peuvent pourquoi pas contenir des fonctions non calculables.

[invite4492c379]

Ce que tu écris est très flou pour moi : je ne comprends pas ce que tu décris. Je ne peux donc rien dire ...


Mais tu fais apparaître le terme système formel. Par définition, les éléments d'un système formel forment un ensemble récursif donc on peut vérifier algorithmiquement (au sens usuel du terme) si un élément fait partie ou non de ce système formel ; or tu conclue que «ces programmes représentent des fonctions non calculables», je sens comme une contradiction, au pire un grande incompréhension (entre nous).

Je ne dis pas que je comprends mieux, mais je persiste à dire qu'il ne faut pas utiliser des termes qui ont des significations précises dans des contextes qui leurs donnent d'autres significations et propriétés. Imagine un étudiant passant par là et prenant pour argent comptant ce qui est écrit ...

[invite6754323456711]

Du moins sur ce que sont un alphabet,un langage,un langage formel ?

Il semble exister aussi la notion de famille abstraite de langage sur un alphabet infini.

Maintenant à partir d'un alphabet fini (ex. les chiffres) on peut construire une infinité de mot (ex. les nombres). Ce qui importe n'est-il pas d'exprimer des énoncés/propositions qui portent sur des mots (qui peuvent être codifié dans un alphabet infini si besoin) et non sur l'alphabet qui n'est qu'un intermédiaire pour construire ces derniers ?

Patrick

[invite7863222222222]

Ce n'est pas parceque tu ne peux pas calculer la solution que tu ne peux pas prendre l'initiative de faire quelque choses à partir de l'énoncé (comme par exemple le traduire en un algorithme qui va en chercher la solution sans garantie qu'il s'arrête un jour puisque le problème n'est pas calculable). J'espère que tu vois un peu mieux l'idée.

Cela pour moi c'est aussi un algorithme, j'ai essayé de faire le lien entre algorithme et système formel pour te satisfaire mais je suis surpris autant que toi que ça colle avec des idées que j'avais au départ et qui semblaient plutôt éloignées au premier abord. Enfin bon.