Книга: Математическая логика

Скачать

Предлагаемая читателю книга представляет собой введение в проблематику и методы теории нумераций - нового развивающегося раздела теории алгоритмов. Насколько известно автору, впервые идею о систематическом изучении нумерованных множеств высказал А. Н. Колмогоров в середине пятидесятых годов. Реализацией этой идеи для вычислимых нумераций в то время занялся В. А. Успенский.

Основные его результаты изложены в статье 63 и в книге 10, вышедшей в 1960 году. Параллельно ряд зарубежных математиков (Райс, Деккер, Майхилл, Фридберг, Лахлан, Лакомб, Пур-Эль и др.) также занимались изучением различных вопросов, связанных с вычислимыми нумерациями. Независимо были осуществлены попытки изучения нумерованных алгебр (Фрелих — Шепердсон, Рабин), которые также обнаружили интересные специфические «нумерационные» особенности.