4 ms·

A better Turing machine tape model

23 points by nickdrozd 5y ago

thethirdone 5y ago
> 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.
a-dub 5y ago
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?
ogogmad 5y ago
This is a summary of what the article says: 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) https://en.wikipedia.org/wiki/Zipper_(data_structure)
fjfaase 5y ago
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 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)
- cube2222 5y ago
  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-automaton-with-two-stacks-equivalent-to-a-turing-machine https://cs.stackexchange.com/questions/2832/is-a-push-down-a...
galaxyLogic 5y ago
Interesting. Are there actual physical working Turing machines anywhere? Can I buy one?
- bowmessage 5y ago
  Here's one physical example: https://www.youtube.com/watch?v=E3keLeMwfHY https://www.youtube.com/watch?v=E3keLeMwfHY
- blueflow 5y ago
  No, so far, mankind hasn't figured out how to construct the infinite tape part of it.
drpixie 5y ago
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.
- vidarh 5y ago
  This is about how to represent that compactly in an implementation, not trying to replace the high level abstraction.
  - thegrasshopper2 5y ago
    Then the title is wrong
mettamage 5y ago
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.
kd5bjo 5y ago
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 https://en.wikipedia.org/wiki/SKI_combinator_calculus
raldi 5y ago
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.
- bruce343434 5y ago
  Haskell (inspect element of the code blocks reveals highlighting metadata)
  - thethirdone 5y ago
    I am pretty sure it is actually Idris based on the interface and implementation keywords.

23 points by nickdrozd 5y ago

> 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.

a-dub 5y ago

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?

ogogmad 5y ago

This is a summary of what the article says: 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) https://en.wikipedia.org/wiki/Zipper_(data_structure)

fjfaase 5y ago

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 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)

cube2222 5y ago
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-automaton-with-two-stacks-equivalent-to-a-turing-machine https://cs.stackexchange.com/questions/2832/is-a-push-down-a...

galaxyLogic 5y ago

Interesting. Are there actual physical working Turing machines anywhere? Can I buy one?

bowmessage 5y ago
Here's one physical example: https://www.youtube.com/watch?v=E3keLeMwfHY https://www.youtube.com/watch?v=E3keLeMwfHY
blueflow 5y ago
No, so far, mankind hasn't figured out how to construct the infinite tape part of it.

drpixie 5y ago

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.

vidarh 5y ago
This is about how to represent that compactly in an implementation, not trying to replace the high level abstraction.
- thegrasshopper2 5y ago
  Then the title is wrong

mettamage 5y ago

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.

kd5bjo 5y ago

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 https://en.wikipedia.org/wiki/SKI_combinator_calculus

raldi 5y ago

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.

bruce343434 5y ago
Haskell (inspect element of the code blocks reveals highlighting metadata)
- thethirdone 5y ago
  I am pretty sure it is actually Idris based on the interface and implementation keywords.