Le plus grand sujet de dispute de mon domaine.

J'ai réalisé que ces derniers temps, mes deux sujets principaux sont l'homosexualité, principalement la lutte contre l'homophobie, et la scène. Ça fait un bail que je ne parle plus de science, d'informatique ou de math, et en particulier de mon travail. Je vais essayer de rattraper ça.

Même les mathématiques ne sont pas exempte de dispute. Par exemple, sur la manière de nommer des choses. Je vais donc vous narrer ce qui a été la plus grande source de désaccord scientifique que j'ai vu durant mon année et demi de thèse dans mon petit domaine à moi. Je vais être précis, mais j'ai l'espoir que le sel du billet soit compréhensible par ceux qui ne sont pas du domaine.

En théorie des langages, on a 3 mots différents pour définir la même chose. Langage rationnels, langage régulier ou langage reconnaissable. En gros, la différence, c'est la même que savoir si un carré c'est un rectangle avec 2 côté adjacent de même longueur, ou si c'est un losange avec un angle droit. À la fin, on trouve toujours la même chose, quelque soit la définition prise.


(Vous pouvez sautez les trois paragraphes suivant, j'essaye d'expliquer en français l'idée mathématique, c'est probablement mal dit pour les matheux, et incompréhensible pour les non matheux):

Pour être plus précis, "rationnel" ça signifie qu'on peut créer le langage en utilisant des ensembles de bases (l'ensemble vide et ceux qui contiennent une unique lettre) avec un nombre fini d'opération sur les langages, la concaténation (La concaténation de "ab" et "cd", c'est "abcd"), l'union (l'union des ensembles {ab} et {cd}, c'est {ab,cd}) et l'étoile ( Dans le dernier cas, le mot est super mal choisi, car ça n'a rien à voir avec une étoile, mais c'est standard, et toujours plus joli que fermeture de Kleene qui n'est pas plus parlant. L'étoile de "ab" c'est l'ensemble des mots de la forme: "", "ab", "abab", ..., "abababababab", ...)

Régulier, ça veut dire que le langage est reconnu par un automate fini. Là ça devient un peu plus complexe à définir. En gros, on a une machine avec un nombre fini d'état - par exemple une machine à écrire aurait les états "minuscule" et "majuscule" - sauf qu'au lieu d'écrire, elle lit les lettre une à une, choisit son nouvel état en fonction de la lettre. À la fin, on regarde l'état final et on a toute l'information qu'on veut.

L est "Reconnaissable" signifie qu'il existe un morphisme f vers un monoïde fini, tel que L est l'inverse de f(L). Là, même en simplifiant, je ne vois pas comment le faire comprendre en français, c'est de l'algèbre.

Le résultat étonnant, c'est que à chaque fois, on peut définir exactement les mêmes langages.


Maintenant, regardons des nombres[1] entiers au lieu de regarder des mots. Un ensemble rationnel peut être définit exactement de la même manière qu'un langage rationnel, sauf qu'on prend l'ensemble qui contient 1 au lieu de celui qui contient une lettre comme brique de base. Les ensembles reconnaissables sont naturellement définit, puisque la définition était déjà purement mathématique, algébrique, à la base.

Mais c'est quoi un ensemble de nombre régulier ? VOILÀ LE PLUS GRAND SUJET DE DISPUTE QUE J'AI VU DANS MON DOMAINE. (Oui, désolé, si vous vous attendiez à des grandes questions éthiques comme chez les médecins, vous devez être déçu.)

Pour certains, la réponse est évidente. Un ensemble régulier, c'est un ensemble définissable dans FO(<,mod) - la logique du premier ordre (First Order) avec la relation d'ordre et les prédicats modulaires. En effet, il est démontré que c'était exactement les ensembles reconnaissable par un automate qui lit des écrite en base 1. (C'est à dire que si vous voulez écrire 24, vous allez écrire 111111111111111111111111). Donc c'est un ensemble reconnu par un automate, et donc Howard Straubing a unilatéralement déclaré qu'on appellerait ces ensembles "régulier". Et il a des fans, j'en connais au moins 2, probablement 3, autour de moi, donc pour eux, la question est déjà réglé.

Sauf que, vous êtes en droit de vous demander, pourquoi lire les nombres en base 1 ? Personne ne veut compter le nombre de 1, l'écriture "24" elle est drôlement plus pratique. C'est ce qu'on appelle l'écriture en base 10, car il y a 10 chiffres possible[2]. Mais, avec des automates en base A, on est capable de définir beaucoup plus d'ensembles d'entiers. En fait tout ceux qui sont définissable dans FO(+,V_A)[3], et il a été dit que ces ensembles seraient appelé A-régulier. Autrement dit, la notation actuelle indique qu'il y a des ensembles qui sont A-régulier, mais qui pourtant ne sont pas régulier, ce qui au niveau des noms est contradictoire.

Enfin, il y a des gens, un peu plus éloigné de mon petit domaine, qui confondent régulier, rationnel et reconnaissable, car ils travaillent sur des langages, et pensent donc qu'un ensemble de nombre est dit régulier s'il est reconnaissable/rationnel. Donc en tout cas que ce nom rend le tout plus confus, et m'ont donc très fortement suggéré d'en trouver un autre.

