Vers de Paterson

Un article de Wikipédia, l'encyclopédie libre.
Aller à : navigation, rechercher

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 elle, 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.
  • 71 sont infinies, à savoir que le ver ne s'arrête jamais.
  • 5 sont toujours indéterminées. « 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 295
3 1010002 105
4 1010005 67
5 101001 33
6 1010051 2 155
7 1010052 235
8 1010055 1 932
9 101020 86
10 101021 99
11 1010251 327
12 1010252 475
13 1010255 61
14 1010401 68
15 1010402 196
16 1010405 67
17 101041 48
18 1010451 1 831
19 1010452 684
20 1010455 99
21 1015001 85
22 1015002 83
23 1015005 96
24 101501 48
25 1015051 7 524
26 1015052 203
27 1015055 67
28 1015201 10 460
29 1015202 Infini
30 1015205 Infini
31 101521 29
32 1015251 534
33 1015252 4 318
34 1015255 93
35 1015410 66
36 1015411 Infini
37 1015415 534
38 1015420 43
39 1015421 48
40 1015425 4 432
41 1015450 53
42 1015451 48
43 1015455 67
44 1040010 54
45 1040012 296
46 1040020 1 660
47 1040022 970
48 1040050 71
49 1040052 102
50 1040101 289
51 1040102 97
52 1040105 110
53 104015 57
54 1040510 1 545
55 1040512 569 804
56 1040521 1 020
57 1040524 10 795
58 1040550 451
59 1040555 451
60 1042010 918 339
61 1042015 Inconnu, supérieur à 5,2×1019
62 1042020 57 493 855 205 939
63 1042022 57 493 855 205 905
64 104205 Infini
65 1042110 631
66 1042115 118
67 1042120 2 056
68 1042122 747
69 1042150 5 865
70 1042155 398
71 1042501 1 550
72 1042502 130
73 1042505 153
74 1042521 2 754
75 1042522 196
76 1042525 122
77 1044001 Infini
78 1044002 Infini
79 1044005 46
80 1044011 Infini
81 1044012 Infini
82 1044015 212
83 1044051 330
84 1044052 Infini
85 1044055 138
86 1044201 Infini
87 1044202 Infini
88 1044205 17 859
89 104421 Infini
90 1044251 347
91 1044252 Infini
92 1044255 73
93 1051 28
94 1054 28
95 120012 110
96 1200141 247
97 1200142 309
98 1200145 181
99 1200412 Infini
100 1200414 711
101 1200422 5 132
102 1200424 345
103 1200452 1 515
104 1200454 839
105 1200521 304
106 1200522 354
107 1200525 631
108 1200541 3 943
109 1200542 201
110 1200545 237
111 1202 Infini
112 1204141 176
113 1204142 735
114 1204145 92
115 120415 57
116 1204412 415
117 1204414 Infini
118 120442 Infini
119 1204454 2 578
120 1204455 2 578
121 12045 Infini
122 121401 48
123 1214041 77
124 1214042 609
125 1214045 114
126 1214051 22 847
127 1214052 Infini
128 1214055 134
129 121421 29
130 1214241 105
131 1214242 7 882
132 1214245 45
133 1214251 281
134 1214252 62
135 1214255 152
136 1214411 Infini
137 1214412 48
138 1214415 48
139 121444 Infini
140 121445 Infini
141 121510 33
142 121512 99
143 121514 48
144 1215401 151
145 1215402 42
146 1215405 53
147 1215421 2 526
148 1215422 2 857
149 1215425 561
150 121544 33
151 12155 28
152 1251 48
153 1252101 220 142
154 1252104 7 584
155 1252105 9 260
156 1252121 Inconnu, supérieur à 2,2×1016
157 1252124 2 565
158 1252125 731
159 1252141 553
160 1252144 173
161 1252145 Infini
162 12522 Infini
163 1252501 248
164 1252504 236
165 1252505 101
166 1252521 1 063
167 1252524 162
168 1252525 86
169 1252541 514
170 1252544 1 116
171 1252545 738
172 1420011 83
173 1420012 81
174 1420015 94
175 1420041 Infini
176 1420042 897
177 1420045 285
178 1420051 90
179 1420052 73
180 1420055 697
181 1420211 Infini
182 1420214 Infini
183 1420215 Infini
184 1420221 Infini
185 1420224 16 811 365 528
186 1420225 284
187 142025 34
188 142041 90
189 1420441 50
190 1420442 Infini
191 1420445 1 688
192 1420451 4 419
193 1420452 3 566
194 1420455 496
195 142101 29
196 1421041 50
197 1421042 248
198 1421045 39
199 1421051 73
200 1421052 5 715
201 1421055 Infini
202 1421211 33
203 1421214 219
204 1421215 79
205 1421221 23
206 1421224 3 793
207 1421225 46
208 1421251 29
209 1421254 52
210 1421255 Infini
211 1421411 Infini
212 1421412 29
213 1421415 35
214 142144 Infini
215 142145 Infini
216 14251 48
217 14252 Infini
218 14255 44
219 1450011 83
220 1450012 81
221 1450015 94
222 1450041 Infini
223 1450042 897
224 1450045 285
225 1450051 90
226 1450052 73
227 1450055 697
228 1450211 Infini
229 1450214 Infini
230 1450215 Infini
231 1450221 Infini
232 1450224 16 811 365 528
233 1450225 284
234 145025 34
235 145041 90
236 1450441 50
237 1450442 Infini
238 1450445 1 688
239 1450451 4 419
240 1450452 3 566
241 1450455 496
242 145101 29
243 1451041 50
244 1451042 248
245 1451045 39
246 1451051 73
247 1451052 5 715
248 1451055 Infini
249 1451211 33
250 1451214 219
251 1451215 79
252 1451221 23
253 1451224 3 793
254 1451225 46
255 1451251 29
256 1451254 52
257 1451255 Infini
258 1451411 Infini
259 1451412 29
260 1451415 35
261 145144 Infini
262 145145 Infini
263 14551 48
264 14552 Infini
265 14555 44
266 150011 50
267 150015 33
268 1500411 196
269 1500415 69
270 1500421 732
271 1500425 159
272 1500451 78
273 1500455 45
274 15005 Infini
275 150111 33
276 150115 29
277 1501411 55
278 1501412 71
279 1501415 44
280 1501451 140
281 1501452 113
282 1501455 119
283 1501511 1 672
284 1501515 10 307
285 1501521 Infini
286 1501525 165
287 1501551 134
288 1501555 112
289 1505111 52 549
290 1505115 Infini
291 1505141 1 632
292 1505145 1 632
293 1505151 1 978
294 1505155 5 148
295 1505211 419
296 1505215 1 564
297 1505241 4 371
298 1505245 7 143
299 1505251 454
300 1505255 306
301 1505511 62
302 1505514 130
303 1505515 55
304 1505551 636
305 1505554 206
306 1505555 242
307 1520 Infini
308 152111 33
309 152115 29
310 1521411 148
311 1521415 247
312 1521421 393
313 1521425 113
314 1521451 136
315 1521455 132
316 1521511 623
317 1521515 2 377
318 1521521 176
319 1521525 1 742
320 1521551 152
321 1521555 112
322 1525111 534
323 1525115 Inconnu, supérieur à 4,5×1015
324 1525121 356
325 1525125 606
326 1525151 533
327 1525155 287
328 1525411 2 754
329 1525412 Infini
330 1525415 126
331 1525451 5 708
332 1525452 Infini
333 1525455 338
334 1525511 83 618
335 1525515 1 574
336 1525521 7 275
337 1525525 843
338 1525551 262
339 1525555 286
340 1541011 194
341 1541012 294
342 1541015 180
343 1541051 354
344 1541052 107
345 1541055 708
346 154111 Infini
347 1541121 48
348 1541125 114
349 1541151 48
350 1541155 58
351 1541511 2 811
352 1541515 663
353 1541521 Infini
354 1541525 Infini
355 1541551 245
356 1541555 321
357 1544101 Infini
358 1544102 Infini
359 1544105 45 477
360 154411 Infini
361 1544151 558
362 1544152 Infini
363 1544155 7 565
364 1544501 Infini
365 1544502 Infini
366 1544505 512
367 1544511 Infini
368 1544512 Infini
369 1544515 1 457
370 1544551 4 802
371 1544552 Infini
372 1544555 138
373 1545 Infini
374 200 9
375 2010 15
376 20140 30
377 201412 45
378 2014141 609
379 2014142 3 563 608 205
380 2014144 615
381 201415 37
382 20142 27
383 2015 Infini
384 2104 12
385 2105 21
386 2144 18
387 21450 63
388 2145121 438
389 2145122 438
390 2145124 411
391 2145141 2 478
392 2145142 87 996 218
393 2145144 2 373
394 214515 68
395 21452 48
396 215 Infini
397 244 9
398 2450 15
399 24540 30
400 245412 45
401 2454141 609
402 2454142 3 563 608 205
403 2454144 615
404 245415 37
405 24542 27
406 2455 Infini
407 2510 12
408 2514 18
409 2515 Infini
410 2540 12
411 2544 18
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,‎ novembre 1973, p. 116-123