7
$\begingroup$

If Turing Machines are the automata equivalent of the $\lambda$ calculus, what is the automaton equivalent of the $\pi$ calculus? I suppose it would be some class of automata that resembled a Turing Machine, but with support for communication channels or signals of some type, but I'm not sure, and would appreciate some direction.

$\endgroup$
  • $\begingroup$ I think (labelled) transition systems are commonly thought of as equivalent. Classic automata/language theory does not really apply since we don't build acceptors here. $\endgroup$ – Raphael Jul 5 '13 at 8:18
  • $\begingroup$ @Raphael, would you please elaborate on your second sentence? $\endgroup$ – BlueBomber Jul 5 '13 at 19:41
  • 1
    $\begingroup$ @BlueBomber Would you be able to elaborate your question a little bit? In what sense are TMs the "automata equivalent of the $\lambda$-calculus"? Expressive power? Then $\pi$-calculus is the same as $\lambda$-calculus and TMs. Automata with channels for interaction are process calculi. $\endgroup$ – Martin Berger Jul 6 '13 at 13:57
  • $\begingroup$ @Martin Berger, we learn in unversity that the lambda calculus and Turing machines are equivalent with respect to computing power, which is probably what you refer to by expressive power, but it isn't what I mean. As far as I can tell, there is no way in either the lambda calculus or Turing machines to express "wait for signal on channel c before continuing". The pi calculus has that, and so do modern computers (and I understand that it doesn't necessarily increase the power/expressiveness of the system in a formal sense). $\endgroup$ – BlueBomber Jul 6 '13 at 16:58
  • 1
    $\begingroup$ @BlueBomber As I pointed out in my answer to this question, Turing machines can express waiting for a channel, but the modelling tends to be inconvenient, e.g. you need to encode channels, signals etc as certain strings that you put on tape. If you want more convenience, you have to go to calculi that models the features you want explicitly. There are many, e.g. interacting TMs, CCS, CSP and $\pi$ calculi. $\endgroup$ – Martin Berger Jul 7 '13 at 10:07
-1
$\begingroup$

The question doesnt make too much sense because the $\pi$-calculus was proven Turing complete, or in other words equivalent to a Turing machine ever since its inception by Milner in 1992. There is a reference on Wikipedia.

$\endgroup$
  • $\begingroup$ I read in the linked article that there is an embedding of the Lambda calculus into Pi calculus. The other direction is not mentioned. $\endgroup$ – Falko Sep 24 '14 at 18:55
-1
$\begingroup$

Turing Machines are to the λ-calculus as Chemical Abstract Machines are to the π-calculus.

Basically, a Chemical Abstract Machine is modeled as a set of molecules that, on each process step, some subset of the molecules react, are consumed by the reaction, and produce new molecules.

$\endgroup$
  • $\begingroup$ Could you give us some more details? A link to a paper or at least a paper reference (author/paper-name/journal/date)? It would be most helpful if you could tell us a little bit about how the features of Chemical Abstract Machines relate to the features of the $\pi$-calculus. $\endgroup$ – Wandering Logic Sep 29 '13 at 2:32
  • $\begingroup$ I don't see either how this analogy works. While $\pi$-calculus has a natural CHAM formulation, the connection between TMs and $\lambda$-calculus is complicated and torturous. $\endgroup$ – Martin Berger Sep 29 '13 at 13:39
  • $\begingroup$ @WanderingLogic The founding paper for the CHAM is The Chemical Abstract Machine by G. Berry and G. Boudol. IIRC Milner used the CHAM for the first time in Functions as Processes to explain the $\pi$-calculus. $\endgroup$ – Martin Berger Sep 29 '13 at 13:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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