I am looking for bounds - both lower and upper - on the time, spacial, and state/symbol (i.e. number of states and symbols required) complexity of simulating the (untyped) λ-calculus with a queue machine (roughly speaking, a pushdown automaton with the stack replaced by a (n unbounded) queue).

It is easy to emulate a tag system with a queue machine, and relatively easy to emulate a 1-tape Turing machine with a queue machine, albeit with quadratic time overhead.

As such, I know that it can be done (you can simulate a 1-tape Turing machine with a stack machine in quadratic time and O(1) space overhead, worst case, and simulate untyped λ-calculus with a Turing machine with I-have-no-clue time and space overhead). I am wondering about the complexity bounds.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.