Si on a un ensemble $A$ dont les éléments sont dans $P(\mathbb{N})$ et que l’on a la propriété suivante.
Pour tout $ n \in \mathbb{N}$, il existe un élément $x$ de $A$ tels que $\mid x \mid \geq n$, alors est ce qu’on peut dire que $A$ contient un élément de cardinal infini ?
Voilà, je ne sais pas trop comment répondre à cette question, suivant la vision que j’ai de $A$ j’ai l’impression que c’est à la fois oui et non.
$\star$ Oui $\rightarrow$ A chaque fois on a un ensemble plus grand, ça donne "une suite" qui tend vers l’infini et donc il existe un élément de cardinal infini.
$\star$ Non $\rightarrow$ C’est impossible car chaque cardinal est "fixé" dans le sens ou chaque cardinal $\in \mathbb{N}$…
Bref, si on pouvait m’éclaircir sur ces "paradoxes" par rapport à l’infini ça m’aiderait beaucoup !
Si tu prends $A=\{[n],n\in \mathbf{N}\}$ (je note $[n]=\{1, \ldots, n\}$), tous les éléments de $A$ sont des ensembles finis. Je comprends pas trop ton argument pour « oui », pour moi c’est un peu comme si tu disais $\{1/n, n\in\mathbf{N}\}$ contient une suite qui tend vers 0 donc 0 est dans l’ensemble…
Plus simple : est-ce que $\mathbb{N}$ contient un nombre $x$ infini ? Non. Mais on peut prendre un $x$ aussi grand qu’on veut : $\mathbb{N}$ est non borné.
Pareil pour ton $A$ : il ne contient pas forcément d’élément de cardinal infini (mais il pourrait : prend $A = \{\mathbb{N}\}$), mais le cardinal des éléments de $A$ est non borné.
Oui en fait, je viens de me rendre compte que ma question était débile.
En fait c’est parceque dans une solution dans lequel je considère un ensemble infini $A \in \P(\mathbb{N})$ je me demandais si on pouvait ordonner ses éléments, et bref j’étais un peu confus.
La question peut devenir plus interessante si l’on generalise $\mathbb{N}$ par $\mathbb{R}$, l’ensemble des parties par une $\sigma$-algebre (ou tribu en bon francais) quelconque et le cardinal (mesure de comptage) par une mesure quelconque.
De même comment on définit $\max$ sur un ensemble infini ? Et est ce qu’il est possible dans un ensemble infini de supposer que ses éléments sont ordonnés ?
Pour un ensemble fini d’une partie de $A$ je le défini comme le plus grand élément par la relation d’ordre : $ < $ (si on est dans $P(\mathbb{N})$).
Sinon, ok je suis d’accord, c’est facile de définir une relation d’ordre mais tu ne peux pas supposer que l’ensemble lui même est ordonné, car en pratique il est difficile avec la donnée d’une realtion d’ordre et d’un ensemble infini de l’ordonner.
En gros ce que je veux dire c’est que là tu me donnes juste une relation d’ordre mais comment en pratique tu l’ordonnes ?
EDIT : ta relation d’ordre est partielle, elle ne permet pas de comparer $2$ et $3$, donc on est dans le même problème
Pour un ensemble fini d’une partie de $A$ je le défini comme le plus grand élément par la relation d’ordre : $ < $ (si on est dans $P(\mathbb{N})$).
Mais tu définis pas ce que c’est « le plus grand élément », du coup. Avec des quantificateurs : $x$ est le plus grand élément de $A$ ssi $\forall y\in A, y\le x$. Cette définition fonctionne toujours pour un ensemble infini.
Sinon, ok je suis d’accord, c’est facile de définir une relation d’ordre mais tu ne peux pas supposer que l’ensemble lui même est ordonné, car en pratique il est difficile avec la donnée d’une realtion d’ordre et d’un ensemble infini de l’ordonner.
En gros ce que je veux dire =, c’est que là tu me donnes juste une relation d’ordre, mais rien ne me dit qu’elle va me permettre d’ordonner mon ensemble infini.
C’est quoi que t’appelles ordonner un ensemble ? En maths, la relation d’ordre que j’ai citée plus haut munit bien n’importe quel ensemble d’une structure d’ensemble ordonné. Je suppose que tu cherches plutôt une relation d’ordre totale ?
Pour un ensemble fini d’une partie de $A$ je le défini comme le plus grand élément par la relation d’ordre : $ < $ (si on est dans $P(\mathbb{N})$).
Mais tu définis pas ce que c’est « le plus grand élément », du coup. Avec des quantificateurs : $x$ est le plus grand élément de $A$ ssi $\forall y\in A, y\le x$. Cette définition fonctionne toujours pour un ensemble infini.
Ce que je veux dire c’est que :
Si on donne un ensemble $A$ finit, et une relation d’ordre qui n’est pas partielle : "$<"$, alors on est d’accord qu’avec un algorithme il est possible d’ordonner $A$ càd que si un algo prend les éléments de $A$ en entré il donne en sortit les éléments de $A$ triées par $<$.
Dans ce cas là, je peux définir le plus grand élément mais aussi donner sa valeur.
Dans le cas ou $A$ est infini, on peut définir le plus grand élément mais pas le donner.
Ma question est donc :
Est il possible dans une preuve de considérer une ensemble $C$ qui correspond aux élément de $A$ triés, càd que pour tout $a_i, a_j \in C, i <j \Leftrightarrow a_i < a_j$.
C’est quoi que t’appelles ordonner un ensemble ? En maths, la relation d’ordre que j’ai citée plus haut munit bien n’importe quel ensemble d’une structure d’ensemble ordonné. Je suppose que tu cherches plutôt une relation d’ordre totale ?
Ce que j’appelle ordonner c’est trié. Ta relation est partielle, et donc donc donne un ordre qui n’est que partielle, et donc il est impossible de trier $A$ dans ce cas.
De même comment on définit $\max$ sur un ensemble infini ? Et est ce qu’il est possible dans un ensemble infini de supposer que ses éléments sont ordonnés ?
De même comment on définit $\max$ sur un ensemble infini ? Et est ce qu’il est possible dans un ensemble infini de supposer que ses éléments sont ordonnés ?
Ce que j’appelle ordonner c’est trié. Ta relation est partielle, et donc donc donne un ordre qui n’est que partielle, et donc il est impossible de trier $A$ dans ce cas.
C’est bien ce que je disais du coup : tu cherches une relation d’ordre totale (autrement dit, on demande à ce que pour tout $x, y$, on ait $x\le y$ ou $y\le x$). C’est la CNS pour que la notion classique d’algorithme de tri ait un sens (sur une entrée finie, entendons-nous…). Est-ce qu’on est d’accord avec ça ?
La question « est-ce que tout ensemble admet une relation d’ordre totale » est déjà plus subtile. On entre dans les bidouilles de logicien qui risquent de rendre plus complexes tes histoires d’algorithme sur des machins infinis (voir par exemple ici, en gros la réponse est oui avec l’axiome du choix).
Ce que je veux dire c’est que :
Si on donne un ensemble $A$ finit, et une relation d’ordre qui n’est pas partielle : "$<"$, alors on est d’accord qu’avec un algorithme il est possible d’ordonner $A$ càd que si un algo prend les éléments de $A$ en entré il donne en sortit les éléments de $A$ triées par $<$.
Je suis d’accord (tu veux dire totale plutôt que « non partielle »).
Dans ce cas là, je peux définir le plus grand élément mais aussi donner sa valeur.
J’ai du mal à donner du sens à cette phrase.
Dans le cas ou $A$ est infini, on peut définir le plus grand élément mais pas le donner.
Ma question est donc :
Est il possible dans une preuve de considérer une ensemble $C$ qui correspond aux élément de $A$ triés, càd que pour tout $a_i, a_j \in C, i <j \Leftrightarrow a_i < a_j$.
Là je ne te suis plus. Ça serait quoi $C$ ? Il faut que t’aies une relation d’ordre dessus.
Je pense que tu essaies de te rattacher à des concepts qui n’existent pas vraiment en maths (ou alors il faut être plus précis), en faisant une différence entre des trucs définis « implicitement » et « explicitement ».
C’est bien ce que je disais du coup : tu cherches une relation d’ordre totale (autrement dit, on demande à ce que pour tout $x, y$, on ait $x\le y$ ou $y\le x$). C’est la CNS pour que la notion classique d’algorithme de tri ait un sens (sur une entrée finie, entendons-nous…). Est-ce qu’on est d’accord avec ça ?
Totalement.
La question « est-ce que tout ensemble admet une relation d’ordre totale » est déjà plus subtile. On entre dans les bidouilles de logicien qui risquent de rendre plus complexes tes histoires d’algorithme sur des machins infinis (voir par exemple ici, en gros la réponse est oui avec l’axiome du choix).
C’est intéressant, merci pour le lien.
Bon je recommence depuis le début en essayant d’être clair.
Si on nous donne un ensemble $A$, et une relation d’ordre totale sur $A$, alors on a deux cas :
$\star$ Si $\mid A \mid $ est finit, alors je peux trier les éléments de $A$, dans le sens ou je peux donner un nouvelle ensemble $C$ dans lequel les élément de $C$ ne sont plus dans le désordre.
En gros on a une fonction de trie : $T_{<}: E \rightarrow C$, ou $C$ est l’élément de $E$ trié. Remarquons que $T$ est idempotente : $T_{<} \circ T_{<} = Id$.
Par exemple supposons qu’on nous donne un ensemble : $A = \{w, z, s\}$ et une relation d’ordre $<$ sur cet ensemble $A$ tels que : $z < w$, $s < w$, $z < s$. Alors on a : $T_{<} (\{w, z, s\}) = \{z, s , w\}$, et donc : $T_{<} (\{z, s, w\}) = \{z, s, w\}$.
Il est alors facile de définir $T_{<}$, n’importe quel algorithme de trie fait l’affaire, et on sait que cet algorithme donnera toujours un résultat au bout d’un temps finit car $\mid A \mid $ est finit.
$\star$ Si $\mid A \mid = \infty$, là j’ai un problème. Supposons pour l’exemple que j’ai un $A \subseteq \mathbb{N}$ infini, alors ma question est peut on numéroter ses élément de sorte que : $a_1 < a_2 < ... < a_i < ...$ ?
En pratique, il est impossible de le faire, et c’est ça qui me pose problème. Il est impossible de bien définir $T_{<}$ dans ce cas ?
Si on nous dit : c’est bon voilà j’ai trié $A$, et le nouvel ensemble trié est $C$, on ne pourra jamais savoir si $C$ est effectivement bien trié.
Et j’ai le même problème pour $\max$, rien nous dit que c’est bien le maximum ou encore que l’ensemble admet un maximum.
Ici, je parle bien sûr du cas général, je sais bien que $[0, 1]$ a pour maximum $1$, mais en quoi "dans tous les cas" on peut bien définir le maximum.
Voilà j’espère que mon problème est plus clair.
EDIT : c’est pour ça qu’à part en construisant l’ensemble élément par élément, cela me paraît compliquer
Question simple : qu’est-ce que tu penses de $\mathbf{R}$ ? Est-ce que tu peux lui appliquer ta notion de tri ?
Un peu plus en détail :
Si on nous donne un ensemble $A$, et une relation d’ordre totale sur $A$, alors on a deux cas :
$\star$ Si $\mid A \mid $ est finit, alors je peux trier les éléments de $A$, dans le sens ou je peux donner un nouvelle ensemble $C$ dans lequel les élément de $C$ ne sont plus dans le désordre.
En gros on a une fonction de trie : $T_{<}: E \rightarrow C$, ou $C$ est l’élément de $E$ trié. Remarquons que $T$ est idempotente : $T_{<} \circ T_{<} = Id$.
Par exemple supposons qu’on nous donne un ensemble : $A = \{w, z, s\}$ et une relation d’ordre $<$ sur cet ensemble $A$ tels que : $z < w$, $s < w$, $z < s$. Alors on a : $T_{<} (\{w, z, s\}) = \{z, s , w\}$, et donc : $T_{<} (\{z, s, w\}) = \{z, s, w\}$.
Je suis pas d’accord avec cette définition du tri. Le problème essentiel dans ta formalisation c’est qu’il n’y a pas de notion d’ordre au sein d’un ensemble : on a $\{w,z,s\}=\{z,s,w\}$, ce sont vraiment les mêmes objets (et c’est justement le coeur du problème : là tu supposes en quelque sorte que tu disposes d’une relation d’ordre naturelle sur ton ensemble).
Je m’essaie à une meilleure formulation. On prend un ensemble $A$ fini de cardinal $n$. La notion correspondante à ce que tu cherches à faire avec tes ensembles ordonnés, c’est celle de $n$-uplet (que tu peux définir avec les bidouilles de $\{a, \{a, b\}\}$ ou, plus parlant, comme une application de $[n]$ dans $A$ — mais dans les deux cas, tu as besoin de $\mathbf{N}$ plus ou moins caché). À l’ensemble $A$ je vais donc associer un $n$-uplet (un élément de $A^n$, donc) $(a_1, \ldots, a_n)$ tels que $a_i< a_{i+1}$.
Pour un ensemble infini dénombrable, on peut éventuellement généraliser ce qu’on a fait en remplaçant $A^n$ par $A^\mathbf{N}$ (est-ce que c’est bien ce qu’on entend naturellement par tri ?). Maintenant dans le cas le plus général c’est moins clair… C’est pour ça que je pose la question avec $\mathbf{R}$, est-ce que la notion de tri d’un ensemble infini non dénombrable a une réalité dans ta tête ?
$A \subseteq \mathbb{N}$ infini, alors ma question est peut on numéroter ses élément de sorte que : $a_1 < a_2 < ... < a_i < ...$ ?
(Cette numérotation suppose que l’ensemble est dénombrable. C’est effectivement le cas pour une partie de $\mathbf{N}$, mais je précise.)
On va construire $a$ par récurrence. Je vais me servir de la propriété (P) suivante : toute partie non vide de $\mathbf{N}$ admet un plus petit élément (pour prouver ça… ça dépend de comment tu construis $\mathbf{N}$, en tout cas c’est très axiomatique).
$n = 1$ : on applique (P) à $A$, on pose $a_1$ le plus petit élément.
Supposons qu’on a construit $a_1, \ldots, a_n$. On applique (P) à $A\setminus \{a_1, \ldots, a_n\}$ (toujours infinie donc non vide). On pose $a_{n+1}$ le plus petit élément.
Et voilà ! On a construit l’objet $a$.
En pratique, il est impossible de le faire, et c’est ça qui me pose problème. Il est impossible de bien définir $T_{<}$ dans ce cas ?
Si on nous dit : c’est bon voilà j’ai trié $A$, et le nouvel ensemble trié est $C$, on ne pourra jamais savoir si $C$ est effectivement bien trié.
Je reformule ce que j’ai dit plus haut : il te faut définir une autre structure que celle d’ensemble. Si $A$ et $C$ ont les mêmes éléments, alors ce sont les mêmes ensembles.
Et j’ai le même problème pour $\max$, rien nous dit que c’est bien le maximum ou encore que l’ensemble admet un maximum.
Effectivement, un ensemble n’admet pas forcément un plus grand élément (genre $\mathbf{N}$ ou $[0,1[$, mais je ne t’apprends rien !). Par contre ta phrase « j’ai le même problème pour $\max$, rien nous dit que c’est bien le maximum », c’est vraiment pas clair.
ÉDIT : Une dernière chose… Tu parles d’algorithme, pour moi un algorithme ça travaille sur des données de type $\{0,1\}^{(\mathbf{N})}$. Tu peux sans doute définir des machines de Turing sur un alphabet exotique, mais potentiellement ça peut être contre-intuitif.
Ici, je parle bien sûr du cas général, je sais bien que [0,1] a pour maximum 1, mais en quoi "dans tous les cas" on peut bien définir le maximum.
On ne peut pas dans tous les cas. C’est quoi le maximum de $\mathbb{N}$ ?
Parfois, comme dans $[0; 1[$, on peut avoir une borne supérieure (ici, $1$) : c’est le plus petit des majorants, c’est-à-dire le plus petit des éléments qui sont plus grands que tous les éléments de l’ensemble. Quand en plus la borne supérieure appartient à l’ensemble en question, on dit que c’est le maximum de l’ensemble. Quand il n’y a pas de borne supérieure (notamment parce qu’il n’y a pas de majorant), a fortiori, il n’y a pas de maximum.
Question simple : qu’est-ce que tu penses de $\mathbf{R}$ ? Est-ce que tu peux lui appliquer ta notion de tri ?
En fait ce qui m’embête dans les exemples avec des ensembles comme : $\mathbb{N}$, $\mathbb{R}$ c’est que ce sont des ensembles qu’on a construit élément par élément, et donc pour moi ils sont déjà triés par $<$.
Je suis pas d’accord avec cette définition du tri. Le problème essentiel dans ta formalisation c’est qu’il n’y a pas de notion d’ordre au sein d’un ensemble : on a $\{w,z,s\}=\{z,s,w\}$, ce sont vraiment les mêmes objets (et c’est justement le coeur du problème : là tu supposes en quelque sorte que tu disposes d’une relation d’ordre naturelle sur ton ensemble).
Je m’essaie à une meilleure formulation. On prend un ensemble $A$ fini de cardinal $n$. La notion correspondante à ce que tu cherches à faire avec tes ensembles ordonnés, c’est celle de $n$-uplet (que tu peux définir avec les bidouilles de $\{a, \{a, b\}\}$ ou, plus parlant, comme une application de $[n]$ dans $A$ — mais dans les deux cas, tu as besoin de $\mathbf{N}$ plus ou moins caché). À l’ensemble $A$ je vais donc associer un $n$-uplet (un élément de $A^n$, donc) $(a_1, \ldots, a_n)$ tels que $a_i< a_{i+1}$.
Yep, je suis d’accord.
On va construire $a$ par récurrence. Je vais me servir de la propriété (P) suivante : toute partie non vide de $\mathbf{N}$ admet un plus petit élément (pour prouver ça… ça dépend de comment tu construis $\mathbf{N}$, en tout cas c’est très axiomatique).
$n = 1$ : on applique (P) à $A$, on pose $a_1$ le plus petit élément.
Supposons qu’on a construit $a_1, \ldots, a_n$. On applique (P) à $A\setminus \{a_1, \ldots, a_n\}$ (toujours infinie donc non vide). On pose $a_{n+1}$ le plus petit élément.
Et voilà ! On a construit l’objet $a$.
En fait là ce qui m’embête, c’est que pour le construire ça suppose la connaissance de $a_1$. Donc pour moi, je ne vois pas comment l’initialisation peut marcher.
Puisque $A$ est infini, tu ne peux pas trouver $a_1$ ou du moins t’assurer que c’est bien lui qui respecte la propriété : d’être le plus petit élément de $A$. Et c’est ce problème qui me gêne depuis le début, et qui me donne l’impression que trier un ensemble infini est "difficile" à définir.
Prenons un exemple en dehors des maths. Si quelqu’un affirme : "je suis éternelle", vas tu le croire ? Personnellement non, puisqu’il ne pourra jamais le prouver…
Ainsi on pose des choses, qui ne sont pas nécessairement vraie comme le fait d’être le plus petit, ou le plus grand élément d’un ensemble infini par une relation d’ordre totale $<$.
Effectivement, un ensemble n’admet pas forcément un plus grand élément (genre $\mathbf{N}$ ou $[0,1[$, mais je ne t’apprends rien !). Par contre ta phrase « j’ai le même problème pour $\max$, rien nous dit que c’est bien le maximum », c’est vraiment pas clair.
Oui ce que j’ai dit n’était pas très rigoureux.
En fait, pour $\max$, c’est pareil que ce que j’explique juste au dessus.
Donc en gros ce que je veux dire, c’est que pour trier (restons ici dans le cas d’un ensemble en bijection avec $\mathbb{N}$) càd numéroter ses élément tels que $a_1 < ... <a_i < ...$, alors cela suppose de connaître $a_1$, mais rien ne peut nous assurer que $a_1$ est bien le plus petit élément, puisque pour s’en assurer il faudrait comparer $a_1$ avec tous les éléments mais dans ce cas là c’est impossible d’arriver à une conclusion puisque $A$ est infini.
Connaître l’existence ne nous indique pas quel élément c’est.
Tu as une vision des maths trop algorithmique, je crois. On manipule souvent des objets qu’on ne peut pas construire, ou manipuler en temps fini. On prouve même des choses dessus. En fait, je pense qu’il y a des choses profondes derrière certaines de tes questions, le « pourquoi historiquement on choisit de gérer les ensembles infinis de cette manière ? », mais honnêtement je suis pas du tout logicien de formation, je peux pas vraiment développer autour.
Bon j’ai l’impression que tout tourne autour de ce « on ne peut pas trouver $a_1$ ». Quelques remarques :
(1) Le premier truc que je pourrais te répondre, mais ça serait pas très intéressant : « c’est comme ça qu’on a choisi de faire les choses en maths, point ». Au fond c’est un peu la bonne réponse, parce qu’on a décrété (prenons même ça pour un axiome inviolable de la vie) : toute partie non vide de $\mathbf{N}$ admet un plus petit élément. Cet élément existe, je lui donne un nom. Même sur un ensemble concret, peut-être je ne connais rien d’autre sur cet élément, sinon son existence. Si tu me demandes : « mais pourquoi c’est le plus petit élément ? », ma réponse sera : « par construction, c’est l’élément que j’ai choisi de considérer ». Je n’ai pas à vérifier que pour tout $y\in A$, on a bien $x\le y$, par que c’est tout simplement automatique.
(2) Pourquoi est-ce que tu ne te poses pas des questions similaires avec $\mathbf{N}$ ou $\mathbf{R}$ ? Honnêtement même sous la perspective « philosophique », je ne vois vraiment pas ce que pourrait vouloir dire « on a construit $\mathbf{R}$ élément par élément ». À la limite, je trouverais même ça plutôt faux (d’une certaine manière — hop hop dénombrabilité toussa toussa — on ne peut pas énumérer $\mathbf{R}$ élément par élément justement… ou sinon par où tu commences ?).
(3) Au fond, pourquoi est-ce que le fait de vérifier une infinité de relations te dérange ? Quand tu montres $\forall x\in[0,1],x\le 2$, est-ce que pour me convaincre tu devrais pas aussi m’écrire sur une feuille : $0\le 2$, $0.1\le 2$, $0.01\le 2$, etc. une infinité de fois ? (le etc. étant évidemment une vaste blague… cf. plus haut).
(4) À la limite, ce que tu racontes, ça me paraît plus proche de la notion de preuve (ou certificat) en complexité/crypto. A et B communiquent sur Twitter, A veut montrer à B qu’il sait quelque chose, il lui envoie une preuve qui tient en 140 caractères (en informatique, on espère que le certificat soit de taille polynomiale en la taille de l’instance). En maths, avec la théorie des ensembles classiques, parfois on fait une infinité de vérifications en une étape de preuve, et ça ne gêne personne (enfin, en soi ça a dû gêner pas mal de gens avant le XIXème… mais si on veut faire des trucs un peu compliqués…).
Prenons un exemple en dehors des maths. Si quelqu’un affirme : "je suis éternelle", vas tu le croire ? Personnellement non, puisqu’il ne pourra jamais le prouver…
Bah s’il prouve par l’absurde qu’il ne peux pas mourir … moi ça me va.
En fait ce qui m’embête dans les exemples avec des ensembles comme : $\mathbb{N}$, $\mathbb{R}$ c’est que ce sont des ensembles qu’on a construit élément par élément, et donc pour moi ils sont déjà triés par $<$.
Je sais pas quelle construction tu as en tête, mais $\mathbf R$ n’est pas vraiment construit élément après élément … après tout il y a bien des nombres réels qu’on ne sait pas calculer (et même la plupart d’entre eux sont comme ça)
Bon, merci pour vos réponses. Je pense qu’effectivement ma vision des choses était trop algorithmique.
Pour $\mathbb{R}$, en fait je dois avouer que je n’avais pas trop de constructions en tête :D.
Pour $\mathbb{N}$, par contre c’est vraiment élément par élément et on le construit "en y mettant un ordre" dans le sens ou dans la construction même de $\mathbb{N}$ il y la notion de précèdent, devance…
ÉDIT : Une dernière chose… Tu parles d’algorithme, pour moi un algorithme ça travaille sur des données de type $\{0,1\}^{(\mathbf{N})}$. Tu peux sans doute définir des machines de Turing sur un alphabet exotique, mais potentiellement ça peut être contre-intuitif.
C’est marrant ce que tu dis, parceque pour moi quand on travaille sur $\{0, 1\}^{\mathbb{N}}$ c’est vraiment un cas particulier (c’est à dire ceux avec quoi les ordis travaillent aujourd’hui). Dans le sens ou tous les cours théoriques que j’ai lu sur les automates, on considère toujours un langage quelconque et je trouve pas que considérer un langage plutôt qu’un autre aide à la compréhension, dans le sens ou si on voit juste un caractère comme une transition entre des états alors finalement "le langage n’a pas tant d’importance que ça". C’est un peu comme en théorie des groupes (ici plus comme des mouvements géométriques), si on considère un langage comme un monoïde, et en voyant les éléments du monoïde comme des transitions d’états finalement le langage a peu d’importance. (bon après je suis loin d’être un grand expert du sujet).
C’est marrant ce que tu dis, parceque pour moi quand on travaille sur $\{0, 1\}^{\mathbb{N}}$ c’est vraiment un cas particulier (c’est à dire ceux avec quoi les ordis travaillent aujourd’hui). Dans le sens ou tous les cours théoriques que j’ai lu sur les automates, on considère toujours un langage quelconque et je trouve pas que considérer un langage plutôt qu’un autre aide à la compréhension, dans le sens ou si on voit juste un caractère comme une transition entre des états alors finalement "le langage n’a pas tant d’importance que ça". C’est un peu comme en théorie des groupes (ici plus comme des mouvements géométriques), si on considère un langage comme un monoïde, et en voyant les éléments du monoïde comme des transitions d’états finalement le langage a peu d’importance. (bon après je suis loin d’être un grand expert du sujet).
Non non tu as raison, tant qu’on reste sur le point de vue « calculabilité » (monoïdes toussa toussa), changer l’alphabet ne fait pas grand chose ; de toute façon, on peut toujours trouver une bijection entre l’alphabet (fini !) et une partie d’un $\{0,1\}^s$ pour $s$ suffisamment grand, et modulo quelques difficultés techniques, on peut bidouiller la machine de Turing pour qu’elle fonctionne de manière identique dans les deux cas.
Par contre quand on prend le point de vue « complexité », ça peut changer ce qu’on considère comme étant une étape de calcul (bon et là on peut sûrement construire des trucs bizarres).
Connectez-vous pour pouvoir poster un message.
Connexion
Pas encore membre ?
Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte
