5 ms·
"You can reduce any program to either a Turing machine or the lambda calculus" Can you easily reduce a program with concurrency to either of these? If not then
by discreteevent 10y ago
"You can reduce
any program to either a Turing machine or the lambda calculus"
Can you easily reduce a program with concurrency to either of these? If not then you are leaving out a large class of programs and systems. I think this is why Milner invented the pi calculus (a calculus of objects)
- mafribe 10y agoConcurrency (understood as message-passing concurrency) is much more expressive than either OO or FP. Milner invented pi-calculus because its predecessor (CCS) was not expressive enough. One example of the lack of expressivity is that the encoding of Turing machines into CCS is quite awkward, whereas the encoding into pi-calculus is smooth. Still, pi-calculus has expressivity limits, e.g. n-way synchronisation (n > 2) a la Petri nets cannot be encoded in a compositional way, and neither can broadcasting or Ambient-calculus mobility.