Short-Course: Thinking, Computing, Thinking

Orador: Wilfried Sieg (Carnegie Mellon University)

Título do mini-curso: "Thinking, Computing, Thinking"

Local: Sala de seminários, ed. VII, FCT-UNL

(NB: O mini-curso é constituído por 4 palestras **independentes**.)

16/10/2017 (2a), 14h (Seminário): "Mechanical procedures - What is the concept of computation?"

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 canonical systems 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.

17/10/2017 (3a), 14h: "Natural deduction in bi-directional ways"

20/10/2017 (6a), 13h: "Natural formalization - The Cantor-Bernstein Theorem derived in ZF"

23/10/2017 (2a), 14h: "Automated search for Gödel's Theorems"