Abstract: Learning over sparse background structures, of at most poly-logarithmic degree, has been recently shown to be in poly-logarithmic time for First-Order Logic (FOL) definable concepts. The primary aim of this proposal is to investigate if the claim holds for counting extensions of FOL and Modal Logic. I will also explore learnability of FOL definable concepts over the field of the Real Numbers as a background structure. Extensions of FOL with some basic counting and aggregation are expressible in infinitary counting logics. These logics are a central component of relational database management systems like SQL. This research, thus arches between database management and machine learning.
Research ProposalPhilosophy
Advisors: Dr. A. Antonelli, Dr. E. LandryIn their classical papers, Alan Turing (1936) and Alonzo Church (1936) independently proved the unsolvability of the Entscheidungsproblem. Each forwarded their own thesis, from which, in 1967 Kleene coined the Church-Turing Thesis (CTT). It is one of the most fundamental hypotheses as far as computation is concerned. More often than not, the CTT is misinterpreted as making a statement concerning the powers of the human mind, or a modern computer. These “variants” are not, as many claim, equivalent to the original thesis. In fact, most of them make claims that are stronger than the actual one and make overt assumptions rendering these “variants” uninteresting. We reject such claims and argue that neither Turing nor Church intended to characterize their hypothesis as such. Both of the theses are restricted to physical machines and are a consequence of the postulates formulated by Gandy in 1980. Further, we argue that it is of much philosophical interest to consider the standing of the CTT as a physical statement than one claiming the limitations of the human mind.
Here is the link to a paper I wrote whilst working on this project.Computer Science
Advisors: Dr. D. Doty