User loginNavigation |
What is computation? Concurrency versus Turing's ModelConcurrency is of crucial importance to the science and engineering of computation in part because of the rise of the Internet and many-core architectures. However, concurrency extends computation beyond the conceptual framework of Church, Gandy [1980], Gödel, Herbrand, Kleene [1987], Post, Rosser, Sieg [2008], Turing, etc. because there are effective computations that cannot be performed by Turing Machines. In the Actor model [Hewitt, Bishop and Steiger 1973; Hewitt 2010], computation is conceived as distributed in space where computational devices communicate asynchronously and the entire computation is not in any well-defined state. (An Actor can have information about other Actors that it has received in a message about what it was like when the message was sent.) Turing's Model is a special case of the Actor Model. A Turing Machine can enumerate all the possible executions of a closed system even though it cannot perform them individually. For example, the integers are recursively enumerable even though a non-deterministic Turing Machine has bounded non-determinism (i.e. there is a bound on the size of integer that can be computed starting on a blank tape by an always-halting machine). Proving that a server will actually provide service to its clients depends on unbounded non-determinism. That's why the semantics of CSP were reversed from bounded non-determinism [Hoare CSP 1978] to unbounded non-determinism [Hoare CSP 1985]. See the article at: What is computation? Concurrency versus Turing's Model By Hewitt at 2010-11-23 19:04 | LtU Forum | previous forum topic | next forum topic | other blogs | 18599 reads
|
Browse archives
Active forum topics |
Recent comments
25 weeks 3 days ago
25 weeks 3 days ago
25 weeks 3 days ago
47 weeks 4 days ago
51 weeks 6 days ago
1 year 1 week ago
1 year 1 week ago
1 year 4 weeks ago
1 year 8 weeks ago
1 year 8 weeks ago