Основы теории алгоритмов

Любая непротиворечивая система арифметики с рекурсивной системой аксиом
не может быть полной
совпадает с системой Пеано
должна быть полной
является замкнутой
Класс примитивно рекурсивных функций
входит в класс вычислимых функций
содержит в себе класс вычислимых функций
расширяет класс вычислимых функций
совпадает с классом вычислимых функций
Если image057.gifи рекурсия проводится по image015.gif, то функция image058.gifравна
image059.gif
image061.gif
image022.gif
image060.gif
Имена и предложения называются фразами
замкнутыми
порождающими
челночными
простейшими
Функция называется частично рекурсивной, если она либо принадлежит к числу исходных п.р.ф., либо может быть получена из них с помощью операторов
подстановки, минимизации
подстановки, рекурсии
рекурсии
подстановки, рекурсии, минимизации
Внутреннее состояние машины Тьюринга обозначается
image102.gif
П, Л, H
image100.gif
image101.gif
Конечное множество команд, имеющих попарно различные начальные пары символов, называется
алгоритмом
машиной Тьюринга
программой
конфигурацией