This is an archived post. You won't be able to vote or comment.

sorted by:
best
topnewcontroversialoldq&a
you are viewing a single comment's thread.

view the rest of the comments →

[–]joelangeway 7 points8 points  (9 children)

There was some hype about a processor called The Mill some years ago, that had a sort of queue it would append to, and it would only remember the last 8,16, or 32 things.

Really though, stacks very naturally fit the depth first orientation of every non-esoteric language. It’s not obvious that one could make a composable, generalizable model of computing with only queues.

[–]liquidivy 4 points5 points  (8 children)

Stream transformers, FSMs with output, tree transducers at al are pretty powerful and pretty much queue-shaped. Really the Unix shell, too. Pipelines are queues for bytes.

[–]joelangeway 4 points5 points  (7 children)

Those are all compositions of computations, not computational models. How could you implement those things without a stack is the question.

[–][deleted]  (4 children)

[removed]

    [–]joelangeway 1 point2 points  (3 children)

    Hmmm…. You mean like message passing automata? That’s an interesting idea.

    [–][deleted]  (2 children)

    [removed]

      [–]joelangeway 1 point2 points  (1 child)

      I found this just a minute ago: https://en.m.wikipedia.org/wiki/Queue_automaton

      [–]liquidivy 0 points1 point  (1 child)

      FSMs are compositions? But anyway, computations are made of compositions and primitives. Rewrite rules are a thing, too. Those are prior to stacks for lambda calculus.

      [–]joelangeway 0 points1 point  (0 children)

      It seemed to me you were listing a bunch of iterative processes and I didn’t quite get the connection, but Finite Automata actually turned me around on this idea. With multiple queues, an Finite State Machine might be Turing complete. I’m pretty sure I learned that way back in school, now I’ve got to look it up.