Computability in Europe 2008
Logic and Theory of Algorithms

Print current page  Print this page

Regular Talk:
Limiting recursion, FM-repressentability, and hypercomputations

Edit abstract data

THIS TALK HAS BEEN CANCELLED!!!
Speaker: Marcin Mostowski
Author(s): Marcin Mostowski

Abstract

We consider various methodologically well motivated notions which appear to be
essentially different, but surprisingly capture the same class of relations.
These are: the notion of FM-representability (representability in Finite
Models), statistical representability, limiting recursion or algorithmic
learning with empty data, and decidability by accelerating Turing machines by
computations of length $\omega$.
Finally, we give a new result characterizing FM-representability in poor
finite arithmetics, weaker than divisibility arithmetic, but stronger than
coprimality arithmetic.


websites: Arnold Beckmann 2008-06-20 Valid HTML 4.01! Valid CSS!