Et donc voilà, mon plus gros problème en math, mais qui n'est pas un problème que les maths peuvent résoudre, c'est trouver quel noms donner à quels type d'objets mathématique.


Personnellement, je n'écoute par leur avis, et suit la norme déjà utilisé par quelques petites dizaine de mon personne dans mon domaine, au risque d'apporter un peu de confusion aux gens extérieur qui cherchent à savoir ce que je fais. Donc un ensemble de nombre régulier, c'est un ensemble définissable dans FO(<,mod).

Mais là où je deviens méchant, et où certains ont probablement raison de m'en vouloir, c'est qu'un ensemble définissable dans FO(<, mod k), c'est à dire si le seul prédicat modulaire que je m’autorise est k, alors j'appelle ça un ensemble mod k-régulier, puisque c'est un cas particulier d'ensemble régulier. Mais ce genre d'ensemble n'a plus de jolie définition en terme d'automate[4], donc ce nom est presque abusif.


Une anecdote pour finir, je ne sais pas si elle fera rire qui que ce soit. Un travail qui m'a pris plusieurs mois, c'était de décider si un ensemble de nombre reconnu par un automate en base A est définissable dans FO(<,mod), autrement dit si vous suivez, s'il est reconnaissable par un automate en base 1, donc selon la définition que j'utilise, s'il est régulier.

Pour résumer, mon travail a donc été de décider si un ensemble reconnu par un automate est régulier[5]...

Et ça a été le titre de la première présentation que j'ai fait sur le sujet. C'est dire si j'avais l'air sérieux !

Notes

[1] en fait les vecteurs de nombres

[2] en fait, je dirai même un automate en base A

[3] où V_A(n) est la fonction qui rend la plus grande puissance de A qui divise n, par exemple V_10(2400)=100

[4] En fait si, grosso modo, c'est ce qui est reconnu par un automate en base 1 dont la longueur des cycles divise k

[5] Pour rappel, j'ai dit en début de billet que la définition d'un langage régulier, c'est qu'il est reconnu par un automate

Commentaires

1. Le vendredi 7 février 2014, 08:02 par Athreeren

Pourquoi l'étoile n'est-elle pas considérée comme un cas particulier de concaténation ?

Je trouve que l'expression "écriture en base 10" est particulièrement absurde ; je comprends qu'on n'écrive pas écriture en base A (avec A=9+1), mais "écriture en base dix" par exemple n'a pas d'ambigüité (je serais même d'avis d'écrire 24(X) = 30(VIIII))

"La mathématique est l’art de donner le même nom à des choses différentes." (Poincaré)

2. Le vendredi 7 février 2014, 08:08 par Typhon

Tiens ça me rappelle mon cours de grammaire formelle.

Et puis un problème de dénomination, si ça c'est pas un boulot pour un linguiste...

Enfin, en fait non, si je m'en tiens au code d'honneur des linguistes, le seul conseil que je peux te donner c'est "fais comme tu l'entends, de toute façon, ce sera mal".

« Mais, avec des automates en base A, on est capable de définir beaucoup plus d'ensembles d'entiers. »

Pourquoi se limiliter à des entiers, d'ailleurs ? Logiquement, tout nombre ayant une expansion décimale finie doit pouvoir être reconnu par une expression régulière et un automate, non ?

( Ou est-ce que ça revient au même ? )

Typhon

3. Le vendredi 7 février 2014, 15:42 par Arthur Milchior

En fait, on a des automates qui acceptent des mots infinis, et quand on veut passer au réel ou aux rationnels, c'est ce qu'on utilise. J'avoue que je n'ai jamais réfléchi à ce que donneraient ces automates sur les nombres au développement décimale fini. Je regarderai à l'occasion, si c'est pas trop dur.

4. Le dimanche 23 février 2014, 00:09 par LCF, traducteur Math->Français

"L est "Reconnaissable" signifie qu'il existe un morphisme f vers un monoïde fini, tel que L est l'inverse de f(L)."

=>
*S'il existe un groupe de nombres non-infini, avec certaines propriétés, avec les nombres duquel on peut faire une fonction f, et défaire cette fonction pour retrouver le nombre de départ, alors on dit que ce nombre est Reconnaissable.*
J'ai bon?

5. Le dimanche 23 février 2014, 14:26 par Arthur Milchior

Sur le principe tu as grosso modo bon, mais parce que tu es vague.

D'abord, ce n'est pas "un groupe", tout bêtement car "groupe" a une signification mathématique précise (Tous les groupes sont des monoïdes, mais ça restreindrait trop la définition)

Donc un ensemble non-infini (fini quoi), qui n'est pas forcément un ensemble de nombre d'ailleurs, en général c'est juste "un ensemble de truc pas vraiment précis"

Avec des certaines propriétés. Oui, 2 pour être précis. Il existe une fonction x qui prend deux éléments du monoïde, c'est à dire de l'ensemble fini, et qui renvoie un élément. Et il existe un élément du monoide, nommé I, tel que Ix m=m=m x I pour tout élément m.

Enfin et surtout, la fonction doit être tel que f(ab)= f(a) x f(b).  

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

Fil des commentaires de ce billet