Die Würmer Paterson sind eine Reihe von Turing-Maschinen . Sie wurden 1971 von John Conway und Mike Paterson kreiert und 1973 von Martin Gardner in einem Artikel in Scientific American populär gemacht .
Im Allgemeinen sind Patersons Würmer eine Art Turmtit , der an den Rändern eines hexagonalen isometrischen Gitters definiert ist.
In Anbetracht eines unendlichen dreieckigen Gitters betrachten wir einen der Knoten dieses Gitters als einen „Wurm“. Der Wurm bewegt sich zunächst entlang einer Gitterlinie zum Knoten unmittelbar rechts davon.
An diesem Knoten angekommen, kann der Wurm fünf mögliche Richtungen einschlagen, ohne seine Schritte zurückzuverfolgen. Wir gehen davon aus, dass der Wurm einen von ihnen nimmt, entsprechend zum nächsten Knoten vorrückt und dies auch weiterhin tut, solange er auf einem Knoten ankommt, auf dem fünf Richtungen möglich sind:
In den letzten beiden Fällen muss unter den vier möglichen eine Richtung definiert werden, die der Wurm einschlagen wird. Dann gehen wir zu jedem Knoten wie folgt vor:
Bei der Ankunft an einem Knoten hat der Wurm fünf mögliche Richtungen. Wir notieren "0" das, was vor ihm liegt (relativ zu seiner Ankunftsrichtung), "1" und "5" diejenigen, die sich 60 ° rechts und links davon befinden, "2" und "4" diejenigen die bei 120 ° zu seiner Rechten und zu seiner Linken sind. Die Notation "3" entspricht der Richtung, aus der sie kommt, und kann daher nicht verwendet werden.
Wir bestimmen dann den Verlauf eines Wurms, indem wir die verschiedenen Entscheidungen notieren, die wir getroffen haben. Somit dreht sich der "244" -Wurm in den ersten 3 Umdrehungen um 120 ° nach rechts, dann um 120 ° nach links, dann wieder um 120 ° nach rechts für 2 Umdrehungen und dann um 120 ° nach links. Nachdem der Wurm in den letzten 2 Umdrehungen um 120 ° nach rechts gedreht wurde, kehrt er ohne neue Richtung zum Startknoten zurück und stoppt.
Es gibt nur 412 verschiedene mögliche Regeln (wobei die Regeln, die in Bezug auf den Start symmetrisch zueinander sind, als eine einzige Regel betrachtet werden). Unter ihnen :
Hier ist eine Liste möglicher Regeln für das Verhalten eines Paterson-Wurms:
# | Regel | Anzahl der Schritte |
---|---|---|
1 | 0 | Unendlich |
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, |
fünfzehn | 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 | Unendlich |
30 | 1015205 | Unendlich |
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 | Unendlich |
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 | Unbekannt, größer als 5,2 × 10 19 |
62 | 1042020 | +57 493 855 205 939, |
63 | 1042022 | +57 493 855 205 905, |
64 | 104205 | Unendlich |
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 | Unendlich |
78 | 1044002 | Unendlich |
79 | 1044005 | +000.000.000.00046, |
80 | 1044011 | Unendlich |
81 | 1044012 | Unendlich |
82 | 1044015 | +00.000.000.000212, |
83 | 1044051 | +00.000.000.000330, |
84 | 1044052 | Unendlich |
85 | 1044055 | +00.000.000.000138, |
86 | 1044201 | Unendlich |
87 | 1044202 | Unendlich |
88 | 1044205 | +000.000.00017 859, |
89 | 104421 | Unendlich |
90 | 1044251 | +00.000.000.000347, |
91 | 1044252 | Unendlich |
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 | Unendlich |
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 | Unendlich |
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 | Unendlich |
118 | 120442 | Unendlich |
119 | 1204454 | +0.000.000.0002,578, |
120 | 1204455 | +0.000.000.0002,578, |
121 | 12045 | Unendlich |
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 | Unendlich |
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 | Unendlich |
137 | 1214412 | +000.000.000.00048, |
138 | 1214415 | +000.000.000.00048, |
139 | 121444 | Unendlich |
140 | 121445 | Unendlich |
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 | Unbekannt, größer als 2,2 × 10 16 |
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 | Unendlich |
162 | 12522 | Unendlich |
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 | Unendlich |
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 | Unendlich |
182 | 1420214 | Unendlich |
183 | 1420215 | Unendlich |
184 | 1420221 | Unendlich |
185 | 1420224 | +00016 811 365 528, |
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 | Unendlich |
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 | Unendlich |
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 | Unendlich |
211 | 1421411 | Unendlich |
212 | 1421412 | +000.000.000.00029, |
213 | 1421415 | +000.000.000.00035, |
214 | 142144 | Unendlich |
215 | 142145 | Unendlich |
216 | 14251 | +000.000.000.00048, |
217 | 14252 | Unendlich |
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 | Unendlich |
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 | Unendlich |
229 | 1450214 | Unendlich |
230 | 1450215 | Unendlich |
231 | 1450221 | Unendlich |
232 | 1450224 | +00016 811 365 528, |
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 | Unendlich |
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 | Unendlich |
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 | Unendlich |
258 | 1451411 | Unendlich |
259 | 1451412 | +000.000.000.00029, |
260 | 1451415 | +000.000.000.00035, |
261 | 145144 | Unendlich |
262 | 145145 | Unendlich |
263 | 14551 | +000.000.000.00048, |
264 | 14552 | Unendlich |
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 | Unendlich |
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 | Unendlich |
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 | Unendlich |
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 | Unendlich |
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 | Unbekannt, größer als 4,5 × 10 15 |
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 | Unendlich |
330 | 1525415 | +00.000.000.000126, |
331 | 1525451 | +0.000.000.0005,708, |
332 | 1525452 | Unendlich |
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 | Unendlich |
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 | Unendlich |
354 | 1541525 | Unendlich |
355 | 1541551 | +00.000.000.000245, |
356 | 1541555 | +00.000.000.000321, |
357 | 1544101 | Unendlich |
358 | 1544102 | Unendlich |
359 | 1544105 | +000.000.00045,477, |
360 | 154411 | Unendlich |
361 | 1544151 | +00.000.000.000558, |
362 | 1544152 | Unendlich |
363 | 1544155 | +0.000.000.0007,565, |
364 | 1544501 | Unendlich |
365 | 1544502 | Unendlich |
366 | 1544505 | +00.000.000.000512, |
367 | 1544511 | Unendlich |
368 | 1544512 | Unendlich |
369 | 1544515 | +0.000.000.0001,457, |
370 | 1544551 | +0.000.000.0004,802, |
371 | 1544552 | Unendlich |
372 | 1544555 | +00.000.000.000138, |
373 | 1545 | Unendlich |
374 | 200 | +0.000.000.000.0009, |
375 | 2010 | +000.000.000.000fünfzehn, |
376 | 20140 | +000.000.000.00030, |
377 | 201412 | +000.000.000.00045, |
378 | 2014 141 | +00.000.000.000609, |
379 | 2014 142 | +0.0003,563,608,205, |
380 | 2014144 | +00.000.000.000615, |
381 | 201415 | +000.000.000.00037, |
382 | 20142 | +000.000.000.00027, |
383 | 2015 | Unendlich |
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, |
393 | 2145144 | +0.000.000.0002.373, |
394 | 214515 | +000.000.000.00068, |
395 | 21452 | +000.000.000.00048, |
396 | 215 | Unendlich |
397 | 244 | +0.000.000.000.0009, |
398 | 2450 | +000.000.000.000fünfzehn, |
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, |
403 | 2454144 | +00.000.000.000615, |
404 | 245415 | +000.000.000.00037, |
405 | 24542 | +000.000.000.00027, |
406 | 2455 | Unendlich |
407 | 2510 | +000.000.000.00012, |
408 | 2514 | +000.000.000.00018, |
409 | 2515 | Unendlich |
410 | 2540 | +000.000.000.00012, |
411 | 2544 | +000.000.000.00018, |
412 | 2545 | Unendlich |