2
$\begingroup$

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.)

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ See this post about the equivalence of Büchi automata with linear $\mu$-calculus. $\endgroup$
    – Shaull
    Commented Sep 23, 2014 at 15:47
  • $\begingroup$ It's just an observation, actually: we have grammars, automata and logics for many of the major classes. Not always are all equally handy or neatly characterised, but they exist. Note how such equivalences (always!) carry over to subclasses. Therefore, once you have equivalent models for TMs, similar models have to exist for all weaker models. (However nastily characterised.) $\endgroup$
    – Raphael
    Commented Sep 23, 2014 at 20:19
  • $\begingroup$ I do think it is an interesting question, though probably naively asked. I do not think I am competent, but here is my feeling. Lambda-calculus is a calculus, i.e. an operational device. That is also true of TM and other automata, but is is equally true of grammars, when considered, as is often the case, as rewriting systems. These are all formal ways of computing with syntactic representations. But there are other readings, and more interesting dualities such as operational and denotational readings. For example, Grammars may be read as languages equations. CC @Raphael $\endgroup$
    – babou
    Commented Sep 23, 2014 at 20:48
  • 3
    $\begingroup$ To kick you off, even Wikipedia lists some models equivalent to NFA. Are such what you are after? $\endgroup$
    – Raphael
    Commented Sep 23, 2014 at 21:04

1 Answer 1

Reset to default
1
$\begingroup$

As I said, I am not sure how to answer your question.

However, given the current rephrasing of it, it finally rung a memory bell. I think that, starting sometime in the 1970's, people have been studying what they called program schemes.

A set of slides (in French) I found on the web seems to give a historical perspective on the subject.

Slide 14 is about Iterative program schemes, corresponding to Regular sets. They correspond to computational structures of the form X=f(X,Y) and Y=a, which are only a functional version of iteration loops.

Slide 15 is about Recursive program schemes, corresponding to Algebraic (also known as Context-Free) languages. They correspond to more complex recursive computation structure, using a stack memory as in early recursive programming langages.

I am not certain that is the kind of correspondance you are looking for, as it correspond (as much as I remember) to the computing power of uninterpreted programs, i.e. the structural aspects of the computationq. But it may be worth reading.

There are many more references, including fairly recent ones, if you serach the web with: "program schemes".

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thank you babou! As I mentioned, I'm a newbie, so it will take me some time to find out whether this is the answer I hoped for. I'm reading .. $\endgroup$
    – Falko
    Commented Sep 25, 2014 at 18:25

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.