4 ms·
> Because there is one aspect of Turing’s model that makes it more useful: Universal Turing Machines (UTM’s). > Universal Turing Machines The idea of UTM’s is
by tromp 3y ago
> Because there is one aspect of Turing’s model that makes it more useful: Universal Turing Machines (UTM’s).
> Universal Turing Machines
The idea of UTM’s is that you can have Turing Machines running other Turing Machines.
Just like you can have lambda terms running other lambda terms [1] [2]. In fact an additvely optimal [3] universal lambda term can be as simple as
┬─┬ ────────────────────────────────────────────────────┬─┬── ┬────────
└─┤ ────────────────────────────────────────────────────┼─┼─┬ │ ┬─┬ ┬─┬
│ ┬───────────────────────────────────────────────────┼─┼─┼ │ └─┤ ├─┘
│ │ ──┬────────────────────────────────────────────── ├─┘ │ │ ├─┘
│ │ ┬─┼─────────────────────────────────────────────┬ │ │ ├───┘
│ │ ┼─┼─┬─────────────┬───────────────────┬─────────┼ │ │ │
│ │ ┼─┼─┼───┬─────────┼─┬───────────┬─────┼─┬───────┼ │ │ │
│ │ │ ┼─┼─┬─┼─────────┼─┼─────────┬─┼───┬─┼─┼─────┬─┼ │ │ │
│ │ │ │ │ ┼─┼─┬───────┼─┼─┬────── │ │ ┬─┼ ┼─┼─────┼─┼ │ │ │
│ │ │ │ │ │ │ ┼─────┬ │ ┼─┼───┬── │ │ ├─┘ │ ┼─┬───┼ │ │ │ │
│ │ │ │ │ │ │ ┼───┬─┼ │ │ ┼─┬─┼─┬ │ ├─┘ │ │ ┼─┬─┼ │ │ │ │
│ │ │ │ │ │ │ │ ┬─┼─┼ │ │ └─┤ ├─┘ └─┤ │ │ │ ├─┘ │ │ │ │
│ │ │ │ │ │ │ │ └─┤ │ │ │ ├─┘ │ │ │ ├─┘ │ │ │ │
│ │ │ │ │ │ │ │ ├─┘ │ ├───┘ │ │ ├─┘ │ │ │ │
│ │ │ │ │ │ │ ├───┘ ├─┘ │ └─┤ │ │ │ │
│ │ │ │ │ │ ├─┘ │ │ ├───────┘ │ │ │
│ │ │ │ │ └─┤ │ ├───────┘ │ │ │
│ │ │ │ │ ├─────────┘ │ │ │ │
│ │ │ │ ├───┘ │ │ │ │
│ │ │ └─┤ │ │ │ │
│ │ │ ├───────────────────────────┘ │ │ │
│ │ ├───┘ │ │ │
│ └─┤ │ │ │
│ └─────────────────────────────────────────────────┤ │ │
│ ├───┘ │
└─────────────────────────────────────────────────────┤ │
└─────┘
in the graphical notation of [3], while an additively optimal TM would be monstrously complex. In that regard, Turing Machines are no more useful than the lambda calculus.
[1] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#lambda-encoding https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
[2] https://rosettacode.org/wiki/Universal_Lambda_Machine https://rosettacode.org/wiki/Universal_Lambda_Machine
[3] https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d861#universality https://gist.github.com/tromp/86b3184f852f65bfb814e3ab0987d8...
[4] https://tromp.github.io/cl/diagrams.html https://tromp.github.io/cl/diagrams.html
- gavinhoward 3y agoYes, but as I said to another commenter, Turing's model helped people think differently.
- tromp 3y agoYes, Turing machines have advantages. But having universal machines is not one of them.
- LegionMammal978 3y agoI'm confused by your 'additively optimal' definition. Suppose that the objects we want to describe are strings of bits, and the description method D is just "listing the bits out in a sequence". Then surely no BLC term can describe the same sequence of bits with only a constant amount of overhead.
- tromp 3y agoThen D is just identity, or λ 1, using only 4 bits of overhead?!
- LegionMammal978 3y agoIf a 'description' of an 'object' is defined to always be a valid term or program that operates on provided input, then I don't see why Turing machines wouldn't nearly as easily be 'additively optimal' in your sense. For most universal Turing machines that represent an input bit as a constant-sized word (such as Neary & Woods' 8-state 4-symbol UTM [0], which represents each input bit as two symbols, or even their 15-state 2-symbol UTM [1], which uses a slightly trickier encoding), you could add a few states extra to expand new input on the fly, shifting any existing data to the left as necessary. The only precondition is that the existing data has a boundary recognizable by a finite-state machine; this condition can always be met with O(n) extra states by adding an extra symbol to the UTM's description to represent the boundary, then converting it back to a 2-symbol machine. Regardless, I'd still consider your 'additively optimal' to be a strange definition, given that BLT programs get to have their input bits pre-expanded as a valid sequence of boolean terms for free. If all it means is that the input format accepted by D is a subset of the input format accepted by U, then many existing small UTMs could easily meet it just by restricting D's input format. [0] https://doi.org/10.1016/j.tcs.2006.06.002 https://doi.org/10.1016/j.tcs.2006.06.002 [1] https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_2009.pdf https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_...