1958 году работами Ляпунова А.А. и Янова Ю.И. заложено новое направление научных исследований - теория схем программ. Первыми изучаемыми в ней объектами стали схемы программ, именуемые в дальнейшем схемами Янова. В последующие годы были предложены и развиты разнообразные варианты моделей программ. В их числе - модели рекурсивных программ. Они служат подходящей математической абстракцией для изучения последовательных программ, снабженных аппаратом процедур. В этой статье определены основные понятия теории моделей рекурсивных программ и представлены некоторые результаты изучения основных задач этой теории. Показано, что подкласс гладких моделей рекурсивных программ с отношением аппроксимации образует верхнюю полурешетку. Затем продемонстрированы некоторые модели рекурсивных программ как с разрешимой, так и с неразрешимой проблемой эквивалентности. Проведен отбор классов моделей рекурсивных программ, наиболее перспективных для построения в них алгоритмов проверки эквивалентности. Описана методика поиска алгоритмов, разрешающих проблему эквивалентности в моделях рекурсивных программ. Также описаны правила (аксиомы) эквивалентных преобразований рекурсивных программ и показано, что в некоторых моделях существуют полные системы эквивалентных преобразований.

модель программ, рекурсивная программа, отношение аппроксимации, проблема эквивалентности, разрешающая процедура, эквивалентное преобразование

Математические вопросы и теория численных методов