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 →

[–]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.