A better Turing machine tape model(nickdrozd.github.io)
nickdrozd.github.io
A better Turing machine tape model
https://nickdrozd.github.io/2021/12/31/turing-machine-tape.html
16 comments
> And that’s it! The Scan ‘n’ Span model is dramatically simpler than the pointer model. As an added bonus, it’s also way faster on account of not needing to bother with constant array-indexing and bounds-checking.
I believe there should be an asterisk saying "in Idris". I don't believe this method removes any extra bounds checking or array-indexing at the assembly level.
I completely agree that in functional programing a dual list method makes more sense than an index into a list. I wouldn't be surprised if the compiler just optimizes better with the more functional code.
> Instead of a list, a single number can be used as a span. Implement Tape (ScanNSpan Nat). (Hint: this amounts to a sort of Gödel numbering.)
If you can restrict the `Color` to a finite set (which is necessary for any turing machine), you can just use multiplication and division which should be vastly faster than encoding based on primes.
I believe there should be an asterisk saying "in Idris". I don't believe this method removes any extra bounds checking or array-indexing at the assembly level.
I completely agree that in functional programing a dual list method makes more sense than an index into a list. I wouldn't be surprised if the compiler just optimizes better with the more functional code.
> Instead of a list, a single number can be used as a span. Implement Tape (ScanNSpan Nat). (Hint: this amounts to a sort of Gödel numbering.)
If you can restrict the `Color` to a finite set (which is necessary for any turing machine), you can just use multiplication and division which should be vastly faster than encoding based on primes.
right but, wouldn't a "better" turing machine be one that is somehow easier to reason about in the abstract or otherwise prove properties about rather than one that can be simulated faster or has simpler simulation implementation?
Rather misses the whole point of Turing's machine - it was the SIMPLEST machine he could devise that could be said to "calculate".
Turning never made and never intended to make such a machine - it's a mathematical abstraction.
All calculation that could be performed on Turning's most simple machine, can also be performed by all equivalent or better machines. The point of Turing's machine is that as long as your fancy new device can model that minimal behavior, your device can be said to calculate and all conclusions about computability apply to your device.
Turning never made and never intended to make such a machine - it's a mathematical abstraction.
All calculation that could be performed on Turning's most simple machine, can also be performed by all equivalent or better machines. The point of Turing's machine is that as long as your fancy new device can model that minimal behavior, your device can be said to calculate and all conclusions about computability apply to your device.
This is about how to represent that compactly in an implementation, not trying to replace the high level abstraction.
Then the title is wrong
I wonder if this is new. Some weeks ago Nick Drozd, who found a new 4 color, 2 state BLB TM, used this in combination with another optimization (a counter for repeated cells with the same color). This was reported on HN: https://news.ycombinator.com/item?id=29888388. To analyze this TM, I made an implementation in C++. (See my home page for the details.)
(Edit: Added name and link to HN article)
(Edit: Added name and link to HN article)
It's not new, at least not as far as the theory goes. This model is basically how the standard proof goes that pushdown automata with two stacks are equal in power to a Turing Machine.
Here's for example a stackexchange answer from 2012 using this: https://cs.stackexchange.com/questions/2832/is-a-push-down-a...
Here's for example a stackexchange answer from 2012 using this: https://cs.stackexchange.com/questions/2832/is-a-push-down-a...
Can’t find it anymore but there was a whole wiki page on what Turing machines you could have.
I once was working with an xml-like language and asking myself if it was turing complete. You could create scores in that language which were basically integer variables.
The trick is to then only have 0 and 1 as a valid alphabet. That meant that an integer can be represented as a stack of 0’s and 1’s. Add another integer and now you have two stacks.
You could also make a Turing Machine just by using prime numbers.
I once was working with an xml-like language and asking myself if it was turing complete. You could create scores in that language which were basically integer variables.
The trick is to then only have 0 and 1 as a valid alphabet. That meant that an integer can be represented as a stack of 0’s and 1’s. Add another integer and now you have two stacks.
You could also make a Turing Machine just by using prime numbers.
To show the Turing-completeness of a functional programming language, it's usually easier to implement the S and K combinators [1] than to directly implement a Turing machine.
[1] https://en.wikipedia.org/wiki/SKI_combinator_calculus
[1] https://en.wikipedia.org/wiki/SKI_combinator_calculus
Interesting. Are there actual physical working Turing machines anywhere? Can I buy one?
No, so far, mankind hasn't figured out how to construct the infinite tape part of it.
Here's one physical example: https://www.youtube.com/watch?v=E3keLeMwfHY
What's the language being used here to define the interface? I don't understand what's intended by terms like "Nat" or "Fin" or "**" or "->" and don't see any link to documentation or even a name I can google.
Haskell (inspect element of the code blocks reveals highlighting metadata)
I am pretty sure it is actually Idris based on the interface and implementation keywords.
To represent the tape of a Turing Machine, you need a doubly linked list. In imperative languages, it's obvious how to implement doubly linked lists efficiently and simply, but in functional languages it's not. The author proposes using two stacks to represent a doubly linked list in a functional language: The first stack is for the part of the list to the left of the current node, and the second stack is for the part of the list to the right of the current node (including the current node). A generalisation of this idea for representing doubly-linked data structures in functional programming is called a Zipper [1].
[1] - https://en.wikipedia.org/wiki/Zipper_(data_structure)