Fully universal Turing machine: Difference between revisions
Jump to navigation
Jump to search
Stub |
PokaLukaWan (talk | contribs) added bounding box and cell count (when the machine has no program) |
||
| (13 intermediate revisions by 4 users not shown) | |||
| Line 1: | Line 1: | ||
{{Pattern | {{Pattern | ||
|name = Fully universal Turing machine | |name = Fully universal Turing machine | ||
|pname = fullyuniversalturingmachine | |||
|c = 692013 | |||
|bx = 81157 | |||
|by = 81133 | |||
|symmetry = C1 | |||
|discoverer = Paul Rendell | |discoverer = Paul Rendell | ||
|discoveryear = 2011 | |discoveryear = 2011 | ||
| | |zip = true | ||
}} | }} | ||
The '''fully universal Turing machine''' is an extension of [[Paul Rendell]]'s [[universal Turing machine]]. Its tape is perfectly diagonal (instead of oblique), and the memory cells of the tape are produced by two complex [[ | The '''fully universal Turing machine''' is an extension of [[Paul Rendell]]'s [[universal Turing machine]]. Its tape is perfectly diagonal (instead of oblique), and the memory cells of the tape are continuously produced by two complex [[rake]] convoys. Rendell experimented with three different variants of this mechanism: | ||
* A [[c/12 diagonal]] stack constructor using [[Cordership]] | * A [[c/12 diagonal]] stack constructor using [[Cordership]]-based rakes (very large); | ||
* A [[c/5 diagonal]] stack constructor using [[Matthias Merzenich]]'s [[c/5 diagonal rake]]s; | * A [[c/5 diagonal]] stack constructor using [[Matthias Merzenich]]'s [[c/5 diagonal rake]]s; | ||
* An expanding stack constructor comprising two perpendicular [[c/2 orthogonal]] convoys of | * An expanding stack constructor comprising two perpendicular [[c/2 orthogonal]] convoys of rakes (the final version). | ||
== | {{POTY|name=The fully universal Turing machine|year=2011|rank=1|tie=the [[Lobster]]}} | ||
== | {| class="wikitable" style="width:425px" | ||
*[http://rendell-attic.org/gol/fullutm/index.htm A Fully Universal Turing Machine] - Official site by Paul Rendell | |[[File:Fullyuniversalturingmachine1.png]]{{br}}The initial UTM state. The dotted line going NW is the program for the stack.<ref name="utm1" /> | ||
|- | |||
|[[File:Fullyuniversalturingmachine2.png]]{{br}}After 149 million generations. The line running SE in the middle is the trace of each address of the finite state machine and is very sparse. The distance this line has moved from the stack is related to the time that [[Golly]] was running after the UTM stopped. The length of this line is related to the time the UTM was running.<ref name="utm1" /> | |||
|} | |||
== See also == | |||
* [[Turing machine]] | |||
* [[Universal computer]] | |||
* [[Universal constructor]] | |||
== References == | |||
<references> | |||
<ref name="utm1">[http://rendell-attic.org/gol/fullutm/index.htm A Fully Universal Turing Machine] - Official site by Paul Rendell</ref> | |||
</references> | |||
Latest revision as of 20:23, 10 April 2025
| Fully universal Turing machine | |||||
| |||||
| View static image | |||||
| Pattern type | Miscellaneous | ||||
|---|---|---|---|---|---|
| Number of cells | 692013 | ||||
| Bounding box | 81157 × 81133 | ||||
| Static symmetry | C1 | ||||
| Discovered by | Paul Rendell | ||||
| Year of discovery | 2011 | ||||
| |||||
The fully universal Turing machine is an extension of Paul Rendell's universal Turing machine. Its tape is perfectly diagonal (instead of oblique), and the memory cells of the tape are continuously produced by two complex rake convoys. Rendell experimented with three different variants of this mechanism:
- A c/12 diagonal stack constructor using Cordership-based rakes (very large);
- A c/5 diagonal stack constructor using Matthias Merzenich's c/5 diagonal rakes;
- An expanding stack constructor comprising two perpendicular c/2 orthogonal convoys of rakes (the final version).
The fully universal Turing machine was voted Pattern of the Year for 2011 on the ConwayLife.com forums, tied with the Lobster.[1]
 The initial UTM state. The dotted line going NW is the program for the stack.[2] |
 After 149 million generations. The line running SE in the middle is the trace of each address of the finite state machine and is very sparse. The distance this line has moved from the stack is related to the time that Golly was running after the UTM stopped. The length of this line is related to the time the UTM was running.[2] |
See also
References
- ↑ beebop (February 28, 2012). Patterns of the Year 2011 (discussion thread) at the ConwayLife.com forums
- ↑ 2.0 2.1 A Fully Universal Turing Machine - Official site by Paul Rendell