Accueil🇫🇷Chercher

Vers de Paterson

Les vers de Paterson sont un ensemble de machines de Turing. Créés par John Conway et Mike Paterson en 1971, ils furent popularisés par Martin Gardner en 1973 dans un article du Scientific American[1].

Règles

De façon générale, les vers de Paterson sont un type de turmite définis sur les bords d'une grille isométrique hexagonale.

En considérant une grille triangulaire infinie, on considère l'un des nœuds de cette grille comme étant un « ver ». Le ver se déplace initialement le long d'une ligne de la grille vers le nœud immédiatement situé à sa droite.

Arrivé à ce nœud, le ver peut prendre cinq directions possibles sans revenir sur ses pas. On pose que le ver prend l'une d'entre elles, avance vers le nœud suivant en conséquence et continuera à faire de même tant qu'il arrivera sur un nœud où cinq directions sont possibles :

  • Si le ver a continué tout droit, il continuera à faire de même indéfiniment
  • Si le ver a tourné de 60° à gauche ou à droite, il fera de même pendant cinq tours pour finalement retomber après un parcours hexagonal sur le nœud de départ où seules quatre directions sont possibles, puisqu'une cinquième a déjà été empruntée par le ver
  • Si le ver a tourné de 120° à gauche ou à droite, il retombe sur le nœud initial au bout de deux tours et là aussi, seules quatre directions sont possibles.

Dans les deux derniers cas, il est nécessaire de définir une direction que le ver va prendre parmi les quatre possibles. Ensuite, on procède à chaque nœud de la manière suivante :

  • Si la situation a déjà été rencontrée par le ver, il se déplace comme il l'a fait dans cette situation
  • Si la situation est inédite, on choisit une direction. Elle sera ensuite utilisée à chaque fois que la même situation se produira
  • Si le ver arrive sur un nœud dont toutes les directions ont déjà été utilisées, il s'arrête.

Notation

En arrivant sur un nœud, le ver a cinq directions possibles. On note « 0 » celle qui est en face d'elle (relativement à sa direction d'arrivée), « 1 » et « 5 » celles qui sont à 60° à sa droite et à sa gauche, « 2 » et « 4 » celles qui sont à 120° à sa droite et à sa gauche. La notation « 3 » correspond à la direction dont il vient et ne peut donc pas être utilisée.

On détermine alors le parcours d'un ver en notant les différents choix qu'on a fait. Ainsi, le ver « 244 » tourne de 120° à droite pendant les 3 premiers tours, puis de 120° à gauche, puis à nouveau de 120° à droite pendant 2 tours, puis de 120° à gauche. Après avoir tourné de 120° à droite pendant 2 derniers tours, le ver retourne au nœud de départ sans nouvelle direction possible et s'arrête.

Propriétés

Il n'existe que 412 règles possibles distinctes (en considérant les règles symétriques entre elles par rapport au départ comme une seule règle). Parmi elles :

  • 336 se terminent au bout d'un certain nombre d'étapes, parfois très grand. Ainsi, le ver « 1042020 » ne s'arrête qu'au bout de 57 493 855 205 939 étapes. En revanche, les règles « 200 » et « 244 » s'arrêtent au bout de seulement 9 étapes.
  • 73 sont infinies, à savoir que le ver ne s'arrête jamais.
  • 3 sont toujours indéterminées en 2015. « 1252121 » et « 1525115 » sont probablement infinies, tandis que « 1042015 » a été poussée au-delà de la 1019e étape sans que l'on puisse conclure.

Liste

Voici une liste des règles possibles pour le comportement d'un ver de Paterson :

