Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)

This Wikipedia table (template for "Formal languages and grammars") maps grammar to language to abstract machine for more than a dozen languages.

http://en.wikipedia.org/wiki/Template:Formal_languages_and_grammars

But I miss another relation: Lambda calculus (that can be described syntactically as a certain context free grammar) has the same computational strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore the correspondence between abstract programming languages and automata further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)

Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this further by asking this question.

Are there any similar equivalences between a calculus and an automaton, especially for finite state machines, and pushdown automata? (Other examples welcome.)

Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this further by asking this question.

Are there any similar equivalences between a calculus and an automaton, for finite state machines, and pushdown automata, to start with? (Other examples welcome.)

Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this further by asking this question.

Are there any similar equivalences between a calculus and an automaton, like for finite state machines, or pushdown automata? (Other examples welcome.)

Lambda calculus has the same strength as a Turing machine. I somehow see this as functional programming (LC) vs imperative programming; but as I don't trust my intuition here, I want to explore this further by asking this question.

Are there any similar equivalences between a calculus and an automaton, especially for finite state machines, and pushdown automata? (Other examples welcome.)