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


Лавров И.А.
ОБЩАЯ ТЕОРИЯ ВЫЧИСЛИМОСТИ
(библиография)

Цель создания подобной базы данных состоит в том, чтобы специалисты в различных направлениях Теории Вычислимости имели достаточно полное на данный момент представление о многообразии научных исследований в этой непрерывно развивающейся области теории алгоритмов.

В базу включены более 3000 известных составителю научных монографий и статей по теории рекурсии, степеням неразрешимости, элементарным теориям, обобщенным вычислениям и их приложениям. В меньшей степени указаны работы по вероятностным алгоритмам, реверсивной математике, полиномиальным алгоритмам, обобщениям вычислимости и приложениям в конкретных математических направлениях. Автор не включал в базу, за редким исключением, неопубликованные работы и частные сообщения.

Предполагается, что в базу будут вноситься необходимые коррективы и дополнения по мере их поступления. Автор будет признателен за все замечания и предложения, которые можно ему сообщать по адресу: lavrov@ispras.ru.

Несколько правил пользования данной поисковой системой

1. Если Вы хотите узнать список авторов, работы которых имеются в базе, надо вызвать первую букву фамилии (русской или английской). Система поиска выдаст список всех фамилий авторов, начинающихся на указанную букву. Необходимо иметь в виду, что авторы могут иметь работы, написанные как кириллицой, так и латинским алфавитом. Они будут находиться в разных списках.

2. Далее, надо вызвать в данном списке фамилию автора. Система выдаст список всех имеющихся в базе работ, где указанная фамилия встречается в списке авторов или в названии работы. Здесь нам пришлось в ряде случаев подсоединять к фамилии часть инициалов, с тем, чтобы избежать случаев однофамильцев или когда фамилия входит частью в другую фамилию или слово. Если Вы вызовете какую-то конкретную работу из этой подборки, то система выдаст наиболее расширенную информацию о данной работе. Например, система выдала следующую подборку:

Abraham U., Shore R.A.
[1986]
Initial segments of the Turing degrees
Israel. J. Math., 53, № 1, 1-51
86.12.68
REOSG
article/book

Здесь в первых четырех строках указаны авторы работы, год опубликования, название работы, где опубликована работа, а в седьмой строке – статус работы (статья или книга).

Особое место занимают пятая и шестая строки – здесь указаны некоторые технические данные. Так, группа 86.12.68 означает, что реферат на данную работу имеется в "Реферативном журнале. Математика" за 1986 год, том 12, номер реферата 68. Большинство работ прореферированы в части А данного журнала, и это специально не оговаривается. Однако, если реферат находится в частях Б, В или Г данного тома, это отмечено во второй группе цифр. Например, 86.Б3.68. Если эта группа имеет следующий вид ВН86.05.123, то реферат находится в "Реферативном журнале. Вычислительные науки". Если вместо всей этой группы стоит ~ или ?, то это означает, что реферат отсутствует или пока не найден.

Комбинация букв REOSG (в любом наборе) в шестой строке означает, что на данную работу имеется ссылка в одной из следующих книг:
R – Роджерс Х. "Теория рекурсивных функций и эффективная вычислимость" (русский вариант);
E – Ершов Ю.Л. "Теория нумераций";
O – Odifreddi P. “Classical Recursive Theory, The theory of functions and sets of natural numbers, v. I, II”;
S – Соар Р.И. "Вычислимо перечислимые множества и степени" (русский вариант);
G – Гончаров С.С., Ершов Ю.Л. "Конструктивные модели".

3. Желающий сразу найти работы конкретного автора должен в таблице "Общий поиск" вызвать фамилию автора. Аналогично можно поступить, если есть желание найти работы, в названии которых встречается некоторое конкретное слово. Система способна делать и такие выборки.

Автор приносит глубокую благодарность М.Н. Гриневу и А.Г. Рыжову, за помощь в создании данной поисковой системы.