Основы теории алгоритмов
Любая непротиворечивая система арифметики с рекурсивной системой аксиом
не может быть полной
совпадает с системой Пеано
должна быть полной
является замкнутой
Класс примитивно рекурсивных функций
входит в класс вычислимых функций
содержит в себе класс вычислимых функций
расширяет класс вычислимых функций
совпадает с классом вычислимых функций
и рекурсия проводится по 
, то функция 
равна
Имена и предложения называются фразами
замкнутыми
порождающими
челночными
простейшими
Функция называется частично рекурсивной, если она либо принадлежит к числу исходных п.р.ф., либо может быть получена из них с помощью операторов
подстановки, минимизации
подстановки, рекурсии
рекурсии
подстановки, рекурсии, минимизации
Конечное множество команд, имеющих попарно различные начальные пары символов, называется
алгоритмом
машиной Тьюринга
программой
конфигурацией