Nora prépare une feuille de décisions pour une activité fictive de cartes. Trois renseignements sont déjà fixés, mais Camille ne les lit pas nécessairement tous. Chacun vaut zéro ou un. La feuille doit remettre une réponse finale, zéro ou un, sans changer ces renseignements pendant la lecture. Nora veut diminuer le nombre de cases différentes conservées dans son dessin, et Camille veut savoir combien de tests elle parcourt réellement. Ces deux commandes peuvent aboutir à des comptes distincts.
Portage présente des carnets.
Odd Giraffe présente des carnets.
Write Notepads & Co. présente des carnets.
Ces catégories situent les feuilles ; aucun carnet, dessin ou procédé réel n'est adapté. Renseignements, branches et réponses sont stipulés, sans mesure informatique ou matérielle examinée.
La règle initiale utilise trois bits x, y et z : si x vaut zéro, la réponse est y ; si x vaut un, elle est z. Chaque case interne teste un seul bit et possède deux flèches, pour zéro et pour un. Les deux cases finales zéro et un sont distinctes. Sur un chemin, les tests suivent un ordre de variables choisi à l'avance, éventuellement en sautant des variables inutiles. Les flèches ne renversent pas la réponse, sauf dans une branche séparée qui autorisera explicitement cette opération. Cette représentation classique de décision ordonnée n'est pas donnée comme une invention.
Lire le sélecteur en premier donne trois cases internes
Nora place x au départ. Sa flèche zéro conduit à une case y, avec zéro vers la fin zéro et un vers la fin un. Sa flèche un conduit à une case z, également reliée aux deux fins suivant sa valeur. Le dessin possède trois cases internes : x, y et z. Dans une réalisation x zéro, y un, z zéro, Camille lit x puis y et remet un. Elle ne consulte pas z. Pour x un avec les mêmes y et z, elle lit x puis z et remet zéro. Les deux chemins utilisent le renseignement sélectionné par x, sans combiner les réponses d'y et de z.
Camille avait relié les deux flèches d'x à la seule case y, parce que les cases y et z semblaient avoir les mêmes deux fins. Nora refuse cette fusion. Pour x un, y un, z zéro, la nouvelle feuille remettrait un au lieu du zéro demandé. Les cases testent des renseignements différents, même lorsqu'elles envoient leurs deux valeurs vers les mêmes fins. L'identité de la variable appartient donc à la case, autant que ses deux sorties. Nora conserve trois cases et le nom testé dans chacune, au lieu de fusionner seulement depuis l'allure des flèches.
Une copie supplémentaire de la case y, testant réellement y avec les mêmes sorties ordonnées, peut en revanche être remplacée par la case y déjà conservée. Si une branche avait ajouté une case qui teste z mais envoie zéro et un vers cette même case y, le test z peut aussi être supprimé sur cette branche : quelle que soit sa valeur, la suite de la lecture est identique. Nora applique ces deux gestes distincts, fusion de copies identiques et suppression d'un test sans effet. Elle ne les applique ni aux cases y et z différentes, ni à une case dont les deux flèches mènent aux fins opposées.
Le même résultat demandé peut nécessiter cinq cases sous un autre ordre
Camille impose maintenant y avant z avant x. Nora ouvre la feuille par y. Après y zéro, la règle restante est « x et z » : si z vaut zéro, la réponse est déjà zéro ; si z vaut un, il faut encore lire x. Après y un, la règle restante est « z ou non x » : si z vaut un, la réponse est déjà un ; si z vaut zéro, il faut encore lire le contraire d'x. Les deux branches d'y doivent donc garder deux cases z différentes. Elles n'ont pas les mêmes sorties ni le même renseignement encore à départager.
Pour la branche y zéro, z un, Nora utilise une case x dont zéro mène à zéro et un à un. Pour y un, z zéro, elle utilise une autre case x, dont zéro mène à un et un à zéro. Le dessin contient une case y, deux cases z et deux cases x, soit cinq cases internes. Dans la réalisation y un, z zéro, x zéro, Camille parcourt la seconde case z puis la case qui renverse x, et remet un. Dans y zéro, z un, x zéro, elle parcourt l'autre z puis l'autre x, et remet zéro. Les deux cases x portent la même variable, mais leurs flèches ordonnées sont inversées.
Nora refuse de partager ces deux cases x sans conserver ce renversement. Si elle garde seulement la case x qui remet x, la réalisation y un, z zéro, x zéro finit sur zéro alors que la règle remet y, donc un. Une même paire de fins ne suffit pas : l'une des cases possède zéro vers zéro et un vers un, l'autre zéro vers un et un vers zéro. Camille conserve les cinq cases sous la permission initiale de flèches ordinaires. Elle peut ensuite décider de revenir à l'ordre x, y, z pour obtenir trois cases, mais elle ne déclare pas avoir réduit cinq à trois en oubliant deux comportements différents.
Dans ce second ordre, si y et z sont tous deux zéro, les deux valeurs possibles d'x remettraient zéro ; si y et z sont tous deux un, elles remettraient un. Nora s'arrête donc après y et z dans ces réalisations. Lorsque y et z diffèrent, elle lit aussi x. La feuille peut ainsi utiliser deux ou trois tests sur un chemin, alors que le premier ordre utilisait toujours x puis un seul renseignement, deux tests. Ce contrôle est une lecture de chemins réels du petit modèle, sans lui attribuer une vitesse mesurée ou une fréquence de renseignements dans une activité réelle.
Le partage dépend de la fonction encore à lire, pas du chemin déjà parcouru
Nora définit une suite de décisions par ce qu'elle répond pour chaque affectation des variables encore libres. Deux chemins antérieurs peuvent partager une même case si la suite restante est exactement la même fonction. La valeur d'un renseignement déjà lu ne doit pas réapparaître comme une donnée secrète dans cette suite. Si les deux chemins demandent de remettre y pour toutes les valeurs encore possibles, ils peuvent rejoindre la même case y ; si l'un demande y et l'autre z, l'affectation y un, z zéro les distingue immédiatement. Nora utilise donc une comparaison de toutes les réponses restantes, et non une comparaison des seules réponses de la réalisation reçue.
Pour un ordre fixé, cette comparaison permet une construction récursive. Une fonction constante conduit directement à la fin zéro ou un. Sinon, sa première variable encore utile dans cet ordre partage la fonction en deux suites, en fixant cette variable à zéro puis à un. Si les deux suites sont identiques, le test n'était pas utile et est supprimé. Si elles diffèrent, la case conserve cette variable et ces deux suites dans cet ordre. Les suites sont réduites de la même manière, puis les cases ayant le même triplet variable, suite zéro, suite un sont partagées. Nora ne laisse pas une variable plus tardive passer avant une variable utile antérieure dans cette construction.
Cette description donne une raison à l'unicité du résultat réduit sous l'ordre choisi. Les deux fonctions constantes ont leurs fins imposées. Pour une fonction non constante, sa première variable utile est déterminée par l'ordre, et les deux restrictions à zéro et à un sont déterminées par la fonction elle-même. En poursuivant sur moins de variables, leurs représentations réduites sont déterminées également. La case du départ et ses deux suites sont donc fixées, jusqu'aux noms de cases que Nora peut renuméroter. Elle ne doit pas conserver deux copies de ce même triplet pour deux chemins différents. Cette justification générale explique la réduction ; elle ne donne pas une même forme sous des ordres différents.
Camille reçoit la feuille à trois cases et celle à cinq cases. Elles ne possèdent pas le même départ, x et y, mais les huit affectations de x, y et z donnent les mêmes réponses finales. Nora ne prend donc pas la différence de leurs cases de départ comme une preuve que leurs règles diffèrent. Elle choisit un même ordre pour une comparaison par représentation réduite, ou vérifie directement les huit affectations du petit cas. La promesse d'une forme unique était attachée à un ordre commun et aux permissions de flèches annoncées, pas à tous les dessins qui peuvent calculer une même règle.
Comparer deux mots peut multiplier les suites encore distinctes
Une autre branche de la feuille reçoit deux mots binaires de trois positions : a1, a2, a3 et b1, b2, b3. La réponse vaut un exactement si les trois positions correspondantes sont égales. Nora compare d'abord chaque paire avant de passer à la suivante : a1, b1, puis a2, b2, puis a3, b3. Après a1 zéro, la case b1 envoie zéro vers la suite de comparaison suivante et un vers la fin zéro. Après a1 un, une autre case b1 envoie un vers cette même suite et zéro vers la fin zéro. Les deux chemins où la première paire correspond rejoignent donc exactement la même suite pour les deux positions restantes.
La construction recommence pour a2, b2 puis a3, b3. Chaque paire demande une case pour son a et deux cases pour son b, qui doivent tester l'égalité à zéro ou à un selon le a lu. Les suites de réussite sont partagées. Le dessin possède neuf cases internes, trois par position. Camille lit par exemple a égale zéro, un, zéro et b égale zéro, zéro, zéro. La première paire correspond, la seconde ne correspond pas : elle remet zéro après a1, b1, a2 et b2, sans lire les deux dernières positions. Le partage a gardé une suite de comparaison indépendante du nom du chemin qui y arrive.
Camille impose ensuite l'ordre a1, a2, a3, b1, b2, b3. Après avoir lu les trois a, la feuille doit comparer b au mot a effectivement reçu. Les huit mots a possibles demandent huit fonctions différentes sur b : chacune répond un sur son seul mot correspondant et zéro sur les sept autres. Aucun des huit mots a ne peut donc rejoindre la même suite que celui qui en diffère, même si une réalisation particulière de b leur donnerait à tous deux zéro. Nora garde huit suites distinctes à ce niveau. La lecture de tous les a d'abord a créé précisément l'information de référence que les tests b suivants devront distinguer.
Avant ces suites, les tests a forment un arbre complet de sept cases : une pour a1, deux pour a2 et quatre pour a3. Au niveau b1, il faut huit cases différentes ; au niveau b2, seules les quatre queues de deux positions restent à distinguer ; au niveau b3, seulement les deux queues d'une position. Les anciennes têtes déjà vérifiées ne doivent plus modifier cette dernière comparaison. Nora partage donc les fins de suites identiques et obtient quatorze cases b, huit plus quatre plus deux. Avec les sept cases a, le dessin réduit conserve vingt et une cases internes, contre neuf dans l'ordre entrelacé. Camille choisit ce dernier pour sa commande de diminuer les cases conservées.
Le phénomène persiste si les mots s'allongent. Pour n positions, l'ordre entrelacé conserve trois n cases par cette construction. Après toutes les n positions a dans l'ordre groupé, les deux à la puissance n références possibles imposent déjà autant de suites différentes sur b. Pour deux références distinctes, prendre b égal à la première donne un dans sa suite et zéro dans l'autre : c'est un témoin concret de leur différence. Nora peut donc prouver ce nombre de suites nécessaires sans connaître l'affectation effectivement reçue. La multiplication ne vient pas d'un refus de partager les suffixes ; elle subsiste après tous les partages autorisés, parce que les fonctions restantes ne sont pas égales.
Moins de cases conservées ne supprime pas toutes les lectures d'un chemin
Pour les deux mots égaux zéro, un, zéro, les deux ordres lisent les six bits. Dans l'ordre entrelacé, Camille compare successivement les trois paires ; dans l'ordre groupé, elle lit d'abord a puis contrôle les trois b. Les neuf cases du premier dessin et les vingt et une du second ne sont donc pas deux nombres de tests parcourus pour cette réalisation. Nora garde six dans les deux traces. Elle ne prétend pas que réduire le dessin à neuf cases donne neuf questions par lecture, ni qu'un dessin de vingt et une cases impose de les visiter toutes avant d'atteindre une fin.
Si la première paire diffère, l'ordre entrelacé peut remettre zéro après deux tests. L'ordre groupé doit encore avoir lu les trois a avant son premier b, quatre tests dans ce modèle où cet ordre est imposé. Nora donne comme témoin a zéro, un, zéro et b un, un, zéro : la différence de a1 et b1 suffit à la réponse, mais elle est lue à des instants différents. Le choix d'ordre peut ainsi affecter le chemin comme la taille conservée, sans que ces deux différences aient le même compte. Camille retient la réduction des cases et joint séparément les chemins des réalisations remises.
Autoriser une flèche qui renverse la fin change la représentation
Nora ouvre une permission nouvelle sur la règle initiale à trois bits. Une flèche peut maintenant porter une marque qui remplace la fin zéro par un et la fin un par zéro après la lecture de sa suite. Dans le dessin d'ordre y, z, x, elle conserve une seule case x ordinaire. La branche y zéro, z un la rejoint sans marque ; la branche y un, z zéro la rejoint avec la marque de renversement. Les deux anciennes cases x sont ainsi remplacées par une case et deux types de flèches. Le dessin a quatre cases internes au lieu de cinq sous cette permission élargie.
Camille vérifie la réalisation y un, z zéro, x zéro. La case x remet provisoirement zéro, puis la marque renverse cette fin en un, la bonne réponse de la règle. Pour y zéro, z un, x zéro, le même x remet zéro sans renversement. Nora conserve la marque dans la trace de chacune de ces deux entrées. En l'effaçant après le partage, elle reproduirait la mauvaise fusion déjà refusée. La réduction d'une case a donc été achetée par une information nouvelle portée sur une flèche ; elle ne prouve pas que les cinq cases étaient réductibles sous les anciennes permissions de flèches ordinaires.
Cette marque ne permet pas de fusionner au hasard toutes les suites qui donnent parfois des réponses opposées. Il faut qu'elles soient complémentaires pour chaque affectation restante. Les deux restrictions d'x de la première règle sont y et z, qui ne sont pas complémentaires : pour y et z tous deux zéro, elles donnent toutes deux zéro. Nora ne remplace donc pas les deux cases y et z du premier dessin par une seule case munie d'une marque de renversement. Elle garde la fusion justifiée des suites x et non x, sans transformer la nouvelle permission en une exemption de leur comparaison complète.
Faire disparaître un renseignement peut vouloir dire deux commandes différentes
Camille ne veut plus fixer x dans la première règle. Elle demande d'abord si une valeur possible d'x pourrait donner la fin un. Pour y zéro, z un, choisir x un suffit ; pour y un, z zéro, choisir x zéro suffit. Pour y et z tous deux zéro, aucun choix ne convient. La nouvelle réponse est donc y ou z. Nora prépare cette feuille à deux renseignements en réunissant les deux possibilités d'x par cette opération, au lieu de supprimer simplement la case x et de conserver sa flèche zéro. Cette suppression arbitraire aurait donné seulement y et aurait répondu zéro dans le premier témoin où z seul permettait un.
Une autre commande exige que la fin soit un pour toutes les valeurs d'x. Pour y zéro, z un, la valeur x zéro donne zéro ; pour y un, z zéro, la valeur x un donne zéro également. Ces deux cas doivent donc être refusés dans cette seconde commande. Seuls y et z tous deux un garantissent la fin un, quelle que soit la sélection : la nouvelle règle est y et z. Nora conserve les deux feuilles, possibilité d'une sélection favorable et garantie pour toute sélection, avec leurs réponses effectivement différentes. Elles ne sont pas deux versions renommées d'une variable devenue inutile ; elles appliquent deux opérations distinctes aux suites de la case supprimée.
Compter les formulaires admis doit rendre leur place aux variables sautées
Camille reçoit ensuite une commande de comptage : combien des huit affectations de x, y et z remettent un ? Dans l'ordre x en premier, le chemin x zéro, y un accepte les deux valeurs de z ; le chemin x un, z un accepte les deux valeurs d'y. Ces chemins sont disjoints par x, donc quatre formulaires sont admis. Compter seulement les deux chemins aurait oublié leurs deux renseignements non lus ; compter seulement la case finale un partagée aurait donné un. Nora joint à chaque arrivée dans cette fin le nombre d'affectations des variables sautées, plutôt qu'un nouveau nom de fin pour chaque formulaire. Dans l'ordre y, z, x, les deux chemins qui consultent x et réussissent comptent chacun un formulaire ; le chemin y un, z un atteint la fin sans x et en compte deux. Elle retrouve quatre malgré les trois chemins différents de ce second dessin.
Nora applique le même principe aux deux mots de trois bits. Chaque mot a possède un seul b qui lui correspond ; huit des soixante-quatre affectations complètes sont donc acceptées. Dans l'ordre entrelacé, après une paire correspondante, les deux possibilités zéro avec zéro et un avec un rejoignent la même suite. Leur réunion double le nombre de préfixes qui y arrivent, sans doubler le nombre de cases conservées. Les trois paires successives donnent deux fois deux fois deux préfixes acceptés, huit, tandis que la fin un reste une seule case. Camille conserve ces multiplicités lorsqu'elle additionne les arrivées depuis les flèches. Si elle marquait une case partagée « déjà comptée » et ignorait tout deuxième chemin qui y arrive, elle effacerait précisément une partie des formulaires distincts. Le partage de la représentation permet de réutiliser le calcul d'une suite, mais ce calcul doit être pondéré par chacune de ses entrées pour cette commande de comptage.
Les catégories citées n'apportent ni variable, ni permission de flèche, ni règle de décision à ces feuilles stipulées.