 A finite-state machine whose only tape is a FIFO queue of unbounded length, such that in each transition the machine reads the symbol at the head of the queue, deletes a constant number of symbols from the head, and appends to the tail a symbol-string that depends solely on the first symbol read in this transition. https://en.wikipedia.org/wiki/Tag_system 5 comments
@fbry Yeah stacks in subleq is a bit less jumping around than say a register machine, but it's pretty slow. Lambda Calculus style graph reduction is more fun for simple systems to handle stacks, especially if operators are linear. What I linked up top is a queue machine, which is pretty interesting, implementing one in subleq is trickier tho, two pointers at once in a ring-buffer. @fbry Subleq emulation is fun, here's one I wrote in just a few lines in a pure stack machine language: https://git.sr.ht/~rabbits/uxn/tree/main/item/projects/examples/exercises/subleq.tal @neauoire Neat! Mine is in C++. I started converting it over to pure C a while ago and never got around to finishing it.  @neauoire Since a Post tag machine as originally defined only halts when the FIFO is empty (_if_ that happens), is it able to provide any useful output? Or do you have to define a halt symbol to get that? |
Gregory's Server
@neauoire I've been thinking about how stack machines could be used to implement an efficient programming language on top of one-instruction set machines like SUBLEQ.
This might be another way to approach it, though I need to get my SUBLEQ emulator running again.
https://en.wikipedia.org/wiki/One-instruction_set_computer#Subtract_and_branch_if_less_than_or_equal_to_zero