Vers de Paterson

{{#invoke:Bandeau|ébauche}}

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<ref name="gardner" />.

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

Voir aussi

Liens internes

• Automate cellulaire
• Fourmi de Langton
• Turmite

Liens externes

• {{#invoke:Langue|indicationDeLangue}} Paterson's Worms Revisited

Références

<references> <ref name="gardner">Modèle:Article</ref> <ref name="rokicki">Modèle:Lien web</ref> </references>