Universiteit van Amsterdam


Institute for Logic, Language and Computation

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

31 March 2015, Logic Tea, Michal Tomasz Godziszewski

Speaker: Michal Tomasz Godziszewski
Title: Learnability in the Limit and Low Sets meet the Church Thesis
Date: Tuesday 31 March 2015
Time: 17:00-18:00
Location: Room F1.15, Science Park 107, Amsterdam


We consider the notion of intuitive learnability and its relation to intuitive computability. We briefly present and discuss the Church's Thesis in the first section. A set is intuitively learnable if there is a (possibly infinite) intuitive procedure that for each input produces a finite sequence of yeses and nos such that the last answer in the sequence is correct. In the second section we formulate the Learnability Thesis which states that the notion of intuitive learnability is equivalent to the notion of algorithmic learnability. Our claim is analogous to the Church's Thesis. Further, in the third section, we analyse the “proof” of the Church's Thesis presented by Mostowski. The “proof” goes in unusual lines – by giving a model of the world, namely F M (N ), separating knowable (intuitively computable) sets from FM-representable (algorithmically learnable) ones and showing that knowable sets are exactly recursive. We indicate which assumptions of the Mostowski's argument implicitly include that Church's Thesis holds. The impossibility of this kind of argument is strengthened in the fourth section by showing that the Learnability Thesis does not imply the Church's Thesis. Specifically, we show a “natural” interpretation of intuitive computability under which intuitively learnable sets are exactly algorithmically learnable but intuitively computable sets form a proper superset of recursive sets.

For more information, please visit the website http://www.illc.uva.nl/logic_tea/ or contact Thomas Brochhagen (), Johannes Marti (), Masa Mocnik () or Julian Schloder ().

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