Universiteit van Amsterdam

Events

Institute for Logic, Language and Computation

Please note that this newsitem has been archived, and may contain outdated information or links.

27 March 2015, Cool Logic, Michal Tomasz Godziszewski

Speaker: Michal Tomasz Godziszewski
Title: Computational properties of undecidable sentences and concrete model theory
Date: Friday 27 March 2015
Time: 17:30-18:30
Location: F1.15 ILLC seminar room, Science Park 107, Amsterdam
Target audience: MSc Logic and PhD students

We consider the properties of the arithmetically simplest class of universal (i.e. $\Pi^0_1$) sentences undecidable in sufficiently strong arithmetical theories. Following the framework of experimental logic and results of R. G. Jeroslow obtained in Jer75, we therefore answer an epistemological question about cognitive reasons of epistemic hardness of undecidable arithmetical sentences. We prove that by adjoining the minimal (in the sense of being on a very low level of arithmetical hierarchy) possible set of undecidable sentences to recursive set of axioms of arithmetical theory and closing it under logical consequence, we obtain a theory such that it is not algorithmically learnable (i.e. not $\Delta^0_2$).

For more information, see http://www.illc.uva.nl/coollogic/ or contact

Please note that this newsitem has been archived, and may contain outdated information or links.