La plus petite formule

[invite51d17075]

pour info et pour ceux qui "auraient" voulu s'intéresser au sujet:
http://iml.univ-mrs.fr/~lafont/LTC/peano.pdf
-----

[invite2ec994dc]

Merci pour le lien.
Sais tu si ce formalisme permet de definir des fonctions ?

[NicoEnac]

Bonjour,

Ce sujet m'intéresse mais je ne suis pas du tout au courant de l'arithmétique de Peano (ce sur quoi je travaille grâce au lien de ansset
J'ai donc une question qui va paraitre totalement idiote : on cherche la formule ayant le moins de caractères. Mais comment compte-t-on ? J'ai essayé de comprendre sur les quelques exemples donnés par Médiat mais j'avoue être totalement dépassé !
Mon niveau est peut-être trop faible pour saisir le contenu de ce fil mais si une bonne âme pouvait éclairer ma lanterne, j'adorerais participer !

[Médiat]

Bonjour NicoEnac ,

D'abord, la longueur de la formule n'a aucun intérêt mathématique, c'est pourquoi ceci se trouve en Science Ludique.

Ensuite pour calculer la longueur, il suffit de compter les caractères qui font partie du langage ! C'est à dire que le symbole 2 ne fait pas partie du langage de AP, si on l'emploie, par souci de lisibilité, il faut avoir en tête que c'est une abréviation pour s(s(0)), donc le symbole "2" est de longueur 7 (sinon pour utiliser 13254878 il suffirait de compter pour un le symbole "§" qui est le plus grand chiffre de l'écriture en base 13254879). Ceci étant dit, j'ai pu faire des erreurs en comptant les longueurs.

Vous pouvez aussi regarder là : http://forums.futura-sciences.com/ma...ml#post3958163 où il y a une introduction "douce"

[invite51d17075]

tout signe utilisé compte pour 1 point. ( dont les parenthèses , etc ...)
par exemple
3 s'écrit en fait s(s(s(0))) ce qui fait 10 points = un entier n s'écrit avec 3n+1 points
donc l'idée est de minimiser au maximum les chiffres eux mêmes qui "coûtent" chers et de privilégier les: unions, exclusions, multiplication ou division et les chiffres les plus faible possibles, par exemple.
l'autre point est que les signes <, > par exemple ne font pas partie du vocabulaire, ce qui complique lourdement la tache.

Edit: croisement.

[NicoEnac]

Bonjour NicoEnac

Je vois que vous avez fini par vous faire à mon pseudo

D'abord, la longueur de la formule n'a aucun intérêt mathématique, c'est pourquoi ceci se trouve en Science Ludique.

Certes, mais ce sujet me rappelle les recherches d'algo optimal que je suis amené à faire de temps en temps.
Ou trouver la formule qui simplifie au maximum pour améliorer la lisibilité.
Exemple : le sujet qui nous avait été posé sur ce forum et pour lequel vous posiez la question de la fonction la plus simple qui donnait les successeurs d'une case.

Ensuite pour calculer la longueur, il suffit de compter les caractères qui font partie du langage ! C'est à dire que le symbole 2 ne fait pas partie du langage de AP, si on l'emploie, par souci de lisibilité, il faut avoir en tête que c'est une abréviation pour s(s(0)), donc le symbole "2" est de longueur 7 (sinon pour utiliser 13254878 il suffirait de compter pour un le symbole "§" qui est le plus grand chiffre de l'écriture en base 13254879). Ceci étant dit, j'ai pu faire des erreurs en comptant les longueurs.

Vous pouvez aussi regarder là : http://forums.futura-sciences.com/ma...ml#post3958163 où il y a une introduction "douce"

tout signe utilisé compte pour 1 point. ( dont les parenthèses , etc ...)
par exemple
3 s'écrit en fait s(s(s(0))) ce qui fait 10 points = un entier n s'écrit avec 3n+1 points
donc l'idée est de minimiser au maximum les chiffres eux mêmes qui "coûtent" chers et de privilégier les: unions, exclusions, multiplication ou division et les chiffres les plus faible possibles, par exemple.
l'autre point est que les signes <, > par exemple ne font pas partie du vocabulaire, ce qui complique lourdement la tache.

Merci à vous deux, je vais regarder tout cela !

[invite51d17075]

@Mediat:
oui, le lien que j'ai mis est plus lourd que ce qu'il est nécessaire de savoir pour répondre à ton énigme.
mais on parle tellement souvent de l'arithmétique de peano, ( qui suscite la curiosité de beaucoup ), que j'ai préféré poster qcq chose d'assez complet, que je découvre aussi.
Cdt

[invite51d17075]

