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 manycore 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 welldefined 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 nondeterministic Turing Machine has bounded nondeterminism (i.e. there is a bound on the size of integer that can be computed starting on a blank tape by an alwayshalting machine). Proving that a server will actually provide service to its clients depends on unbounded nondeterminism. That's why the semantics of CSP were reversed from bounded nondeterminism [Hoare CSP 1978] to unbounded nondeterminism [Hoare CSP 1985]. See the article at: What is computation? Concurrency versus Turing's Model By Hewitt at 20101123 19:04  LtU Forum  previous forum topic  next forum topic  other blogs  11940 reads

Browse archivesActive forum topics 
Recent comments
2 days 3 hours ago
3 days 8 hours ago
3 days 8 hours ago
3 days 9 hours ago
3 days 9 hours ago
3 days 22 hours ago
4 days 7 hours ago
5 days 8 hours ago
5 days 13 hours ago
5 days 18 hours ago