```Interaction:
Conjectures, Results, and Myths
Dina Goldin
Univ. of Connecticut, Brown University
http://www.cse.uconn.edu/~dqg
7 June 2005
CWI
1
Fundamental Questions
Underlying Theory of Computation
What is computation?
How do we model it?
7 June 2005
CWI
2
Shared Wisdom
(from undergraduate Theory of Computation courses)
computation: finite transformation
of input to output
input: finite size (e.g. string or
number)
Mathematical worldview:
All computable problems
are function-based.
closed system: all input available
at start, all output generated at end
behavior: functions, transformation of
input data to output data
Church-Turing thesis: Turing
Machines capture this (algorithmic)
notion of computation
7 June 2005
CWI
3
The Operating System
Conundrum
If a computation
does not terminate,
it’s “useless” –
but aren’t OS’s
useful??
Real programs… often receive an unbounded amount of input over
time, and never "finish" their task. Turing machines do not model
such ongoing computation well.
[TM entry, Wikipedia]
7 June 2005
CWI
4
Outline
• Rethinking the mathematical worldview
–
–
–
–
•
•
•
•
•
Historical perspective
Algorithmic vs. interactive computation
Wegner’s conjecture
Driving home from work
Persistent Turing Machines (PTMs)
PTM expressiveness
Sequential Interaction Thesis
The Myth of the Church-Turing Thesis
Future work
7 June 2005
CWI
5
The Mathematical Worldview
“The theory of computability and non-computability [is] usually
referred to as the theory of recursive functions... the notion of TM has
been made central in the development."
Martin Davis, Computability & Unsolvability, 1958
“Of all undergraduate CS subjects, theoretical computer science has
changed the least over the decades.”
SIGACT News, March 2004
“A TM can do anything that a computer can do.”
Michael Sipser, Introduction to the Theory of Computation, 1997
7 June 2005
CWI
6
Rethinking Shared Wisdom:
(what do computers do?)
computation: ongoing process which
computation: finite
transformation of input to output performs a task or delivers a service
input: finite-size (string or number) dynamically generated stream of input
tokens (requests, percepts, messages)
open system: later inputs depend on
closed system: all input available at
earlier outputs and vice versa (I/O
start, all output generated at end
entanglement, history dependence)
behavior: functions, algorithmic
transformation of input data to
output data
behavior: processes, components,
control devices, reactive systems,
intelligent agents
Church-Turing thesis: Turing
Machines capture this (algorithmic)
notion of computation
Turing Machines do not capture this
(interactive) notion of computation
7 June 2005
CWI
7
Modeling Interactive Computation
• Many interactive models
– Reactive [MP] and embedded systems
– Dataflow, I/O automata [Lynch], synchronous languages, finite/pushdown
automata over infinite words
– Interaction games [Abramsky], online algorithms [Albers]
– TM extensions: on-line Turing machines [Fischer], interactive Turing
machines [Goldreich]
• Concurrency Theory
– Focuses on communication (between concurrent agents/processes) rather
than computation [Milner]
– Orthogonal to the theory of computation and TMs.
• What makes our approach unique?
– Communication (I/O) is part of computation.
– Bridging the gap between concurrency theory (labeled transition systems)
• models borrow from both fields
– Focus on expressiveness
• rather than mere convenience of modeling
7 June 2005
CWI
8
Our Motivation
Wegner’s Conjecture:
Interaction is more powerful
than algorithms
[CACM’97]
7 June 2005
CWI
9
Example:
Driving home from work
Algorithmic input: a description of the world (a static “map”)
Output: a sequence of pairs of #s (time-series data)
- for turning the wheel
- for pressing gas/break
Similar to classic AI search/planning problems.
7 June 2005
CWI
10
Can you get the car
into my driveway
without running
over my kid?
7 June 2005
CWI
11
Driving home from work (cont.)
But… in a real-world environment, the output depends
on every grain of sand in the road (chaotic behavior).
?
Can we possibly have a map that’s detailed enough?
Worse yet… the domain is dynamic. The output
depends on weather conditions, and on other drivers and
pedestrians.
We can’t possibly be expected to predict that in advance!
Nevertheless the problem is solvable!
7 June 2005
CWI
12
Driving home from work (cont.)
The problem is solvable interactively.
Interactive input: stream of video camera images, gathered
as we are driving
Output: the desired time-series data, generated
as we are driving
similar to control systems, or online computation
A paradigm shift in the conceptualization of computational problem solving.
7 June 2005
CWI
13
Outline
• Rethinking the mathematical worldview
• Persistent Turing Machines (PTMs)
– extending N3TM computations model
– Persistent Stream Languages
– examples
• PTM expressiveness
• Sequential Interaction Thesis
• The Myth of the Church-Turing Thesis
• Future work
7 June 2005
CWI
14
Three-tape Turing Machines
(N3TM)
s - current state
w1 - contents of input tape
w2 - contents of work tape
w3 - contents of output tape
n1 , n2 , n3 - tape head posns
input
work
S
output
• N3TM configurations:
 s , w1 , w 2 , w 3 , n1 , n 2 , n 3 
• Computation = a sequence of transitions between
configurations, from initial to halting.
7 June 2005
CWI
15
N3TM macrosteps
 < sh, win, w’, wout, 1, 1, 1 >
< s0, win, w, e, 1, 1, 1 > |
So
Notation:
7 June 2005
win
win
w
w’
e
Sh
wout
 win, w  M  w’, wout 
CWI
16
Extending N3TM Computations
S0
in1
in1
in2
in2
e
w1
w1
w2
e
Sh
out1
S0
e
Sh
...
out2
• Dynamic stream semantics
- Inputs are streams of dynamically generated tokens (strings).
- For each input token, there is an N3TM macrostep generating the
corresponding output token.
• Persistence (memory)
- The contents w of the work tape at the beginning of each macrostep
is the same as at the end of the previous one.
7 June 2005
CWI
17
Persistent Turing Machine (PTM)
PTM: N3TM with persistent stream-based
computational semantics
Interaction Stream
PTM
stream of inputs
memory
stream of outputs
...
Environment
• Persistent Stream Language of a PTM: set of streams
{  in 1 , out 1  ,  in 2 , out 2  ,...}
• Conductive stream semantics:
S  (  *   *)  S
7 June 2005
CWI
18
Formal Definition
(Coinductive definition, relative to N3TM M and memory w)
PSL(M(w)) = { (wi, wo), s’  S | \$w’S*:
 wi , w    w ' , wo  
s ' PSL ( M ( w ' ))}
PSL ( M )  PSL ( M ( e ))
PSL equivalenc e :
M 1  PSL M 2
PSL = { PSL(M) | M is a PTM}
7 June 2005
CWI
19
PTM Example
fAM(record Y, X) = (ok, XY)
fAM(erase, X) = (done, e)
fAM(playback, X) = (X, X)
– PSL(AM) contains:
(record hello, ok), (erase, done) , (record Farhad, ok),
(record Arbab, ok) , (playback, Farhad Arbab), …
– Sequential objects as PTMs
7 June 2005
CWI
20
More PTM Examples
• PowerPoint Editor
– Input: mouse movements, keyboard clicks
– Output: refreshed view of presentation
• Driving Agent
7 June 2005
CWI
21
PTM Example: Latch
• At each step, output first bit of
previous step.
–
–
–
–
inputs in1; outputs 1
inputs in2; outputs 1st bit of in1
inputs in3; outputs 1st bit of in2
...
(1*,1)
#
• PSL(Latch) contains:
{( 1,1), ( 0 ,1), ( 0 , 0 ), (1, 0 ),...}
1
(1*,0)
(0*,1)
(0*,1)
(1*,1)
0
(0*,0)
• PTM as a Labeled Transition System
– Latch has 3 states, meaning “contents of worktape”
– The labels are input/output pairs, as in the interaction stream.
7 June 2005
CWI
22
Outline
• Rethinking the mathematical worldview
• Persistent Turing Machines (PTMs)
• Interactive Transition Systems
– Different notions of equivalence
– Correspondence to PTMs
• Sequential Interaction Thesis
• The Myth of the Church-Turing Thesis
• Future work
7 June 2005
CWI
23
Interactive Transition Systems
over S
(1*,1)
< S, m, r >
• S is set of states
• r is initial state (root)
• m is transition relation
#
1
(1*,0)
(0*,1)
(0*,1)
(1*,1)
0
(0*,0)
m  S   * S   *
Required to be recursively enumerable
7 June 2005
CWI
24
Interactive Stream
Equivalence
• Infinite sequences of input/output token-pairs
emanating from a particular ITS state
• ISL(T), the interactive stream language of an ITS
T, is the set of all such sequences emanating from
T’s root.
T1 =ISL T2 if ISL(T1) = ISL(T2)
7 June 2005
CWI
25
ITS Isomorphism
Let T1, T2 be ITSs
Ti  S i ,  , m i , ri 
T1  iso T 2 if \$ bijection  : S 1  S 2
s.t.
1.  ( r1 )  r2
2.  w i , w o   *, s , s ' S 1 :
 s , w i , s ' , w o  m 1 iff
  ( s ), w i ,  ( s ' ), w o  m 2
7 June 2005
CWI
26
ITS Bisimulation
Ti  S i ,  , m i , ri  be ITSs, i=1,2
R  S 1  S 2 is a (strong) interactive bisimulation if:
Let
1.
r1 R r2
2.
s R t   s , w i , s ' , w o   m 1  \$ t ' s.t.
 t , wi , t ' , wo   m 2  s ' R t '
3. Clause 2. with roles of s and t reversed
R is defined recursively, has greatest fixpoint semantics
T1 =bisim T2
7 June 2005
if
\$
an interactive bisim. between them
CWI
27
Comparing Equivalence
Relations
=1 is strictly finer than =2 if
(x =1 y) implies (x =2 y)
but not vice-versa
=ISL  =bisim  =iso
Equivalent machines = same behavior
Equivalence classes = set of distinct behaviors
7 June 2005
CWI
28
From PTMs to ITSs
Reachable memories of a PTM M:
reach(M)   *
Set of words (work-tape contents) w encountered
after zero or more macrosteps.
ξ(M)   reach(M), m, e 
where
 s , wi , s ' , wo m iff wi , s  M  s' , wo
ξ is a bijection between PTMs and ITSs [I&C’04]
7 June 2005
CWI
29
Theorem:
The structures
 M ,  ms  and  T ,  iso 
are isomorphic
Proof:
structure - preserving : M 1  ms M
2
iff
 ( M 1 )  iso  ( M 2 )
(set the  for  iso to the  for  ms )
onto :  T  T , \$ M  M : T   ( M )
( m is recursive;
7 June 2005
choose
CWI
the obvious
M)
30
PTMs vs. ITSs
PTMs
=PSL
=ms
ITSs
=ISL  =bisim  =iso
Two representation of the same computational behavior
7 June 2005
CWI
31
Outline
•
•
•
•
Rethinking the mathematical worldview
Persistent Turing Machines (PTMs)
Interactive Transition Systems
PTM expressiveness
– Infinite equivalence hierarchy
• Equivalence hierarchy gap
– Unbounded nondeterminism and divergence
– Amnesic PTMs
• It pays to be persistent
• Sequential Interaction Thesis
• Future work
7 June 2005
CWI
32
Infinite Equivalence Hierarchy
• Lk(M) = stream prefix language of PTM M
set of prefixes of length  k for streams in PSL(M)
represents finite observations of M (testing equivalence)
• L∞(M) = Uk≥1 Lk(M)
• Corresponding notions of equivalence:
M1 =k M2 : Lk(M1) = Lk ( M2 )
M1 =∞ M2 : L∞ (M1) = L∞ ( M2 )
• =1 is like Turing Machine equivalence
7 June 2005
CWI
33
Infinite Equivalence Hierarchy
(cont)
=1  =2 
...

=∞

=PSL
More equivalence classes = more distinct behaviors
What is your
name?
A deterministic
machine
7 June 2005
CWI
34
Equivalence Hierarchy Gap
=1  =2
...
=  =PSL
• Proof: construct PTMs M1 and M2 where
L(M1) = L (M2 ) but PSL (M1 ) ≠ PSL (M2 )
• Note: M1 exhibits unbounded nondeterminism
• Unbounded nondeterminism implies divergence. [I&C 2004]
7 June 2005
CWI
35
Proof Details
• M1 produces output streams of the form 1*0+
On 1st macrostep, initializes a persistent string n of 1’s:
while true do
write ‘1’ on the work tape, move head to the right;
nondeterministically choose to exit loop or continue
The output at every macrostep is determined as follows:
if n > 0
then decrement n by 1 and output ‘1’;
else output ‘0’
• M2 is the same, but also produces the stream 1*
• M1 , M2 exhibit unbounded non-determinism
7 June 2005
CWI
36
Divergent Computation
sdiv
(S*, t)
(S*, t)
e
M1
(S*, 1)
(S*, 1)
(S*, 1)
(S*, 1)
...
(S*, 1)
(S*, 0)
n=0
(S*, 1)
n=1
(S*, 1)
n=2
(S*, 1)
n=3
...
(S*, 1)
Theorem: If a PTM M has unbounded
nondeterminism, then M diverges. [I&C’04]
7 June 2005
CWI
37
Amnesic PTM Computation:
stream-based but not persistent
ASL ( M )  {  ( w i , w o ), s '  S | \$ w   * :
 wi , e    w', wo  
s ' PSL( M ( w' ))}
ASL equivalenc e :
M 1  ASL M 2
ASL = { ASL(M) | M is a PTM}
PTM M is amnesic if PSL(M)  ASL
7 June 2005
CWI
38
Amnesic PTMs:
“half-way” between TMs and PTMs
S0
in1
in1
in2
in2
e
w1
e
w2
e
Sh
out1
S0
e
Sh
...
out2
• Amnesic PTMs extend TMs with stream-based semantics.
At least as expressive as TMs
• Unlike PTMs, they lack persistence.
Example: squaring machine (outi = ini2)
[Prasse & Rittgen]
7 June 2005
CWI
39
It Pays to be Persistent
Two arguments that PTMs are more expressive
than Amnesic PTMs:
1. Collapse of the equivalence hierarchy.
=1 =
=PSL
2. Smaller set of stream languages.
ASL
7 June 2005

PSL
CWI
40
Summary of Results
ASL
=TM
[I&C’04]
 PSL
=
PTMs
=1  =2
...
=  =PSL
=ms
ITSs
=ISL  =bisim  =iso
7 June 2005
CWI
41
Outline
•
•
•
•
•
Rethinking the mathematical worldview
Persistent Turing Machines (PTMs)
Interactive Transition Systems
PTM expressiveness
Sequential Interaction
– Sequential Interaction Thesis
– Universal PTMs
– Church-Turing Thesis revisited
• Future work
7 June 2005
CWI
42
Sequential Interaction
• Sequential interactive computation:
system continuously interacts with its environment
by alternately accepting an input string
and computing a corresponding output string.
• Examples:
- method invocations of an object instance
in an OO language
- a C function with static variables
- recurrent neural networks
7 June 2005
CWI
- control systems
- online computation
- transducers
- dynamic algorithms
- embedded systems
43
Sequential Interaction Thesis
Whenever there is an effective method for performing
sequential interactive computation, this computation
can be performed by a Persistent Turing Machine
• Universal PTM: simulates any other PTM
– Need additional input describing the PTM (only once)
(simulate AM, will-do),
(record hello, ok), (erase, done), (record Farhad, ok),
(record Arbab, ok), (playback, Farhad Arbab), …
Simulation of other sequential interactive systems is analogous.
7 June 2005
CWI
44
Origins of the Church-Turing Thesis Myth
A TM can do anything that a computer can do.
Based on several claims:
1. A problem is solvable if there exists a Turing Machine
for computing it.
2. A problem is solvable if it can be specified by an algorithm.
3. Algorithms are what computers do.
Each claim is correct in isolation
provided we understand the underlying assumptions
Together, they induce an incorrect conclusion
TMs = solvable problems = algorithms = computation
7 June 2005
CWI
45
Deconstructing the Turing Thesis Myth (1)
TMs = solvable problems
• Assumes:
All computable problems are function-based.
• Reasons:
– Theory of Computation started as a field of mathematics;
mathematical principles were adopted for the fundamental
notions of computation, identifying computability with the
computation of functions, as well as with Turing Machines.
– The batch-based modus operandi of original computers did
not lend itself to other conceptualizations of computation.
7 June 2005
CWI
46
Deconstructing the Turing Thesis Myth (2)
solvable problems = algorithms
Assumes:
- Algorithmic computation is also function based;
i.e., the computational role of an algorithm
is to transform input data to output data.
• Reasons:
– Original (mathematical) meaning of “algorithms”
E.g. Euclid’s greatest common divisor algorithm
– Original (Knuthian) meaning of “algorithms”
“An algorithm has zero or more inputs, i.e., quantities which are
given to it initially before the algorithm begins.“
[Knuth’68]
7 June 2005
CWI
47
Deconstructing the Turing Thesis Myth (3)
algorithms = computation
• Reasons:
– The ACM Curriculum (1968): Adopted algorithms as the central
concept of CS without explicit agreement on the meaning of this term.
– Textbooks: When defining algorithms, the assumption of their closed
function-based nature was often left implicit, if not forgotten
“An algorithm is a recipe, a set of instructions or the specifications
of a process for doing something. That something is usually solving
a problem of some sort.”
[Rice&Rice’69]
“An algorithm is a collection of simple instructions for carrying out
some task. Commonplace in everyday life, algorithms sometimes
are called procedures or recipes...”
[Sipser’97]
7 June 2005
CWI
48
Church-Turing Thesis Revisited
•
Church-Turing Thesis:
Whenever there is an effective method
for obtaining the values of a mathematical function,
the function can be computed by a Turing Machine
• Common Reinterpretation (Strong Church-Turing Thesis)
A TM can do (compute) anything that a computer can do
• The equivalence of the two is a widespread myth
the function-based behavior of algorithms does not
capture all forms of computation
• Turing himself would have denied it
in the same paper where he introduced what we now call Turing
Machines, he also introduced choice machines, as a distinct
model of computation
choice machines extend Turing Machines to interaction by
allowing a human operator to make choices during the
computation.
7 June 2005
CWI
49
Outline
• Rethinking the mathematical worldview
• Persistent Turing Machines (PTMs)
• Interactive Transition Systems
• PTM expressiveness
• Sequential Interaction
• Future work
7 June 2005
CWI
50
Future Work: 3 conjectures
• Theory of Sequential Interactiove Computation
This is a robust notion of computation, admitting
notions analogous to computational complexity,
logic, and recursive functions
• Where are the ports? -- Multi-stream interaction
multi-stream interaction is more powerful than
sequential interaction [Wegner’97]
• Formalizing indirect interaction
direct interaction (via message passing) does not
capture all forms of multi-agent behaviors
7 June 2005
CWI
51
Direct & Indirect Interaction
DIRECT INTERACTION: interaction via message passing.
• Known as “communication” in concurrency theory.
• ID of destination agent specified in the message.
INDIRECT INTERACTION: interaction via persistent,
observable changes to the common environment.
• Agents can affect each other without interacting directly, when one of them
makes changes to their environment that the other later observes.
• Example: multi-user document editing, stigmergy.
7 June 2005
CWI
52
Role of the Environment
in Indirect Interaction
• The environment is the medium of communication.
• It must be changeable and observable: when one agent
changes it, another can observe the change.
• It must be persistent: change to it remain, so they can be
observed later.
• It may posess locality: given an agent, parts of the
environment are accessible to it while others are not (may
be different parts for actuating & sensing).
May be very simple (Dining Philosophers example)
or complex (Foraging Ants example)
7 June 2005
CWI
53
Dining Philosophers
• Classic problem in concurrency
and shared resources: define a
protocol for a ring-shaped
arrangement of processes
(philosophers) where no two
simultaneously.
• Goal: let the philosophers carry
on while avoiding starvation.
• Starvation: all philosophers
pick up one chopstick and wait
to pick up the other.
• Mobile version: philosophers
may leave table when sleepy, or
join at empty place when ready
to eat and think.
7 June 2005
CWI
Indirect Interaction:
philosophers interact with neighbors
(persistent observable change to
environment = picking up and
putting down chopsticks).
Direct Interaction:
philosophers interact with chopsticks
(modeled as simple processes).
54
Foraging Ants
• Classic problem in artificial life
and stigmergy.
• Ants wander randomly looking for
sources of food.
• If they find food, they leave
behind a phermone trail (or
reinforce existing one).
• Or, if they find a phermone trail,
they follow it in search of food.
• Achieves coordination without
centralization.
• An example of swarm computing,
and of emergent behavior.
7 June 2005
CWI
Indirect Interaction:
ants interact with each other
(persistent observable change to
environment = phermone trails).
Direct Interaction:
?
55
Properties of Indirect Interaction (1)
Dining Philosophers
Foraging Ants
Late binding of recipient
(anonymity)
Identity of the observer of given
state changes may be determined
by dynamic events occurring
[mobile] The chopstick
X puts down will be
picked up either by X or
by who-ever happens to
be sitting next to X at
the time they get
hungry.
X’s pheromone trail
will be detected by
whoever happens to
wander past it.
Time decoupling (asynchrony)
There may be a delay between
the change and its observation,
whose duration may be
determined by dynamic events.
There may be a delay
after X puts down a
chopstick before it’s
picked up again; cannot
know when the neighbor
will get hungry.
There may be a delay
after X puts down
pheromone before it’s
detected; cannot know
when someone will
wander by to detect it.
Space Decoupling
Indirect interaction need not
imply co-location (for mobile
agents); first agent may leave
after making changes, second
arriving later.
[mobile] X may go
away after putting down
chopstick; when Y picks
it up, he interacts with X
without ever being in
the same location.
Ants who lay down
and pick up a
pheromone trail
usually do not actually
meet each other.
7 June 2005
CWI
56
Properties of Indirect Interaction (2)
Dining Philosophers
Localization
Agents may be restricted to
make/ observe changes in only
a part of the shared space (that
is local to them).
Foraging Ants
A philosopher can
pick up / put down
only the chopsticks
next to him.
An ant can leave or
sense pheromones
only in its local
neighborhood.
Non-intentionality
Intent to communicate is not
required, nor awareness that
communication is occurring; agents
may simply be doing their own task.
X puts down
chopsticks because
he is done, NOT
because she wants
others to know that
they can eat.
X leaves pheromones
because he is
programmed to do
this when carrying
food, not out of
intent to notify
others.
Hybrid nature
The real world may serve as the
medium of indirect interaction; the
system will involve real-world
processes, and will be hybrid rather
than fully digital.
[analog] X will not
eat with dirty
chopsticks (where
the notion of
dirtiness is fuzzy).
Pheromones
evaporate over time.
7 June 2005
CWI
57
Ubiquity of Indirect Interaction
• Social Biology: Social insects living in colonies interact
indirectly by making changes to common structures (termite
piles) or through pheromones.
• Operating Systems: Processes exchange information via
semaphores in shared memory
• Programming Languages: Tuple spaces in Linda enable
coordination by indirect interaction.
• Anatomy: Cells exchange information via hormones in the
blood stream.
• Economics: the value of stocks, bonds, and currency acts as
medium of interaction between buyers and sellers as they
negotiate prices.
7 June 2005
CWI
58
Formalizing Indirect Interaction
• There is a need for a formalization of indirect
interaction that
– models its properties explicitly, without the intermediate
protocol layer
– directly reflects problem semantics (i.e. chopsticks are passive
objects, not active agents)
– is domain-independent
– allows for real world as medium of interaction
– extends existing models of interaction (Persistent Turing
Machines)
• Conjecture
– decentralized coordination in multiagent systems of simple
agents requires indirect interaction (to provide asynchrony and
anonymity)
7 June 2005
CWI
59
References
http://www.cse.uconn.edu/~dqg/papers/
[Wegner’97] Peter Wegner
Why Interaction is more Powerful than Algorithms
Communications of the ACM, May 1997
[EGW’04] Eugene Eberbach, Dina Goldin, Peter Wegner
Turing's Ideas and Models of Computation
book chapter, in Alan Turing: Life and Legacy of a Great Thinker, Springer
2004
[I&C’04] Dina Goldin, Scott Smolka, Paul Attie, Elaine Sonderegger
Turing Machines, Transition Systems, and Interaction
Information & Computation Journal, 2004
[GW’04] Dina Goldin, Peter Wegner
The Church-Turing Thesis: Breaking the Myth
presented at CiE 2005, Amsterdam, June 2005
to be published in LNCS
7 June 2005
CWI
60
Questions?
7 June 2005
CWI
61
```