# Talk by Wilfried Sieg

**Venue:**

Room 302, INF, Neubrückstrasse 10, 3012 Bern

**Speaker**

Prof. Dr. Wilfried Sieg (Carnegie Mellon University)

**Title:**

What is the *concept* of computation?

**Abstract:**

The Church-Turing Thesis asserts that particular mathematical notions are adequate to represent informal notions of *effective calculability* or *mechanical decidability*. I first sketch contexts that called for such adequate mathematical notions, namely, problems in mathematics (e.g., Hilbert’s 10th problem), decision problems in logic (e.g., the *Entscheidungsproblem* for first-order logic), and the precise characterization of formality (for the general formulation of Gödel’s incompleteness theorems).

The classical approach to the *effective calculability* of number theoretic functions led, through Gödel and Church, to a notion of computability in logical calculi and metamathematical *absoluteness theorems*. The classical approach to the *mechanical decidability* of problems concerning syntactic configurations led, through Turing and Post, to a notion of computability in formal calculi (canonical systems) and metamathematical *representation theorems*.

Particular features of formal calculi motivate the formulation of an abstract concept of a *computable dynamical system*. This concept articulates finiteness and locality conditions that are satisfied by the standard concrete notions of computation. A representation theorem can be established: Turing machines can simulate the computations of any concrete system falling under the abstract concept. I sketch a generalization of this approach to obtain *computable parallel dynamical systems*. Some applications will conclude my discussion.

- Log in to post comments