- Ver de Paterson
-
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].
Sommaire
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 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
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.
- 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
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
Liens internes
Liens externes
- (en) Paterson's Worms
- (en) Paterson's Worms Revisited
Références
- ↑ (en) Martin Gardner, « Mathematical Games: Fantastic patterns traced by programmed "worms" », dans Scientific American, vol. 229, novembre 1973, p. 116-123
Catégories : Automate cellulaire | Calculabilité
Wikimedia Foundation. 2010.