#RègleNombre d'étapes
10Infini
21010001+00 000 000 000295,
31010002+00 000 000 000105,
41010005+000 000 000 00067,
5101001+000 000 000 00033,
61010051+0 000 000 0002 155,
71010052+00 000 000 000235,
81010055+0 000 000 0001 932,
9101020+000 000 000 00086,
10101021+000 000 000 00099,
111010251+00 000 000 000327,
121010252+00 000 000 000475,
131010255+000 000 000 00061,
141010401+000 000 000 00068,
151010402+00 000 000 000196,
161010405+000 000 000 00067,
17101041+000 000 000 00048,
181010451+0 000 000 0001 831,
191010452+00 000 000 000684,
201010455+000 000 000 00099,
211015001+000 000 000 00085,
221015002+000 000 000 00083,
231015005+000 000 000 00096,
24101501+000 000 000 00048,
251015051+0 000 000 0007 524,
261015052+00 000 000 000203,
271015055+000 000 000 00067,
281015201+000 000 00010 460,
291015202Infini
301015205Infini
31101521+000 000 000 00029,
321015251+00 000 000 000534,
331015252+0 000 000 0004 318,
341015255+000 000 000 00093,
351015410+000 000 000 00066,
361015411Infini
371015415+00 000 000 000534,
381015420+000 000 000 00043,
391015421+000 000 000 00048,
401015425+0 000 000 0004 432,
411015450+000 000 000 00053,
421015451+000 000 000 00048,
431015455+000 000 000 00067,
441040010+000 000 000 00054,
451040012+00 000 000 000296,
461040020+0 000 000 0001 660,
471040022+00 000 000 000970,
481040050+000 000 000 00071,
491040052+00 000 000 000102,
501040101+00 000 000 000289,
511040102+000 000 000 00097,
521040105+00 000 000 000110,
53104015+000 000 000 00057,
541040510+0 000 000 0001 545,
551040512+00 000 000569 804,
561040521+0 000 000 0001 020,
571040524+000 000 00010 795,
581040550+00 000 000 000451,
591040555+00 000 000 000451,
601042010+00 000 000918 339,
611042015Inconnu, supérieur à 5,2 × 1019[2]
621042020+57 493 855 205 939,[2]
631042022+57 493 855 205 905,[2]
64104205Infini
651042110+00 000 000 000631,
661042115+00 000 000 000118,
671042120+0 000 000 0002 056,
681042122+00 000 000 000747,
691042150+0 000 000 0005 865,
701042155+00 000 000 000398,
711042501+0 000 000 0001 550,
721042502+00 000 000 000130,
731042505+00 000 000 000153,
741042521+0 000 000 0002 754,
751042522+00 000 000 000196,
761042525+00 000 000 000122,
771044001Infini
781044002Infini
791044005+000 000 000 00046,
801044011Infini
811044012Infini
821044015+00 000 000 000212,
831044051+00 000 000 000330,
841044052Infini
851044055+00 000 000 000138,
861044201Infini
871044202Infini
881044205+000 000 00017 859,
89104421Infini
901044251+00 000 000 000347,
911044252Infini
921044255+000 000 000 00073,
931051+000 000 000 00028,
941054+000 000 000 00028,
95120012+00 000 000 000110,
961200141+00 000 000 000247,
971200142+00 000 000 000309,
981200145+00 000 000 000181,
991200412Infini
1001200414+00 000 000 000711,
1011200422+0 000 000 0005 132,
1021200424+00 000 000 000345,
1031200452+0 000 000 0001 515,
1041200454+00 000 000 000839,
1051200521+00 000 000 000304,
1061200522+00 000 000 000354,
1071200525+00 000 000 000631,
1081200541+0 000 000 0003 943,
1091200542+00 000 000 000201,
1101200545+00 000 000 000237,
1111202Infini
1121204141+00 000 000 000176,
1131204142+00 000 000 000735,
1141204145+000 000 000 00092,
115120415+000 000 000 00057,
1161204412+00 000 000 000415,
1171204414Infini
118120442Infini
1191204454+0 000 000 0002 578,
1201204455+0 000 000 0002 578,
12112045Infini
122121401+000 000 000 00048,
1231214041+000 000 000 00077,
1241214042+00 000 000 000609,
1251214045+00 000 000 000114,
1261214051+000 000 00022 847,
1271214052Infini
1281214055+00 000 000 000134,
129121421+000 000 000 00029,
1301214241+00 000 000 000105,
1311214242+0 000 000 0007 882,
1321214245+000 000 000 00045,
1331214251+00 000 000 000281,
1341214252+000 000 000 00062,
1351214255+00 000 000 000152,
1361214411Infini
1371214412+000 000 000 00048,
1381214415+000 000 000 00048,
139121444Infini
140121445Infini
141121510+000 000 000 00033,
142121512+000 000 000 00099,
143121514+000 000 000 00048,
1441215401+00 000 000 000151,
1451215402+000 000 000 00042,
1461215405+000 000 000 00053,
1471215421+0 000 000 0002 526,
1481215422+0 000 000 0002 857,
1491215425+00 000 000 000561,
150121544+000 000 000 00033,
15112155+000 000 000 00028,
1521251+000 000 000 00048,
1531252101+00 000 000220 142,
1541252104+0 000 000 0007 584,
1551252105+0 000 000 0009 260,
1561252121Inconnu, supérieur à 2,2 × 1016[2]
1571252124+0 000 000 0002 565,
1581252125+00 000 000 000731,
1591252141+00 000 000 000553,
1601252144+00 000 000 000173,
1611252145Infini
16212522Infini
1631252501+00 000 000 000248,
1641252504+00 000 000 000236,
1651252505+00 000 000 000101,
1661252521+0 000 000 0001 063,
1671252524+00 000 000 000162,
1681252525+000 000 000 00086,
1691252541+00 000 000 000514,
1701252544+0 000 000 0001 116,
1711252545+00 000 000 000738,
1721420011+000 000 000 00083,
1731420012+000 000 000 00081,
1741420015+000 000 000 00094,
1751420041Infini
1761420042+00 000 000 000897,
1771420045+00 000 000 000285,
1781420051+000 000 000 00090,
1791420052+000 000 000 00073,
1801420055+00 000 000 000697,
1811420211Infini
1821420214Infini
1831420215Infini
1841420221Infini[2]
1851420224+00016 811 365 528,[2]
1861420225+00 000 000 000284,
187142025+000 000 000 00034,
188142041+000 000 000 00090,
1891420441+000 000 000 00050,
1901420442Infini
1911420445+0 000 000 0001 688,
1921420451+0 000 000 0004 419,
1931420452+0 000 000 0003 566,
1941420455+00 000 000 000496,
195142101+000 000 000 00029,
1961421041+000 000 000 00050,
1971421042+00 000 000 000248,
1981421045+000 000 000 00039,
1991421051+000 000 000 00073,
2001421052+0 000 000 0005 715,
2011421055Infini
2021421211+000 000 000 00033,
2031421214+00 000 000 000219,
2041421215+000 000 000 00079,
2051421221+000 000 000 00023,
2061421224+0 000 000 0003 793,
2071421225+000 000 000 00046,
2081421251+000 000 000 00029,
2091421254+000 000 000 00052,
2101421255Infini
2111421411Infini
2121421412+000 000 000 00029,
2131421415+000 000 000 00035,
214142144Infini
215142145Infini
21614251+000 000 000 00048,
21714252Infini
21814255+000 000 000 00044,
2191450011+000 000 000 00083,
2201450012+000 000 000 00081,
2211450015+000 000 000 00094,
2221450041Infini
2231450042+00 000 000 000897,
2241450045+00 000 000 000285,
2251450051+000 000 000 00090,
2261450052+000 000 000 00073,
2271450055+00 000 000 000697,
2281450211Infini
2291450214Infini
2301450215Infini
2311450221Infini[2]
2321450224+00016 811 365 528,[2]
2331450225+00 000 000 000284,
234145025+000 000 000 00034,
235145041+000 000 000 00090,
2361450441+000 000 000 00050,
2371450442Infini
2381450445+0 000 000 0001 688,
2391450451+0 000 000 0004 419,
2401450452+0 000 000 0003 566,
2411450455+00 000 000 000496,
242145101+000 000 000 00029,
2431451041+000 000 000 00050,
2441451042+00 000 000 000248,
2451451045+000 000 000 00039,
2461451051+000 000 000 00073,
2471451052+0 000 000 0005 715,
2481451055Infini
2491451211+000 000 000 00033,
2501451214+00 000 000 000219,
2511451215+000 000 000 00079,
2521451221+000 000 000 00023,
2531451224+0 000 000 0003 793,
2541451225+000 000 000 00046,
2551451251+000 000 000 00029,
2561451254+000 000 000 00052,
2571451255Infini
2581451411Infini
2591451412+000 000 000 00029,
2601451415+000 000 000 00035,
261145144Infini
262145145Infini
26314551+000 000 000 00048,
26414552Infini
26514555+000 000 000 00044,
266150011+000 000 000 00050,
267150015+000 000 000 00033,
2681500411+00 000 000 000196,
2691500415+000 000 000 00069,
2701500421+00 000 000 000732,
2711500425+00 000 000 000159,
2721500451+000 000 000 00078,
2731500455+000 000 000 00045,
27415005Infini
275150111+000 000 000 00033,
276150115+000 000 000 00029,
2771501411+000 000 000 00055,
2781501412+000 000 000 00071,
2791501415+000 000 000 00044,
2801501451+00 000 000 000140,
2811501452+00 000 000 000113,
2821501455+00 000 000 000119,
2831501511+0 000 000 0001 672,
2841501515+000 000 00010 307,
2851501521Infini
2861501525+00 000 000 000165,
2871501551+00 000 000 000134,
2881501555+00 000 000 000112,
2891505111+000 000 00052 549,
2901505115Infini
2911505141+0 000 000 0001 632,
2921505145+0 000 000 0001 632,
2931505151+0 000 000 0001 978,
2941505155+0 000 000 0005 148,
2951505211+00 000 000 000419,
2961505215+0 000 000 0001 564,
2971505241+0 000 000 0004 371,
2981505245+0 000 000 0007 143,
2991505251+00 000 000 000454,
3001505255+00 000 000 000306,
3011505511+000 000 000 00062,
3021505514+00 000 000 000130,
3031505515+000 000 000 00055,
3041505551+00 000 000 000636,
3051505554+00 000 000 000206,
3061505555+00 000 000 000242,
3071520Infini
308152111+000 000 000 00033,
309152115+000 000 000 00029,
3101521411+00 000 000 000148,
3111521415+00 000 000 000247,
3121521421+00 000 000 000393,
3131521425+00 000 000 000113,
3141521451+00 000 000 000136,
3151521455+00 000 000 000132,
3161521511+00 000 000 000623,
3171521515+0 000 000 0002 377,
3181521521+00 000 000 000176,
3191521525+0 000 000 0001 742,
3201521551+00 000 000 000152,
3211521555+00 000 000 000112,
3221525111+00 000 000 000534,
3231525115Inconnu, supérieur à 4,5 × 1015[2]
3241525121+00 000 000 000356,
3251525125+00 000 000 000606,
3261525151+00 000 000 000533,
3271525155+00 000 000 000287,
3281525411+0 000 000 0002 754,
3291525412Infini
3301525415+00 000 000 000126,
3311525451+0 000 000 0005 708,
3321525452Infini
3331525455+00 000 000 000338,
3341525511+000 000 00083 618,
3351525515+0 000 000 0001 574,
3361525521+0 000 000 0007 275,
3371525525+00 000 000 000843,
3381525551+00 000 000 000262,
3391525555+00 000 000 000286,
3401541011+00 000 000 000194,
3411541012+00 000 000 000294,
3421541015+00 000 000 000180,
3431541051+00 000 000 000354,
3441541052+00 000 000 000107,
3451541055+00 000 000 000708,
346154111Infini
3471541121+000 000 000 00048,
3481541125+00 000 000 000114,
3491541151+000 000 000 00048,
3501541155+000 000 000 00058,
3511541511+0 000 000 0002 811,
3521541515+00 000 000 000663,
3531541521Infini
3541541525Infini
3551541551+00 000 000 000245,
3561541555+00 000 000 000321,
3571544101Infini
3581544102Infini
3591544105+000 000 00045 477,
360154411Infini
3611544151+00 000 000 000558,
3621544152Infini
3631544155+0 000 000 0007 565,
3641544501Infini
3651544502Infini
3661544505+00 000 000 000512,
3671544511Infini
3681544512Infini
3691544515+0 000 000 0001 457,
3701544551+0 000 000 0004 802,
3711544552Infini
3721544555+00 000 000 000138,
3731545Infini
374200+0 000 000 000 0009,
3752010+000 000 000 00015,
37620140+000 000 000 00030,
377201412+000 000 000 00045,
3782014141+00 000 000 000609,
3792014142+0 0003 563 608 205,[2]
3802014144+00 000 000 000615,
381201415+000 000 000 00037,
38220142+000 000 000 00027,
3832015Infini
3842104+000 000 000 00012,
3852105+000 000 000 00021,
3862144+000 000 000 00018,
38721450+000 000 000 00063,
3882145121+00 000 000 000438,
3892145122+00 000 000 000438,
3902145124+00 000 000 000411,
3912145141+0 000 000 0002 478,
3922145142+000 00087 996 218,[2]
3932145144+0 000 000 0002 373,
394214515+000 000 000 00068,
39521452+000 000 000 00048,
396215Infini
397244+0 000 000 000 0009,
3982450+000 000 000 00015,
39924540+000 000 000 00030,
400245412+000 000 000 00045,
4012454141+00 000 000 000609,
4022454142+0 0003 563 608 205,[2]
4032454144+00 000 000 000615,
404245415+000 000 000 00037,
40524542+000 000 000 00027,
4062455Infini
4072510+000 000 000 00012,
4082514+000 000 000 00018,
4092515Infini
4102540+000 000 000 00012,
4112544+000 000 000 00018,
4122545Infini

Voir aussi

Liens internes

Liens externes

Références

  1. (en) Martin Gardner, « Mathematical Games: Fantastic patterns traced by programmed "worms" », Scientific American, vol. 229, , p. 116-123
  2. (en) Tomas Rokicki, « My results on Paterson's Worms »
Cet article est issu de wikipedia. Text licence: CC BY-SA 4.0, Des conditions supplémentaires peuvent s’appliquer aux fichiers multimédias.