Общая теория вычислимости

General Theory of Computability
by Lavrov I.A.


This database was created to provide specialists in different areas of computability theory a full view on a variety of current research directions in continuously developing field of theory of algorithms.

The bibliography includes more than 3000 known to the author scientific monographs and articles on recursion theory, degrees of unsolvability, elementary theories, generalized computations and their applications. There are some, but not as many papers on random algorithms, reverse mathematics, polynomial algorithms, generalization of computability, and applications in particular directions of mathematics. With a few exceptions unpublished articles and private messages were not included in the bibliography.

The database will be corrected and updated whenever new information arrives. Any feedback including remarks and suggestions is welcomed on e-mail: lavrov@ispras.ru.

Search Hints

1. To get the list of authors included in the database click on first letter of author’s last name, either Russian or English. You will be provided with the list of all authors whose name starts with the selected letter. It must be observed that the same author can have papers written in English and in Russian, and they will appear in different lists depending on the language of the selected letter. Sometimes last names in the list include initials to distinguish namesakes and avoid cases when a last name is a common word or a part of another last name.

2. Clicking on the author’s last name brings the list of all papers in the database, which have given last name among authors or in the name of the paper.

3. Clicking on a certain paper in the list brings detailed information about the paper containing the following lines.

1. Names of authors.

2. Year of publication.

3. Name of the paper.

4. Source of publication.

5. Technical data formatted as YY.VV.NN meaning that abstract for this paper was published in Russian magazine "Mathematics Abstracts" in the year 19YY, volume VV, number NN. Most papers were published in the part A of the magazine and it is meant by default. If the abstract was published in parts Б or В, VV is replaced with БVV or ВVV.
Data formatted as BHYY.VV.NN means that the abstract was published in "Computational Sciences Abstracts" magazine.
Symbols ~ and ? mean that the abstract does not exist or was not yet found.

6. A combination of letters R,E,O,S,G meaning that this paper is referred in the following books:

R – R – Rogers H. "Theory of recursive functions and effective computability" (Russian version).
E - Ershov Ju. L. "Theory of numberings" (Russian version).
O – Odifreddi P. "Classical Recursive Theory, The theory of functions and sets of natural numbers, v. I, II".
S – Soare R.I. "Recursively enumerable sets and degrees" (Russian version).
G – Goncharov S.S., Ershov Ju. L. "Constructive Models" (Russian version).

7. Type of the paper: either book or article.

For example:

Abraham U., Shore R.A.
Initial segments of the Turing degrees
Israel. J. Math., 53, № 1, 1-51

To find the papers containing certain words in the name or authored by a certain author type the words or author’s name in the Search box and click "Искать" button.

The author wants to thank M.N. Grinev and A.G. Ryzhov for their help in creating the database.

Search query syntax

A common search query is one or more words, for example:
contact information
This query will find pages containing both query words.

Logical operators allow building more complex queries, for example:
contact information or phone
This query will find pages containing either words "contact" and "information" or "phone".

contact information not phone
This query will find pages containing words "contact" and "information" but not "phone".
You can use brackets to build more complex queries.

Logical operators

Operator SynonymsDescription
andand, &, +Operator logical and is implied and can be omitted: a query "contact information" is fully equivalent to "contact and information".
oror, |Operator logical or allows searching for entities containing at least one of the operands.
notnot, ~Operator logical not restricts searches to pages not containing the operand.
( ) Round brackets define the logical operator precedence.