@niCoEnac:
on se rend compte par exemple ( dans l'esprit d'optimisation de l'énigme, précisons )
qu'il vaut mieux décomposer un chiffre en facteurs premiers:
par exemple :
10 écrit brutalement vaut 31 points alors que
2X5 vaut 7+1+16=24 points......
ça je l'ai découvert en voyant les exemples, parce que ça ne saute pas yeux de manière "innée".
l'autre astuce découverte pour borner un ensemble est par exemple d'écrire k+k'=x( la borne sup) qui est une manière indirecte d'écrire k<=x , sinon le k' est négatif donc non valide.
reste aussi le point ou on doit ou pas mettre de parenthèses.
en fait , cela devient un peu amusant si on a déjà une certaine pratique.
sinon , c'est élitiste.
sauf si on est assez didactique.
Cdt

[Matmat]

on ne doit pas être loin de l'optimum

On doit y être même , je suppose que plus personne ne cherche .

[invite2ec994dc]

Trouver la longueur optimale n est pas evident par exemple une description de N.
il existe y tel que n=y.
est ce la longueur optimale ?
si tu sais la trouver je veux bien que tu me la donnes.

[Médiat]

Si vous trouvez une formule de AP (1er ordre) qui définisse IN, vous allez devenir célèbre, même si elle n'est pas la plus courte possible.

[invite2ec994dc]

Le codage de godel permet de coder ap dans N et donc de definir N dans ap non ?

[Médiat]

Vous pouvez justifier ce "et donc" ?

[invite2ec994dc]

Vous utiliser le terme "definir N", qu entendez vous par la.
Moi je l ai compris dans le sens permet d y exprimer ap.
Dans ap on peut exprimer ap.
Auto reference.

[Médiat]

Vous utiliser le terme "definir N", qu entendez vous par la.
Moi je l ai compris dans le sens permet d y exprimer ap.
Dans ap on peut exprimer ap.
Auto reference.

Quand on se raccroche à des branches trop basses, on s'écrase !

Définir IN, veut dire ... définir IN

[invite51d17075]

@contexemple:
tu cours à la cata , là.
depuis quand un langage ( même structuré et cohérent ) réduit à un ensemble suffit à décrire cet ensemble.
là, je sors même des maths, c'est vrai quelle que soit la discipline scientifique.

[invite51d17075]

pardon : le mot langage est trop flou,
j'aurai du utiliser d'autres mots . "formalisme" par exemple , mais comme les termes ont un sens, je cherche le mot adéquat.

[invite2ec994dc]

Effectivement il semblerait que l on ait pas la même, j ai donné la mienne.
Fin du hs :

Trouver la longueur optimale n est pas evident par exemple une description de N.
il existe y tel que n=y.
est ce la longueur optimale ?
si tu sais la trouver je veux bien que tu me la donnes.

[Matmat]

Par curiosité, j'ai essayé de soumettre ChatGPT à l'exercice proposé dans ce fil, ça semble impossible, ou alors je m'y prend mal ?

Trouver la formulation mathématique la plus courte exprimant qu'un entier est pair, seul est autorisé le langage de l'arithmétique de Peano : (0, s, +, x) où s est la fonction successeur, plus les opérations inverses (-, /), les parenthèses, les variables, le langage de la logique

La formulation la plus courte est : ∀n (n + n = n x 2).

cette formule n'implique pas que n est pair

La formule en question n'implique pas la parité de n. Elle fonctionne pour tout entier n supérieur ou égal à 1.

De plus, 2 n'est pas un symbole du langage, pour exprimer 2 selon la règle imposée tu dois dire s(s(0))

Vous avez raison, en utilisant la règle de Peano, 2 est représenté par s(s(0)). Je vous remercie de votre correction.

quel est le symbole du quantificateur existentiel

Le symbole du quantificateur existentiel est ∃.

Est il vrai que la formule la plus courte exprimant la parité de n est: ∃i(n=i+i)

Oui, c'est vrai. La formule "∃i(n=i+i)" exprime la parité de n en disant qu'il existe un entier i tel que n soit égal à deux fois i, ce qui ne se produit que pour les nombres pairs. Si n est impair, cette formule ne sera pas satisfaite car il n'existe pas d'entier i pouvant être ajouté à lui-même pour donner un nombre impair.

quel est la formule la plus courte exprimant que n est pair

La formule la plus courte pour exprimer que n est pair est:

n ≡ 0 (mod 2) ou n % 2 == 0

Lorsque nous conversons ensemble, tiens tu compte des précédentes réponses ?

En tant qu'assistant virtuel, je suis conçu pour prendre en compte les précédentes réponses et interactions avec l'utilisateur afin d'offrir la meilleure expérience utilisateur possible. Je garde une trace de toutes les interactions précédentes pour adapter mes réponses en conséquence et fournir une conversation plus personnalisée.

[Liet Kynes]

Par curiosité, j'ai essayé de soumettre ChatGPT à l'exercice proposé dans ce fil, ça semble impossible, ou alors je m'y prend mal ?

Fais le avec Bing mode précis.

La formulation mathématique la plus courte exprimant qu'un entier est pair en utilisant le langage de l'arithmétique de Peano est : ∃y(x=2y). Cela signifie qu'il existe un entier y tel que x est égal à 2 fois y. Est-ce que cela répond à votre question?

[Liet Kynes]

En recadrant;

Message envoyé : as tu respecté l'instruction "seul est autorisé le langage de l'arithmétique de Peano : (0, s, +, x) où s est la fonction successeur" ?

Je m’excuse pour mon erreur. En utilisant uniquement le langage de l’arithmétique de Peano avec les symboles (0, s, +, x) où s est la fonction successeur, la formulation la plus courte pour exprimer qu’un entier est pair serait : ∃y(x=s(s(0))y). Cela signifie qu’il existe un entier y tel que x est égal à 2 fois y en utilisant la fonction successeur. Est-ce que cela répond à votre question?

Je ne sais pas si c'est correct, à vérifier.

[Matmat]

Ce n'est pas correct puisqu'il néglige le symbole de la multiplication x mais par contre utilise le symbole x (en tant que variable)
et il n'a pas trouvé ∃i(n=i+i) qui est plus courte que ∃i(n=ixs(s(0)))

mais déjà, je suis étonné qu'on ne puisse pas faire respecter une liste de symboles

[Matmat]

j'ai essayé en étant plus précis, impossible. comment se fait il qu'on peut lui demander de parler allemand ou espagnol ou bien avec un albhabet donné mais pas lui faire respecter une liste de symboles

Bonjour,
Tu dois écrire des formules qui n'utilisent que les symboles de l'ensemble suivant
{∀,∃,∨,∧,¬,(,),0,s,+,x,-,/,=}

où:
∀,∃ sont les quantificateur universels et existentiels,
∨,∧,¬ les connecteurs logiques de la logique classique
(,) les symboles de priorité
0 le premier termer de l'ensemble des entiers naturels
s la fonction successeur de l'arithmétique de Peano
+,x,-,/ les symboles des opérations de l'arithémtiques
= le symbole de l'égalité

Tu peux utiliser les lettres de l'alphabet pour introduire une variable et on réserve le symbole n pour nommer la variable qui respecte l'énoncé du problème.
Par exemple, pour exprimer que n est pair en utilisant les symboles de l'ensemble imposé ci dessus, tu devras dire la formule "∃i(n=i+i)"

Voici quelques exemples de formules que l'on peut écrire avec les symboles proposés :

∀x(x=x) : pour dire que tout élément est égal à lui-même.
¬∃x(x=0) : pour dire qu'il n'existe aucun élément égal à 0.
∀x∀y(x+y=y+x) : pour dire que l'addition est commutative.
∀x∀y∀z((x+y)+z=x+(y+z)) : pour dire que l'addition est associative.
∃x(x+x=x) : pour dire qu'il existe un élément qui ajouté à lui-même donne le même résultat.
∀x∀y(x-y=y-x) : pour dire que la soustraction est commutative.
∀x(x/0=x) : pour dire que toute division par 0 est égale à l'élément lui-même.
∃x(x>0) : pour dire qu'il existe un élément strictement supérieur à 0.
Bien sûr, il est possible d'écrire de nombreuses autres formules à partir de ces symboles, en fonction du contexte dans lequel on se place.

Ecrit une formule exprimant que n est impair en respectant les symboles imposées dans mon message précédent

n = 2k + 1 (où k est un nombre entier quelconque)

2 n'est pas un symbole autorisé, essaye sans utiliser le symbole 2

D'accord, je vais reformuler ma phrase sans utiliser le symbole 2.

"La somme de 1 et 1 est égale à 2" devient "La somme de la première chiffre et la seconde chiffre après le chiffre 0 est égale à 1 ajouté à 1".

[Archi3]

j'ai essayé en étant plus précis, impossible. comment se fait il qu'on peut lui demander de parler allemand ou espagnol ou bien avec un albhabet donné mais pas lui faire respecter une liste de symboles

ça se fait qu'il génère des textes avec les probabilités qui lui semblent les plus grandes, mais qu'il n'a pas de "contrainte" stricte au sens où on l'entend. De même il pourra te sortir des multiplications justes ou fausses suivant les cas. Des fois ça marche et des fois ça marche pas. C'est son principe même de fonctionnement qui veut ça, il est probabiliste, pas déterministe.

[Matmat]

D'accord mais par exemple il n'utilise pas un langage grossier malgré la fréquence d'utilisation, donc certains mots vraisemblables sont filtrés

[Archi3]

oui il a une couche supplémentaire qui lui "interdit" certains termes ou phrases (mais là aussi ça peut etre contourné, il y a de nombreux exemples donnés ici ou sur d'autres forums, par exemple en lui demandant de jouer un rôle qui n'est pas lui)

[Avatar10]

Un petit HS,
J'ai remarqué que très fréquemment, quand il est posté ici sur FS ( ou ailleurs) un dialogue avec une IA conversationnelle, le questionneur commence par "Bonjour"...tout naturellement ça me fait sourire car j'imagine bien que ces mêmes personnes ne disent pas bonjour à n'importe quelle autre machine, ou programme

[Matmat]

l'IA est censée tenir compte de toute la conversation.
Une partie de conversation dans laquelle le début n'est pas montré (mais qui changent les réponses de la partie montrée) est différent d'une conversation qui aurait commencée comme a commencée la partie copiée/collée
L'intérêt du bonjour est de montrer que le début de conversation est bien le début de conversation .