Vers de Paterson

Un article de Wikipédia, l'encyclopédie libre.

Cet article est une ébauche concernant la logique.

Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants.

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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[modifier | modifier le code]

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

# Règle Nombre d'étapes
1 0 Infini
2 1010001 +00 000 000 000295,
3 1010002 +00 000 000 000105,
4 1010005 +000 000 000 00067,
5 101001 +000 000 000 00033,
6 1010051 +0 000 000 0002 155,
7 1010052 +00 000 000 000235,
8 1010055 +0 000 000 0001 932,
9 101020 +000 000 000 00086,
10 101021 +000 000 000 00099,
11 1010251 +00 000 000 000327,
12 1010252 +00 000 000 000475,
13 1010255 +000 000 000 00061,
14 1010401 +000 000 000 00068,
15 1010402 +00 000 000 000196,
16 1010405 +000 000 000 00067,
17 101041 +000 000 000 00048,
18 1010451 +0 000 000 0001 831,
19 1010452 +00 000 000 000684,
20 1010455 +000 000 000 00099,
21 1015001 +000 000 000 00085,
22 1015002 +000 000 000 00083,
23 1015005 +000 000 000 00096,
24 101501 +000 000 000 00048,
25 1015051 +0 000 000 0007 524,
26 1015052 +00 000 000 000203,
27 1015055 +000 000 000 00067,
28 1015201 +000 000 00010 460,
29 1015202 Infini
30 1015205 Infini
31 101521 +000 000 000 00029,
32 1015251 +00 000 000 000534,
33 1015252 +0 000 000 0004 318,
34 1015255 +000 000 000 00093,
35 1015410 +000 000 000 00066,
36 1015411 Infini
37 1015415 +00 000 000 000534,
38 1015420 +000 000 000 00043,
39 1015421 +000 000 000 00048,
40 1015425 +0 000 000 0004 432,
41 1015450 +000 000 000 00053,
42 1015451 +000 000 000 00048,
43 1015455 +000 000 000 00067,
44 1040010 +000 000 000 00054,
45 1040012 +00 000 000 000296,
46 1040020 +0 000 000 0001 660,
47 1040022 +00 000 000 000970,
48 1040050 +000 000 000 00071,
49 1040052 +00 000 000 000102,
50 1040101 +00 000 000 000289,
51 1040102 +000 000 000 00097,
52 1040105 +00 000 000 000110,
53 104015 +000 000 000 00057,
54 1040510 +0 000 000 0001 545,
55 1040512 +00 000 000569 804,
56 1040521 +0 000 000 0001 020,
57 1040524 +000 000 00010 795,
58 1040550 +00 000 000 000451,
59 1040555 +00 000 000 000451,
60 1042010 +00 000 000918 339,
61 1042015 Inconnu, supérieur à 5,2 × 1019[2]
62 1042020 +57 493 855 205 939,[2]
63 1042022 +57 493 855 205 905,[2]
64 104205 Infini
65 1042110 +00 000 000 000631,
66 1042115 +00 000 000 000118,
67 1042120 +0 000 000 0002 056,
68 1042122 +00 000 000 000747,
69 1042150 +0 000 000 0005 865,
70 1042155 +00 000 000 000398,
71 1042501 +0 000 000 0001 550,
72 1042502 +00 000 000 000130,
73 1042505 +00 000 000 000153,
74 1042521 +0 000 000 0002 754,
75 1042522 +00 000 000 000196,
76 1042525 +00 000 000 000122,
77 1044001 Infini
78 1044002 Infini
79 1044005 +000 000 000 00046,
80 1044011 Infini
81 1044012 Infini
82 1044015 +00 000 000 000212,
83 1044051 +00 000 000 000330,
84 1044052 Infini
85 1044055 +00 000 000 000138,
86 1044201 Infini
87 1044202 Infini
88 1044205 +000 000 00017 859,
89 104421 Infini
90 1044251 +00 000 000 000347,
91 1044252 Infini
92 1044255 +000 000 000 00073,
93 1051 +000 000 000 00028,
94 1054 +000 000 000 00028,
95 120012 +00 000 000 000110,
96 1200141 +00 000 000 000247,
97 1200142 +00 000 000 000309,
98 1200145 +00 000 000 000181,
99 1200412 Infini
100 1200414 +00 000 000 000711,
101 1200422 +0 000 000 0005 132,
102 1200424 +00 000 000 000345,
103 1200452 +0 000 000 0001 515,
104 1200454 +00 000 000 000839,
105 1200521 +00 000 000 000304,
106 1200522 +00 000 000 000354,
107 1200525 +00 000 000 000631,
108 1200541 +0 000 000 0003 943,
109 1200542 +00 000 000 000201,
110 1200545 +00 000 000 000237,
111 1202 Infini
112 1204141 +00 000 000 000176,
113 1204142 +00 000 000 000735,
114 1204145 +000 000 000 00092,
115 120415 +000 000 000 00057,
116 1204412 +00 000 000 000415,
117 1204414 Infini
118 120442 Infini
119 1204454 +0 000 000 0002 578,
120 1204455 +0 000 000 0002 578,
121 12045 Infini
122 121401 +000 000 000 00048,
123 1214041 +000 000 000 00077,
124 1214042 +00 000 000 000609,
125 1214045 +00 000 000 000114,
126 1214051 +000 000 00022 847,
127 1214052 Infini
128 1214055 +00 000 000 000134,
129 121421 +000 000 000 00029,
130 1214241 +00 000 000 000105,
131 1214242 +0 000 000 0007 882,
132 1214245 +000 000 000 00045,
133 1214251 +00 000 000 000281,
134 1214252 +000 000 000 00062,
135 1214255 +00 000 000 000152,
136 1214411 Infini
137 1214412 +000 000 000 00048,
138 1214415 +000 000 000 00048,
139 121444 Infini
140 121445 Infini
141 121510 +000 000 000 00033,
142 121512 +000 000 000 00099,
143 121514 +000 000 000 00048,
144 1215401 +00 000 000 000151,
145 1215402 +000 000 000 00042,
146 1215405 +000 000 000 00053,
147 1215421 +0 000 000 0002 526,
148 1215422 +0 000 000 0002 857,
149 1215425 +00 000 000 000561,
150 121544 +000 000 000 00033,
151 12155 +000 000 000 00028,
152 1251 +000 000 000 00048,
153 1252101 +00 000 000220 142,
154 1252104 +0 000 000 0007 584,
155 1252105 +0 000 000 0009 260,
156 1252121 Inconnu, supérieur à 2,2 × 1016[2]
157 1252124 +0 000 000 0002 565,
158 1252125 +00 000 000 000731,
159 1252141 +00 000 000 000553,
160 1252144 +00 000 000 000173,
161 1252145 Infini
162 12522 Infini
163 1252501 +00 000 000 000248,
164 1252504 +00 000 000 000236,
165 1252505 +00 000 000 000101,
166 1252521 +0 000 000 0001 063,
167 1252524 +00 000 000 000162,
168 1252525 +000 000 000 00086,
169 1252541 +00 000 000 000514,
170 1252544 +0 000 000 0001 116,
171 1252545 +00 000 000 000738,
172 1420011 +000 000 000 00083,
173 1420012 +000 000 000 00081,
174 1420015 +000 000 000 00094,
175 1420041 Infini
176 1420042 +00 000 000 000897,
177 1420045 +00 000 000 000285,
178 1420051 +000 000 000 00090,
179 1420052 +000 000 000 00073,
180 1420055 +00 000 000 000697,
181 1420211 Infini
182 1420214 Infini
183 1420215 Infini
184 1420221 Infini[2]
185 1420224 +00016 811 365 528,[2]
186 1420225 +00 000 000 000284,
187 142025 +000 000 000 00034,
188 142041 +000 000 000 00090,
189 1420441 +000 000 000 00050,
190 1420442 Infini
191 1420445 +0 000 000 0001 688,
192 1420451 +0 000 000 0004 419,
193 1420452 +0 000 000 0003 566,
194 1420455 +00 000 000 000496,
195 142101 +000 000 000 00029,
196 1421041 +000 000 000 00050,
197 1421042 +00 000 000 000248,
198 1421045 +000 000 000 00039,
199 1421051 +000 000 000 00073,
200 1421052 +0 000 000 0005 715,
201 1421055 Infini
202 1421211 +000 000 000 00033,
203 1421214 +00 000 000 000219,
204 1421215 +000 000 000 00079,
205 1421221 +000 000 000 00023,
206 1421224 +0 000 000 0003 793,
207 1421225 +000 000 000 00046,
208 1421251 +000 000 000 00029,
209 1421254 +000 000 000 00052,
210 1421255 Infini
211 1421411 Infini
212 1421412 +000 000 000 00029,
213 1421415 +000 000 000 00035,
214 142144 Infini
215 142145 Infini
216 14251 +000 000 000 00048,
217 14252 Infini
218 14255 +000 000 000 00044,
219 1450011 +000 000 000 00083,
220 1450012 +000 000 000 00081,
221 1450015 +000 000 000 00094,
222 1450041 Infini
223 1450042 +00 000 000 000897,
224 1450045 +00 000 000 000285,
225 1450051 +000 000 000 00090,
226 1450052 +000 000 000 00073,
227 1450055 +00 000 000 000697,
228 1450211 Infini
229 1450214 Infini
230 1450215 Infini
231 1450221 Infini[2]
232 1450224 +00016 811 365 528,[2]
233 1450225 +00 000 000 000284,
234 145025 +000 000 000 00034,
235 145041 +000 000 000 00090,
236 1450441 +000 000 000 00050,
237 1450442 Infini
238 1450445 +0 000 000 0001 688,
239 1450451 +0 000 000 0004 419,
240 1450452 +0 000 000 0003 566,
241 1450455 +00 000 000 000496,
242 145101 +000 000 000 00029,
243 1451041 +000 000 000 00050,
244 1451042 +00 000 000 000248,
245 1451045 +000 000 000 00039,
246 1451051 +000 000 000 00073,
247 1451052 +0 000 000 0005 715,
248 1451055 Infini
249 1451211 +000 000 000 00033,
250 1451214 +00 000 000 000219,
251 1451215 +000 000 000 00079,
252 1451221 +000 000 000 00023,
253 1451224 +0 000 000 0003 793,
254 1451225 +000 000 000 00046,
255 1451251 +000 000 000 00029,
256 1451254 +000 000 000 00052,
257 1451255 Infini
258 1451411 Infini
259 1451412 +000 000 000 00029,
260 1451415 +000 000 000 00035,
261 145144 Infini
262 145145 Infini
263 14551 +000 000 000 00048,
264 14552 Infini
265 14555 +000 000 000 00044,
266 150011 +000 000 000 00050,
267 150015 +000 000 000 00033,
268 1500411 +00 000 000 000196,
269 1500415 +000 000 000 00069,
270 1500421 +00 000 000 000732,
271 1500425 +00 000 000 000159,
272 1500451 +000 000 000 00078,
273 1500455 +000 000 000 00045,
274 15005 Infini
275 150111 +000 000 000 00033,
276 150115 +000 000 000 00029,
277 1501411 +000 000 000 00055,
278 1501412 +000 000 000 00071,
279 1501415 +000 000 000 00044,
280 1501451 +00 000 000 000140,
281 1501452 +00 000 000 000113,
282 1501455 +00 000 000 000119,
283 1501511 +0 000 000 0001 672,
284 1501515 +000 000 00010 307,
285 1501521 Infini
286 1501525 +00 000 000 000165,
287 1501551 +00 000 000 000134,
288 1501555 +00 000 000 000112,
289 1505111 +000 000 00052 549,
290 1505115 Infini
291 1505141 +0 000 000 0001 632,
292 1505145 +0 000 000 0001 632,
293 1505151 +0 000 000 0001 978,
294 1505155 +0 000 000 0005 148,
295 1505211 +00 000 000 000419,
296 1505215 +0 000 000 0001 564,
297 1505241 +0 000 000 0004 371,
298 1505245 +0 000 000 0007 143,
299 1505251 +00 000 000 000454,
300 1505255 +00 000 000 000306,
301 1505511 +000 000 000 00062,
302 1505514 +00 000 000 000130,
303 1505515 +000 000 000 00055,
304 1505551 +00 000 000 000636,
305 1505554 +00 000 000 000206,
306 1505555 +00 000 000 000242,
307 1520 Infini
308 152111 +000 000 000 00033,
309 152115 +000 000 000 00029,
310 1521411 +00 000 000 000148,
311 1521415 +00 000 000 000247,
312 1521421 +00 000 000 000393,
313 1521425 +00 000 000 000113,
314 1521451 +00 000 000 000136,
315 1521455 +00 000 000 000132,
316 1521511 +00 000 000 000623,
317 1521515 +0 000 000 0002 377,
318 1521521 +00 000 000 000176,
319 1521525 +0 000 000 0001 742,
320 1521551 +00 000 000 000152,
321 1521555 +00 000 000 000112,
322 1525111 +00 000 000 000534,
323 1525115 Inconnu, supérieur à 4,5 × 1015[2]
324 1525121 +00 000 000 000356,
325 1525125 +00 000 000 000606,
326 1525151 +00 000 000 000533,
327 1525155 +00 000 000 000287,
328 1525411 +0 000 000 0002 754,
329 1525412 Infini
330 1525415 +00 000 000 000126,
331 1525451 +0 000 000 0005 708,
332 1525452 Infini
333 1525455 +00 000 000 000338,
334 1525511 +000 000 00083 618,
335 1525515 +0 000 000 0001 574,
336 1525521 +0 000 000 0007 275,
337 1525525 +00 000 000 000843,
338 1525551 +00 000 000 000262,
339 1525555 +00 000 000 000286,
340 1541011 +00 000 000 000194,
341 1541012 +00 000 000 000294,
342 1541015 +00 000 000 000180,
343 1541051 +00 000 000 000354,
344 1541052 +00 000 000 000107,
345 1541055 +00 000 000 000708,
346 154111 Infini
347 1541121 +000 000 000 00048,
348 1541125 +00 000 000 000114,
349 1541151 +000 000 000 00048,
350 1541155 +000 000 000 00058,
351 1541511 +0 000 000 0002 811,
352 1541515 +00 000 000 000663,
353 1541521 Infini
354 1541525 Infini
355 1541551 +00 000 000 000245,
356 1541555 +00 000 000 000321,
357 1544101 Infini
358 1544102 Infini
359 1544105 +000 000 00045 477,
360 154411 Infini
361 1544151 +00 000 000 000558,
362 1544152 Infini
363 1544155 +0 000 000 0007 565,
364 1544501 Infini
365 1544502 Infini
366 1544505 +00 000 000 000512,
367 1544511 Infini
368 1544512 Infini
369 1544515 +0 000 000 0001 457,
370 1544551 +0 000 000 0004 802,
371 1544552 Infini
372 1544555 +00 000 000 000138,
373 1545 Infini
374 200 +0 000 000 000 0009,
375 2010 +000 000 000 00015,
376 20140 +000 000 000 00030,
377 201412 +000 000 000 00045,
378 2014141 +00 000 000 000609,
379 2014142 +0 0003 563 608 205,[2]
380 2014144 +00 000 000 000615,
381 201415 +000 000 000 00037,
382 20142 +000 000 000 00027,
383 2015 Infini
384 2104 +000 000 000 00012,
385 2105 +000 000 000 00021,
386 2144 +000 000 000 00018,
387 21450 +000 000 000 00063,
388 2145121 +00 000 000 000438,
389 2145122 +00 000 000 000438,
390 2145124 +00 000 000 000411,
391 2145141 +0 000 000 0002 478,
392 2145142 +000 00087 996 218,[2]
393 2145144 +0 000 000 0002 373,
394 214515 +000 000 000 00068,
395 21452 +000 000 000 00048,
396 215 Infini
397 244 +0 000 000 000 0009,
398 2450 +000 000 000 00015,
399 24540 +000 000 000 00030,
400 245412 +000 000 000 00045,
401 2454141 +00 000 000 000609,
402 2454142 +0 0003 563 608 205,[2]
403 2454144 +00 000 000 000615,
404 245415 +000 000 000 00037,
405 24542 +000 000 000 00027,
406 2455 Infini
407 2510 +000 000 000 00012,
408 2514 +000 000 000 00018,
409 2515 Infini
410 2540 +000 000 000 00012,
411 2544 +000 000 000 00018,
412 2545 Infini

Voir aussi[modifier | modifier le code]

Liens internes[modifier | modifier le code]

Liens externes[modifier | modifier le code]

Références[modifier | modifier le code]

  1. ↑ (en) Martin Gardner, « Mathematical Games: Fantastic patterns traced by programmed "worms" », Scientific American, vol. 229,‎ , p. 116-123
  2. ↑ a b c d e f g h i j k et l (en) Tomas Rokicki, « My results on Paterson's Worms »
Ce document provient de « https://fr.wikipedia.org/w/index.php?title=Vers_de_Paterson&oldid=170236914 ».