Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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.
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.
Dernière modification par Médiat ; 01/12/2011 à 13h11.
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Il faut bien sur lireet non alpeh_0
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Et encore le langage de la logique habituelleautorise les alphabets infinis (exemple : les symboles de constantes de
).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
L'alphabet reste fini, non ?
????
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 ?
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.
Justement, je le vois plus construit uniquement sur l'alphabet {0}, la fonction successeur et la fonction "concaténation".
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')'
Oui, il est toujours fini, mais le pgcd de tous algorithmes, c'est "succ", et donc à la place, il "suffit" de mettre {0, 1, ....}.
Dernière modification par invite7863222222222 ; 01/12/2011 à 14h15.
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) ?
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.
Tout est là or cette précision n'apparaît pas dans votre première intervention, d'où ma réaction.
Comment faites-vous avec un langage comprenant un nombre dénombrable de prédicats n-naires (par exemple), pour tout n entier ?
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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).
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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.
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 ?
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é!!
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
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 suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
Je suis Charlie.
J'affirme péremptoirement que toute affirmation péremptoire est fausse
*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.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 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 :
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.By a vocabulary, we mean a set L of constant symbols, and
relation and operation symbols with finitely many argument places.
Ce qui me pousse à penser cela est simplement la phrase :
On emploierai un symbole qui n'est pas dans un des alphabets ? (un langage formel est toujours défini par deux alphabets).The equality symbol is always available, but is not counted as
an element of the vocabulary L.
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.
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.
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 queexiste car on arrive à définir une fonction
qui coïncide avec factorielle sur les entiers ...
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.
Dernière modification par invite7863222222222 ; 01/12/2011 à 20h00.
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 ...
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
Dernière modification par invite6754323456711 ; 01/12/2011 à 21h11.
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.
Dernière modification par invite7863222222222 ; 01/12/2011 à 21h34.