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.
