Тема: Теория вычислимости

И.В. Ашаев, Омский государственный университет, кафедра математической логики. Обычная теория алгоритмов изучает...
В качестве формализации обобщенной вычислимости будем использовать машину над списочной надстройкой из [1]. Эта машина представляет...

Темами исследований в информатике являются вопросы: что можно, а что нельзя реализовать в программах ( теория вычислимости и искусственный интеллект), каким образом можно решать специфические задачи с максимальной эффективностью (алгоритмы), в...

Дескриптивная теория . Задача точного определения понятия алгоритма была полностью решена в 30-х годах XX века в двух формах: на основе описания...
Можно доказать, что операции суперпозиции, рекурсии и минимизации сохраняют свойство вычислимости [10].

Из данного определения и приведенных выше замечаний о сохранении. вычислимости операторами S, R, М легко следует, что всякая частично.
В книге Гудстейн Р. Л. Математическая логика. М.: ИЛ, 1961, с. 149-154. 3. Смальян Р. Теория формальных систем.

Тогда возникает вопрос, чем же это не теория ремесла, чем же не наука? Дело в том, что подобные трактаты содержали не систему, а набор знаний...
теорию алгоритмов (формальные модели алгоритмов, проблемы вычислимости , сложность вычислений и т.п.)

Заключают работы Ершова по теории программирования его публикации, посвященные понятию вычислимости .