Re: I'm confused: Turing machine model vs. interactivity

Jamie Andrews; real address @ bottom of message wrote:
qt88717@xxxxxxxxx wrote:
Could someone please point me to literature or terminology that
explains how interactivity like this fits in with all the Turing
machine-style theory?

Some people have argued that process algebras, like
Milner's CCS and Hoare's CSP, are a more realistic foundation
for computing than Turing or von Neumann machines, because
process algebras are inherently interactive. I believe the
papers by Wegner that have been referred to by others discuss
process algebras.

Process algebras are certainly an approach towards a theory of
interaction in computation, and (as far as I know) the richest or
furthest developed approach theory-wise, but they are not the only
approach. Two more general keywords are "concurrency" (or concurrent
systems) and "reactive systems". Under these you will find Petri nets,
temporal logic, various notations consisting of interacting state
machines, and so on.

A typical process algebra consists of
- a language for describing systems, and
- a semantic theory that abstracts away the unessential internal
details of the behaviour of a system.

Because of history and inertia in the research communities, the
languages and semantic theories tend to be linked: CSP has its own
semantic models that are mathematically and content-wise quite different
from the semantic models seen in connection with CCS. However, they need
not be linked like this. One may apply CCS-like semantics to the CSP
language or vice versa (some fine-tuning is needed in the details), and
this has been done for long. Failure to realize this has caused a lot of
unnecessary confusion.

A process-algebraic language is somewhat comparable to the regular
expressions, while the semantics is comparable to the formal language
described by a regular expression. However, both the language and the
semantics are typically much richer than regular expressions and their
formal languages, and there are indeed many alternative semantics with
different properties. There is an intermediate formalism that
corresponds to finite automata, namely labelled transition systems
(LTS). I personally find the language of secondary importance and
usually work at the level of LTSs. However, I, too, must use some
operators to compose systems from their components.

In process algebras, interaction is synchronous: the interacting
components execute some transition (action, computation step)
simultaneously, as if "hand in hand". The CCS language is restricted to
two-way synchronisation, but CSP and some others allow arbitrarily many
simultaneous partners. It turns out that input and output are special
roles in synchronous interaction, and they are not always meaningful
(like "night" is meaningful on earth but not in space). It has turned
out that most, probably all, other forms of interaction can be built
from process-algebraic synchronous interaction easily, while the
opposite is not the case. So synchronous interaction seems
"fundamental".

Process-algebraic languages typically allow the use of local variables
and computation with them (usually in the functional style). One can
think of there being a "socket" in which one can plug any formalism that
is capable of describing relations between the values of the variables
before the transition, values communicated with the neighbouring
components during the transition, and the values of the variables after
the transition. Often the relation is a partial function that takes the
"before"-values and some of the communicated values (those that the
component in question inputs) and produces the "after"-values and the
rest of the communicated values. When the partial function is not
defined, it is said that the corresponding transition is not enabled.

Turing machines are a general formalism for describing computation of
partial functions, and also relations. However, the way the
above-mentioned relation is specified and whether it is computable are
not important for process algebras (at least as I see them). Process
algebras just take it and continue with it. If one is interested in
computability issues in this context, then Turing machines may be *the*
choice, but the core of process algebraic theories is not there.

One can thus think of process algebras as orthogonal to Turing machines,
or as an upper layer that employs some mechanism --- like Turing
machines --- for describing sequential computation and provides
concurrent computation. I would not call process algebras more general
than Turing machines. They do entirely different tasks. Both tasks are
relevant to understand modern computing systems.

What I wrote above is more or less "in the air" in the process algebra
community --- not much have been written, although I believe that most
of those who have bothered to think these issues probably more or less
agree with me. The link below is to an attempt to explicate these
issues.

slides: http://www.cs.tut.fi/~ava/ait05slide.pdf
paper: http://www.cs.tut.fi/ohj/VARG/publications/05-4.pdf

--- Antti Valmari ---
.

Relevant Pages