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. • a paradigm change – Bridging the gap between concurrency theory (labeled transition systems) and traditional TOC. • 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! Google “autonomous vehicle research” 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 • Answering Machine (AM) 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 - queries/updates to single-user databases - 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) • Example: simulating Answering Machine (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 adjacent processes may execute 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 after the change is made. [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

Descargar
# Modeling Interactive Computation: Turing Machines or