On Finitary Interpretations of Theorems of the Theory of Algorithms and Recursively Enumerable Sets
by
Nikolai A. Shanin
Petersburg Department of Steklov Mathematical Institute

The statements of theorems of the theory of algorithms and recursively enumerable sets (including some basic theorems) often go beyond the limits of languages of finitary mathematics thus being "semantic riddles" (from the point of view of the finitary mathematical thought). For a series of such theorems (including undecidability of several mass problems), finitarily sensible and finitarily provable strengthenings (finitary majorants) are introduced. They are usually extracted from the "natural" procedures of deduction of the theorems by means of wider constructive mathematics while at the same time suiting the role of finitary versions of our non-finitary statements.

Date received: March 31, 2003

Copyright © 2003 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Mathematical Conference Abstracts. Document # cajy-22.