Nora prépare un index de renvois entièrement fictif pour un livre privé. Chaque fiche possède un nom et une seule destination suivante. Camille doit suivre ces destinations depuis une fiche donnée, reconnaître si le parcours revient sur lui-même, puis nommer la première fiche de la boucle. Aucun index, fichier ou livre réel n'est testé. Notre chaîne ne suspend aucune lecture pour revenir ensuite au passage qui l'appelait : chaque déplacement remplace simplement la fiche courante par sa destination.
Une notice du Met classe une œuvre parmi les estampes.
Une autre notice du Met classe une œuvre parmi les estampes.
Une troisième notice du Met classe une œuvre parmi les livres.
Ces notices ont été lues pour leurs catégories. Aucun sujet ou procédé artistique n'est repris ; les fiches, destinations et décisions sont créées ici.
Nous employons un petit procédé classique de détection de cycle, sans invention revendiquée. Un curseur désigne une fiche présente ; avancer d'un pas signifie consulter sa destination. Les fiches de ce modèle ont toutes une destination définie, qui reste fixe pendant un contrôle. Aucun écran, logiciel ni vitesse physique de lecture n'est étudié. Les coûts annoncés compteront seulement ces consultations abstraites, et les noms seront des identifiants distincts plutôt que les titres éventuellement semblables de deux textes.
Le premier retour ne donne pas le nombre de fiches avant la boucle
Camille reçoit les destinations A vers B, B vers C, C vers D, D vers E, E vers F, F vers G, G vers H et H vers C. Depuis A, elle obtient donc A, B, C, D, E, F, G, H, C. La première fiche répétée est C. Deux déplacements, A vers B puis B vers C, précèdent son entrée dans la boucle. Celle-ci contient six fiches distinctes, C, D, E, F, G et H. Nora inscrit deux pour la partie précédant la boucle et six pour sa période, au lieu de leur donner un même compte.
Pour réaliser un premier contrôle, Camille garde une liste des fiches déjà rencontrées. Elle inscrit A avant de consulter sa destination, puis B, C et les cinq suivantes. Après la consultation de H, C figure déjà dans sa liste. Son premier emplacement dans cette liste est le troisième, à l'indice deux si le départ A porte l'indice zéro. La distance entre ce premier C et le retour situé à l'indice huit est six. Camille remet ainsi les deux nombres avec leur origine dans le relevé, plutôt que déduire la longueur de la boucle du seul fait que huit déplacements ont été effectués.
Nora voudrait garder seulement deux curseurs plutôt que la liste complète. Camille prépare alors une seconde méthode sur la même chaîne. Les deux curseurs partent de A ; au cours de chaque tour, le premier avance d'un pas, le second de deux. Ils ne s'arrêtent pas sur leur égalité initiale en A : la comparaison qui nous intéresse vient après leurs déplacements. Les noms conservés dans les deux curseurs suffisent à comparer leurs fiches présentes, mais aucun de ces noms ne raconte à lui seul la liste des fiches déjà traversées.
Deux vitesses se rencontrent ailleurs que sur l'entrée
Après le premier tour, les curseurs sont B et C. Après le deuxième, C et E ; après le troisième, D et G ; après le quatrième, E et C ; après le cinquième, F et E. Ils se rejoignent au sixième en G : le premier a effectué six déplacements, le second douze. Nora retire donc G de la case « entrée de la boucle ». La rencontre a montré une répétition compatible avec la règle des destinations fixes, mais elle n'a pas désigné C. Les cinq comparaisons précédentes montrent également que ce sixième tour est leur première rencontre après le départ.
Camille peut expliquer pourquoi deux noms égaux prouvent ici une répétition. Au sixième tour, G est à la fois la fiche atteinte après six déplacements et celle atteinte après douze depuis le même départ. Le parcours a donc rejoint une même fiche après six consultations supplémentaires. À partir de cette fiche, une destination unique impose la même suite chaque fois qu'elle est suivie. Ce raisonnement porte sur les identifiants G, pas sur une phrase imprimée qui pourrait être commune à deux fiches. Nora conserve leur égalité comme preuve de boucle dans la chaîne donnée, sans la transformer en position d'entrée.
Pour retrouver l'entrée, Camille replace le premier curseur en A et garde le second au G de la rencontre. Elle les fait maintenant avancer chacun d'un pas. Au premier déplacement, ils sont B et H. Au deuxième, ils sont C et C. Nora choisit C et le nombre deux pour la fiche d'entrée et la longueur de la partie qui la précède. Camille conserve le G initial dans le relevé de détection, mais ne le maintient plus comme résultat de la nouvelle recherche. Les deux opérations ont produit deux rencontres différentes qui répondent à deux questions différentes.
Nora demande pourquoi ce replacement ne serait pas seulement une réussite fortuite. Camille appelle t le nombre de tours de la première méthode, donc six ici, et λ la longueur de la boucle. À la rencontre, le second curseur est à l'indice 2t et le premier à l'indice t du parcours. Ils sont tous deux dans la boucle ; deux indices y désignent la même fiche lorsque leur différence est un multiple de λ. Leur différence vaut t. La rencontre impose donc que t soit un multiple de λ. Avec un second curseur gardé à l'indice t, les deux curseurs avançant ensuite ensemble conservent précisément cet écart d'indice.
Camille distingue cependant l'écart d'indice et une égalité déjà présente avant la boucle. La partie A puis B ne se répète jamais dans le parcours. Tant que le curseur replacé au départ reste dans cette partie, il ne peut être égal à celui conservé dans la boucle. Dès qu'il atteint C, après deux pas, l'écart t multiple de six donne la même fiche aux deux. Ils ne peuvent donc se rencontrer plus tôt et leur première rencontre de cette seconde phase est l'entrée. Nora conserve la condition de deux vitesses un et deux dans ce certificat, au lieu de promettre le même replacement après n'importe quelle rencontre.
Trois pas contre un détectent encore, mais changent le replacement
Nora essaie justement une autre première phase : un pas pour le premier curseur, trois pour le second. Le premier tour donne B et D ; le deuxième C et G ; le troisième D et D. La rencontre arrive donc plus tôt, au troisième tour et sur D. Camille accepte cette nouvelle détection. Mais lorsqu'elle replace un curseur en A et garde l'autre en D, tous deux avançant désormais d'un pas, elle obtient successivement B et E, C et F, D et G, E et H, F et C. La méthode ne retrouve pas C par une égalité des deux noms.
Dans la boucle, les deux curseurs de cette seconde phase restent séparés de trois positions. Après trois tours de la détection, le curseur rapide était à l'indice neuf, celui d'un pas à l'indice trois : leur différence six est bien une période entière. Pourtant, la différence entre l'indice trois conservé et le départ zéro ne vaut que trois. Nora ne peut donc pas réutiliser le certificat précédent. Pour les vitesses un et trois, la rencontre impose que 2t soit un multiple de λ, et non que t le soit. Ici, 2t vaut six tandis que t vaut trois. La détection correcte ne suffit pas à rendre correct ce replacement particulier.
Nora choisit de ne pas modifier les destinations pour sauver la rencontre après replacement. Camille garde la chaîne intacte et prépare une autre façon de retrouver son entrée. Depuis D, elle immobilise un curseur comme repère et fait tourner l'autre d'un pas à la fois : E, F, G, H, C, puis D. Le premier retour au repère prend six déplacements et fournit λ égal à six. Cette phase compte la période depuis une fiche de la boucle, sans réclamer que cette fiche soit déjà son entrée. Le D choisi convient comme repère, alors qu'il ne convenait pas comme réponse à la question précédente.
Camille replace ensuite les deux curseurs en A et avance l'un de six pas avant toute comparaison de leur marche commune. Celui-ci atteint G ; l'autre demeure A. Ils avancent alors ensemble : B et H, puis C et C. Nora retient C et deux comme auparavant. Le décalage initial est maintenant la période effectivement comptée, pas le nombre trois de tours d'une autre détection. Camille retire la fiche qui donnait ce trois comme écart à conserver et la remplace par le tour complet de six réellement obtenu depuis D.
La preuve du nouveau départ ne dépend plus de la vitesse de détection. Deux curseurs dont les indices diffèrent exactement de λ coïncident dès qu'ils sont dans la boucle. Le curseur laissé au départ n'y entre qu'après les deux pas de la partie initiale ; avant cela, son nom est absent de toutes les positions cycliques. Le décalage de six donne donc une première égalité exactement en C. Nora choisit cette préparation pour sa variante à trois pas. Elle a reçu la même entrée finale avec une phase supplémentaire justifiée, plutôt qu'un résultat correct annoncé auprès d'une procédure qui tournait sans fin.
Deux départs peuvent rejoindre le même cycle sans se rencontrer au même moment
Une autre commande donne deux fiches de départ. La première reste A. La seconde est J, dont la destination est K, puis K mène à E. E garde ensuite F, G, H, C et D comme dans la boucle initiale. Nora ne demande plus l'entrée depuis A seul : elle veut savoir si deux curseurs partant ensemble de A et de J, et avançant chacun d'un pas par tour, finiront par occuper la même fiche au même tour. Partager les fiches d'une boucle ne répond pas encore à cette question synchronisée.
Camille remplit leur marche : A et J au départ, B et K au premier tour, C et E au deuxième, D et F au troisième, E et G au quatrième, F et H au cinquième, G et C au sixième. Une fois les deux curseurs dans la boucle, ils sont séparés de deux positions, un écart qui reste inchangé puisque chacun avance d'un pas. Ils ne seront donc jamais égaux au même tour. Nora retire la mention « les parcours se rejoignent, donc les curseurs se rencontrent ». Les deux parcours possèdent bien C, D, E, F, G et H, mais ils n'y arrivent pas avec la même phase.
Nora décide alors quelle question sa feuille doit réellement fermer. Pour reconnaître l'appartenance au même cycle, Camille retrouve l'entrée C depuis A et E depuis J, puis effectue un tour complet depuis C. Elle rencontre E au cours de ce tour et revient à C après six pas. Elle peut donc répondre oui à la question de cycle commun et non à celle d'égalité synchronisée. Nora garde ces deux réponses avec leurs contrôles propres. Elle ne déclare pas que les entrées différentes prouvaient deux cycles différents : une entrée dépend du départ, alors que les six fiches cycliques peuvent être communes aux deux chaînes.
Nora crée enfin une deuxième tête, Q vers R, R vers S, S vers T et T vers E. Les deux curseurs partent cette fois de A et de Q. Les comparaisons donnent B et R, C et S, D et T, puis E et E au quatrième tour. La rencontre est suivie de F et F, puis G et G ; la destination unique garde leur égalité. Cette tête rejoint exactement la phase du parcours de A. Nora choisit Q pour la commande qui exige une rencontre synchronisée, et conserve J seulement dans la feuille répondant au cycle commun. Elle a changé deux destinations précédant E, pas la boucle elle-même.
Le contrôle des indices confirme cette décision. Depuis A, l'entrée C est atteinte après deux pas ; E vient deux positions plus loin dans la boucle, donc à l'indice quatre. Depuis Q, l'entrée E est atteinte après quatre pas. Les deux parcours nomment ainsi E au même indice. Depuis J, E venait à l'indice deux, créant le décalage conservé de deux positions. Camille remet les longueurs des deux têtes et la position de E dans le cycle auprès du choix Q. La différence ne vient pas d'un hasard dans les noms de fiches, mais des déplacements effectivement ajoutés avant leur première position commune.
Garder moins de noms peut demander davantage de consultations
Nora compare maintenant les préparations sur la chaîne A à H, en comptant chaque consultation d'une destination comme une opération. La liste des noms visités a consulté successivement A, B, C, D, E, F, G puis H : huit opérations, avant de reconnaître le C déjà enregistré. Elle conservait alors huit identifiants distincts, avec leurs indices. Nora pose une règle supplémentaire pour ce seul exercice : cette liste ne doit pas recevoir plus de trois noms. La méthode de liste dépasserait cette limite avant d'avoir trouvé le retour, alors même que son total de consultations est le plus petit des deux préparations réalisées.
Avec deux curseurs, la première phase aux vitesses un et deux effectue trois consultations par tour : une pour le premier et deux successives pour le second. Ses six tours en demandent donc dix-huit. Le replacement qui trouve C prend deux tours à deux consultations, soit quatre supplémentaires. Camille compte enfin les six destinations du tour complet depuis C pour remettre λ. Le total atteint vingt-huit consultations. Nora ne présente donc pas les deux curseurs comme une accélération de la liste dans ce cas. Elle reçoit une méthode qui conserve moins de noms actifs, avec davantage de consultations effectivement effectuées.
La règle de trois noms porte sur des identifiants de fiches, pas sur l'absence de tout autre renseignement. Camille doit aussi conserver des compteurs : tours effectués, longueur de la tête et période. Nora accepte expressément ces entiers sur la feuille. Sans eux, deux noms égaux ne fourniraient pas automatiquement les deux nombres demandés. La liste conservait de son côté des indices auprès de huit noms. Camille joint donc à chaque préparation les informations qu'elle garde réellement, au lieu de nommer « sans mémoire » une procédure qui possède deux curseurs et des compteurs.
Une dernière consigne limite la préparation complète à vingt consultations de destinations, tout en gardant la limite de trois noms et en demandant entrée plus période par le procédé à deux curseurs décrit. Nora refuse cette combinaison pour ce procédé précis : ses vingt-huit consultations sont déjà remplies et dépassent vingt. Elle ne déclare pas impossible toute méthode imaginable sous ces limites, car leur optimalité générale n'a pas été prouvée. Pour le livrable présent, elle retire la limite vingt et choisit les vingt-huit opérations avec les deux curseurs. Si elle rétablit la liste à huit noms, elle peut conserver ses huit consultations dans une remise séparée.
Faire finir la chaîne demande une destination réellement terminale
Nora souhaite ensuite réparer la chaîne A à H pour qu'une lecture depuis A se termine, tout en rencontrant G et H. Elle autorise une seule modification de destination, mais conserve d'abord la règle donnant à chaque fiche un successeur parmi les mêmes huit noms. Camille refuse de promettre une fin sous cette règle. Un parcours possède toujours une prochaine fiche ; après neuf positions, il a nécessairement répété un des huit noms. Les destinations restent fixes, donc la répétition relance la même suite. Changer un lien pourrait déplacer l'entrée ou raccourcir le cycle, mais ne pourrait créer une fin absente de toutes les destinations autorisées.
Camille remplit justement une tentative : elle remplace la destination H vers C par H vers H. Le parcours atteint encore G et H, puis reste sur H. La nouvelle boucle comporte une fiche au lieu de six, avec sept déplacements avant son entrée depuis A. Nora retire la mention « index terminé » de cette proposition : H est devenue une boucle sur elle-même, pas une destination terminale. La différence est contrôlable dans les opérations données. Suivre encore la destination de H demande toujours une consultation et redonne H ; rien dans cette nouvelle relation n'a fourni l'ordre de s'arrêter.
Nora autorise alors une destination supplémentaire, nommée fin, qui ne désigne aucune fiche à consulter. Elle souhaite conserver G et H avant cette fin et ne modifier qu'un lien de la boucle initiale. Camille place fin comme destination de H. Le parcours devient A, B, C, D, E, F, G, H, fin et atteint donc les deux noms exigés avant de se terminer. Elle refuse de remplacer plutôt la destination de G par fin : G serait rencontré, mais H manquerait. Les coupures après C, D, E ou F manqueraient également H. Couper après H est donc le seul choix parmi les six liens de la boucle qui garde les deux rencontres requises depuis A.
La remise conserve la fiche H et son contenu fictif ; elle a remplacé uniquement sa destination. Nora ne retire pas H du catalogue en prenant sa destination fin pour un nouveau nom de fiche. Camille remet les huit noms effectivement rencontrés et l'arrêt qui les suit. Elle garde aussi la tentative H vers H comme modification refusée, avec son cycle d'une fiche. La permission terminale et la contrainte de rencontrer G et H ont ensemble choisi l'unique coupure, au lieu de donner à un changement de lien quelconque la qualité d'une fin conforme.
Les premières feuilles donnent C comme entrée depuis A et six comme période. La variante à trois pas compte d'abord cette période pour reconstruire correctement l'entrée ; les départs A et J partagent un cycle sans rencontre synchronisée, tandis que A et Q se rencontrent en E. La réparation finale conserve G et H puis atteint la nouvelle destination fin. Nora garde les procédures et leurs questions. Aucun de ces résultats ne certifie un index réel ni le fonctionnement d'un appareil de lecture : ils terminent les contrôles effectivement composés pour cette chaîne de fiches.
Les Éditions privées donnent une forme aux voix, aux archives et aux histoires que vous souhaitez transmettre.
Découvrir Codex de Maison →