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