Математический форум Math Help PlanetОбсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 4 часа [ Летнее время ] |
Рекурсивные функции | |
---|---|
Онлайн-сервисы
Нахождение НОД и НОК
Разложение числа на простые множители
Сравнения по модулю
Операции над множествами
Операции над векторами
Разложение вектора по базису. Доказательство, что векторы образуют базис
Чертёж треугольника по координатам вершин
Решение треугольника
Решение Пирамиды
Построение Пирамиды по координатам вершин
Чертёж многоугольника по координатам вершин
Решение систем методом Крамера и Матричным
Онлайн построение графика кривой 2-го порядка
Определение вида кривой или поверхности 2-го порядка по инвариантам
МНК и регрессионный анализ Онлайн + графики
Алгоритмы JavaScript
Алгоритмы поиска
Алгоритмы сортировки
Уникальные элементы массива
Объединение, пересечение и разность массивов
НОД и НОК
Операции над матрицами
Введение в анализ
Функции: понятие, определение, графики
Непрерывность функции
Исследование функции и построение графика
Теория множеств
Множества: понятие, определение, примеры
Точечные множества
Замкнутые и открытые множества
Мера множества
Группы, кольца, поля в математике
Поле комплексных чисел
Кольцо многочленов
Основная теорема алгебры и ее следствия
Математическая логика
Алгебра высказываний
Аксиоматика и логические рассуждения
Методы доказательств теорем
Алгебра высказываний и операции над ними
Формулы алгебры высказываний
Тавтологии алгебры высказываний
Логическая равносильность формул
Нормальные формы для формул высказываний
Логическое следование формул
Приложение алгебры высказываний для теорем
Дедуктивные и индуктивные умозаключения
Решение логических задач
Принцип полной дизъюнкции
Булевы функции
Множества, отношения и функции в логике
Булевы функции от одного и двух аргументов
Булевы функции от n аргументов
Системы булевых функций
Применение булевых функций к релейно-контактным схемам
Релейно-контактные схемы в ЭВМ
Практическое применение булевых функций
Теория формального
Формализованное исчисление высказываний
Полнота и другие свойства формализованного исчисления высказываний
Независимость системы аксиом формализованного исчисления высказываний
Логика предикатов
Логика предикатов
Логические операции над предикатами
Кванторные операции над предикатами
Формулы логики предикатов
Тавтологии логики предикатов
Преобразования формул и следование их предикатов
Проблемы разрешения для общезначимости и выполнимости формул
Применение логики предикатов в математике
Строение математических теорем
Аристотелева силлогистика и методы рассуждений
Принцип полной дизъюнкции в предикатной форме
Метод полной математической индукции
Необходимые и достаточные условия
Логика предикатов и алгебра множеств
Формализованное исчисление предикатов
Неформальные и формаль-ные аксиоматические теории
Неформальные аксиоматические теории
Свойства аксиоматических теорий
Формальные аксиоматические теории
Формализация теории аристотелевых силлогизмов
Свойства формализованного исчисления предикатов
Формальные теории первого порядка
Формализация математической теории
Теория алгоритмов
Интуитивное представление об алгоритмах
Рекурсивные функции
Нормальные алгоритмы Маркова
Разрешимость и перечислимость множеств
Неразрешимые алгоритмические проблемы
Теорема Гёделя о неполноте формальной арифметики
Математическая логика и компьютеры
Дискретная математика
Множества и отношения
Теория множеств: понятия и определения
Операции над множествами
Кортеж и декартово произведение множеств
Соответствия и бинарные отношения на множествах
Операции над соответствиями на множествах
Семейства множеств
Специальные свойства бинарных отношений
Отношения эквивалентности на множестве
Упорядоченные множества
Теорема о неподвижной точке
Мощность множества
Парадокс Рассела
Метод характеристических функций
Группы и кольца
Алгебраические структуры и операции
Группоиды, полугруппы, группы
Кольца, тела, поля
Области целостности в теории колец
Модули и линейные пространства
Подгруппы и подкольца
Теорема Лагранжа о порядке конечной группы
Гомоморфизмы групп и нормальные делители
Гомоморфизмы и изоморфизмы колец
Алгебра кватернионов
Полукольца и булевы алгебры
Полукольца: определение, аксиомы, примеры
Замкнутые полукольца
Полукольца и системы линейных уравнений
Булевы алгебры и полукольца
Решетки и полурешетки
Алгебраические системы
Алгебраические системы: модели и алгебры
Подсистемы алгебраических систем
Конгруэнции и фактор-системы
Гомоморфизмы алгебраических систем
Прямые произведения алгебраических систем
Конечные булевы алгебры
Многосортные алгебры
Теория графов
Теория графов: основные понятия и определения
Способы представления графов
Неориентированные и ориентированные деревья
Остовное дерево и алгоритм Краскала
Методы систематического обхода вершин графа
Алгоритмы поиска в глубину и ширину в графах
Задача о путях во взвешенных ориентированных графах
Изоморфизм, гомоморфизм и автоморфизм графов
Топологическая сортировка вершин графа
Элементы цикломатики в теории графов
Булева алгебра и функции
Булевы функции и булев куб
Таблицы булевых функций и булев оператор
Равенство булевых функций. Фиктивные переменные
Формулы и суперпозиции булевых функций
Дизъюнктивные и конъюнктивные нормальные формы
Построение минимальных ДНФ
Теорема Поста и классы
Критерий Поста
Схемы из функциональных элементов
Конечные автоматы и регулярные языки
Конечные автоматы и регулярные языки
Алфавит, слово, язык в программировании
Порождающие грамматики (грамматики Хомского)
Классификация грамматик и языков
Регулярные языки и регулярные выражения
Конечные автоматы
Допустимость языка конечным автоматом
Теорема Клини
Детерминизация конечных автоматов
Минимизация конечных автоматов
Лемма о разрастании для регулярных языков
Обоснование алгоритма детерминизации автоматов
Конечные автоматы с выходом
Морфизмы и конечные подстановки
Машины Тьюринга
Контекстно-свободные языки
Контекстно-свободные языки и грамматики
Приведенная форма КС-грамматики
Лемма о разрастании для КС-языков
Магазинные автоматы (автомат с магазинной памятью)
Алгоритм построения МП-автомата по КС-грамматике
Алгоритм построения КС-грамматики по МП-автомату
Алгебраические свойства КС-языков
Основное свойство суперпозиции КС-языков
Пересечение контекстно-свободных языков
Методы синтаксического анализа КС-языков
Восходящий синтаксический анализ и LR(k)-грамматики
Семантика формальных языков
Принцип индукции по неподвижной точке
Графовое представление МП-автоматов
Интегральное исчисление
Неопределённый и определённый
Неопределенный и определенный интегралы
Свойства интегралов
Интегрирование по частям
Интегрирование методом замены переменной
Интегрирование различных рациональных функций
Интегрирование различных иррациональных функций
Интегрирование различных тригонометрических функций
Определенный интеграл и его основные свойства
Необходимое и достаточное условие интегрируемости
Теоремы существования первообразной
Свойства определенных интегралов
Несобственные интегралы
Интегральное определение логарифмической функции
Приложения интегралов
Вычисление площадей плоских фигур
Площади фигур в различных координатах
Вычисление объемов тел с помощью интегралов
Объём тела вращения
Вычисление длин дуг кривых
Формулы длины дуги регулярной кривой
Кривизна плоской кривой
Площадь поверхности вращения тела
Интегралы в физике
Статические моменты и координаты центра тяжести
Теоремы Гульдина–Паппа
Вычисление моментов инерции
Другие приложения интегралов в физике
Основные интегралы
Вариационное исчисление
Примеры вариационных задач
Дифференциальное уравнение Эйлера
Функционалы, зависящие от нескольких функций
Задача о минимуме кратного интеграла
Финансовый анализ
Анализ эффективности
Критерии и показатели эффективности предприятия
Методы анализа эффективности деятельности
Факторный анализ прибыли от операционной деятельности
Анализ безубыточности предприятия
Операционный рычаг и эффект финансового рычага
Анализ и оценка состава, структуры и динамики доходов и расходов
Анализ рентабельности и резервов устойчивого роста капитала
Анализ распределения прибыли предприятия
Анализ и оценка чувствительности показателей эффективности
Анализ устойчивости
Финансовая устойчивость и долгосрочная платежеспособность
Характеристика типов финансовой устойчивости
Рыночная активность
Финансовый анализ рыночной активности
Методика анализа рыночной активности
Анализ и оценка дивидендного дохода на одну акцию
Инвестиционная деятельность
Инвестиции: экономическая сущность и классификация
Государственное регулирование инвестиционной деятельности
Источники финансовых ресурсов на капитальные вложения
Инвестиции в основные фонды
Оценка состояния основных фондов
Амортизация основных фондов
Капитальное строительство в инвестиционном процессе
Планирование инвестиций в форме капитальных вложений
Экономическая эффективность инвестиций
Финансирование капитальных вложений
Кредитование капитальных вложений
Кредитоспособность
Финансирование и кредитование затрат
Финансирование и кредитование инвестиционной деятельности потребительской кооперации
Финансирование и кредитование капитальных вложений потребительской кооперации
Инвестиционное строительное проектирование
Анализ инвестиций
Инвестиции и инвестиционная деятельность предприятия
Задачи финансового анализа инвестиций предприятия
Учет фактора времени в инвестиционной деятельности
Аннуитет и финансовая рента в инвестициях
Учет фактора инфляции при инвестировании
Оценка фактора риска инвестиционного проекта
Методы оценки эффективности инвестиций
Показатели эффективности инвестиционного проекта
Стоимость компании
Концепция построения международных стандартов финансовой отчетности (МСФО)
Экономическое содержание международных стандартов финансовой отчётности
Цели и принципы оценки стоимости акций и активов компании
Оценка акций и активов предприятия по справедливой стоимости
Методы оценки справедливой стоимости акций предприятия
Затратный подход к оценки стоимости компаний и акций
Сравнительный подход к оценки стоимости предприятий и акций
Доходный подход к оценке стоимости компании и акций
Выбор ставки дисконтирования при инвестировании в акции
Метод капитализации прибыли
Сравнение подходов к оценке стоимости компаний и пакетов акций
Форвардные контракты
Форвардный контракт и цена
Форвардная цена акции на бирже
Цена форвардного контракта инвестора
Форвардная цена акции с учетом величины дивиденда
Форвардная цена акции с учетом ставки дивиденда
Форвардная цена валюты на рынке форекс
Форвардный валютный курс и инфляция на рынке
Форвардная цена товара и спотовый рынок
Форвардная цена при различии ставок по кредитам и депозитам
Синтетический форвардный контракт на акции и валюту
Теория вероятностей
Основные понятия теории вероятностей
Зависимые и независимые случайные события
Повторные независимые испытания
Формула Бернулли
Одномерные случайные величины
Многомерные случайные величины
Функции случайных величин
Законы распределения целочисленных случайных величин
Законы распределения непрерывных случайных величин
Предельные теоремы теории вероятностей
Закон больших чисел и предельные теоремы
Вероятностные закономерности
Мат. статистика
Элементы математической статистики
Выборочный метод
Оценки параметров генеральной совокупности
Статистические гипотезы
Критерии согласия
Теоретические и эмпирические частоты
Теория очередей (СМО)
Определение системы массового обслуживания
Уравнения Колмогорова
Предельные вероятности состояний
Определение СМО с отказами
Определение СМО с ожиданием (очередью)
Аналитическая геометрия
Векторная алгебра
Метрические понятия и аксиомы геометрии
Равенство и подобие геометрических фигур
Бинарные отношения
Вектор, его направление и длина
Линейные операции над векторами
Линейная зависимость и независимость векторов
Отношение коллинеарных векторов
Проекции векторов на прямую и на плоскость
Угол между векторами
Ортогональные проекции векторов
Координата вектора на прямой и базис
Координаты вектора на плоскости и базис
Координаты вектора в пространстве и базис
Операции над векторами в координатной форме
Ортогональный и ортонормированный базисы
Cкалярное произведение векторов и его свойства
Выражение скалярного произведения через координаты векторов
Векторное произведение векторов и его свойства
Смешанное произведение векторов и его свойства
Ориентированные площади и объемы
Двойное векторное произведение и его свойства
Применение векторов в задачах на аффинные свойства фигур
Применение произведений векторов при решении геометрических задач
Применение векторной алгебры в механике
Системы координат
Прямоугольные координаты
Преобразования прямоугольных координат
Полярная система координат
Цилиндрическая система координат
Сферические координаты
Аффинные координаты
Аффинные преобразования координат
Аффинные преобразования плоскости
Примеры аффинных преобразований плоскости
Аффинные преобразования пространства
Многомерное координатное пространство
Линейные и аффинные подпространства
Скалярное произведение n-мерных векторов
Преобразования систем координат
Геометрия на плоскости
Алгебраические линии на плоскости
Общие уравнения геометрических мест точек
Алгебраические уравнения линий на плоскости
Уравнения прямой, проходящей через точку перпендикулярно вектору
Уравнения прямой, проходящей через точку коллинеарно вектору
Уравнения прямой, проходящей через две точки
Уравнения прямой с угловым коэффициентом
Взаимное расположение прямых
Примеры задач с прямыми на плоскости
Системы неравенств с двумя неизвестными
Системы линейных уравнений с двумя неизвестными
Линии 2-го порядка
Канонические уравнения линий второго порядка
Порядок приведения уравнения линии к каноническому виду
Эллипс
Гипербола
Парабола
Квадратичные неравенства с двумя неизвестными
Применение линий 1-го и 2-го порядков в задачах на экстремум функций
Инварианты линий
Классификация линий 2-го порядка по инвариантам
Приведение уравнения линии к каноническому виду по инвариантам
Геометрия в пространстве
Способы задания ГМТ в пространстве
Алгебраические уравнения поверхностей
Уравнения плоскости, проходящей через точку перпендикулярно вектору
Уравнения плоскости, компланарной двум неколлинеарным векторам
Уравнения плоскости, проходящей через три точки
Взаимное расположение плоскостей
Типовые задачи с плоскостями
Уравнения прямых в пространстве
Взаимное расположение прямых в пространстве
Типовые задачи с прямыми в пространстве
Поверхности 2-го порядка
Канонические уравнения поверхностей
Порядок приведения уравнения поверхности к каноническому виду
Поверхности второго порядка
Эллипсоиды
Гиперболоиды
Конусы
Параболоиды
Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций
Инварианты поверхностей
Линейная алгебра
Матрицы и операции
Линейные операции над матрицами
Умножение матриц
Возведение матриц в степень
Многочлены от матриц
Транспонирование и сопряжение матриц
Блочные матрицы
Произведение и сумма матриц Кронекера
Метод Гаусса приведения матрицы к ступенчатому виду
Элементарные преобразования матриц
Определители
Определители матриц и их основные свойства
Формула полного разложения определителя
Формула Лапласа полного разложения определителя
Определитель произведения матриц
Методы вычисления определителей
Ранг матрицы
Линейная зависимость и линейная независимость строк (столбцов) матрицы
Ранг матрицы и базисный минор матрицы
Методы вычисления ранга матрицы
Ранг системы столбцов (строк)
Обратная матрица
Обратные матрицы и их свойства
Ортогональные и унитарные матрицы
Способы нахождения обратной матрицы
Матричные уравнения
Односторонние обратные матрицы
Скелетное разложение матрицы
Полуобратная матрица
Псевдообратная матрица
Системы уравнений
Системы линейных алгебраических уравнений
Метод Гаусса решения систем линейных уравнений
Структура общего решения системы уравнений
Решение систем с помощью полуобратных матриц
Псевдорешения системы линейных уравнений
Функциональные матрицы
Функциональные матрицы скалярного аргумента
Производные матриц по векторному аргументу
Линейные и квадратичные формы и их преобразования
Приведение форм к каноническому виду
Закон инерции вещественных квадратичных форм
Знакоопределенность форм вещественных квадратичных
Формы и исследование функций на экстремум
Многочленные матрицы
Многочленные матрицы (лямбда-матрицы)
Операции над лямбда-матрицами
Простые преобразования многочленных матриц
Инвариантные множители многочленной матрицы
Функции от матриц
Собственные векторы и значения матрицы
Подобие числовых матриц
Характеристический многочлен матрицы
Минимальный многочлен матрицы
Теорема Гамильтона-Кэли
Жорданова форма матрицы
Приведение матрицы к жордановой форме
Многочлены от матриц
Применение многочленов от матриц
Функции от матриц
Линейные пространства
Линейные пространства: определение и примеры
Размерность и базис линейного пространства
Преобразования координат в линейном пространстве
Изоморфизм линейных пространств
Подпространства
Подпространства линейного пространства
Пересечение и сумма подпространств
Способы описания подпространств
Нахождение дополнения и суммы подпространств
Нахождение пересечения подпространств
Линейные отображения
Линейные многообразия
Линейные отображения
Матрица линейного отображения
Ядро и образ линейного отображения
Линейные операторы
Линейные операторы (преобразования)
Инвариантные подпространства
Собственные векторы и значения оператора
Свойства собственных векторов операторов
Канонический вид линейного оператора
Методика приведения линейного преобразования к каноническому виду
Евклидовы пространства
Евклидовы пространства
Ортогональные векторы евклидова пространства
Ортогональный базис евклидова пространства
Ортонормированный базис евклидова пространства
Ортогональные дополнения в евклидовом пространстве
Задача о перпендикуляре
Матрица и определитель Грама и его свойства
Линейные преобразования евклидовых пространств
Канонический вид ортогонального оператора евклидова пространства
Сопряженные операторы евклидова пространства
Самосопряженные операторы евклидова пространства
Приведение квадратичной формы к главным осям
Унитарные пространства и их линейные преобразования
Комплексный анализ
Комплексные числа
Комплексные числа в алгебраической форме
Комплексные числа в тригонометрической и показательной формах
Множества на комплексной плоскости
Последовательности и ряды комплексных чисел
Комплексные функции
Функции комплексного переменного. Предел, непрерывность и производная
Элементарные функции комплексного переменного
Дифференцирование функций комплексного переменного
Аналитические функции и их свойства
Конформные отображения
Функциональные ряды в комплексной области
и их свойства Интегрирование функций комплексного переменного
Функциональные ряды и последовательности
Степенные ряды и их свойства
Разложение функций в степенные ряды
Нули аналитических функций
Ряд Лорана и разложение функций по целым степеням
Особые точки, Вычеты
Изолированные особые точки функций и полюсы
Вычеты и их применение
Вычисление интегралов с помощью вычетов
Вычеты и расположение нулей многочлена
Операционное исчисление
Дифференциальные уравнения
ДУ первого порядка
Основные понятия и определения ДУ
Метод изоклин для ДУ 1-го порядка
Метод последовательных приближений
ДУ с разделяющимися переменными
Однородные ДУ
Линейные ДУ 1-го порядка
Дифференциальное уравнение Бернулли
ДУ в полных дифференциалах
Интегрирующий множитель
ДУ, не разрешенные относительно производной
Дифференциальное уравнение Риккати
Составление ДУ семейств линий
Задачи на траектории
Особые решения ДУ
ДУ высших порядков
Понятия и определения ДУ высших порядков
ДУ, допускающие понижение порядка
Линейная независимость функций
Определители Вронского и Грама
Однородные и неоднородные дифференциальные уравнения
Задача Коши и Уравнение Эйлера
Линейные ДУ с переменными коэффициентами
Метод Лагранжа решения ДУ
Краевые задачи для ДУ высших порядков
Разложение решения ДУ в степенной ряд
Разложение решения ДУ в обобщенный степенной ряд
Нахождение периодических решений ДУ
Асимптотическое интегрирование ДУ
Системы ДУ
Системы ДУ: понятия и определения
Сведение системы ДУ к одному уравнению
Нахождение интегрируемых комбинаций
Интегрирование однородных линейных систем ДУ
Методы интегрирования неоднородных систем ДУ
Преобразование Лапласа и решение ДУ и систем
Теория устойчивости
Численные методы
Методы алгебры
Численные методы линейной алгебры
Численные методы решения СЛАУ
Итерационный метод Шульца обратной матрицы
Методы решения задач о собственных значениях и векторах матрицы
Методы решения нелинейных уравнений
Методы решения систем нелинейных уравнений
Методы теории приближений
Методы приближения сеточных функций
Методы функциональной интерполяции
Методы интегрально-дифференциальной интерполяции
Методы интегрального сглаживания
Методы интерполяции и сглаживания сплайнами
Методы численного дифференцирования и интегрирования
Методы численного дифференцирования
Методы численного интегрирования
Методы решения обыкновенных ДУ
|
Рекурсивные функцииПонятие машины Тьюринга — не единственный известный путь уточнения понятия алгоритма. В настоящем и следующем параграфах будут рассмотрены еще два способа такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова. Происхождение рекурсивных функцийВсякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий. Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 1930-х гг. теории рекурсивных функций. При этом класс вычислимых функций (названных здесь рекурсивными) получил такое описание, которое весьма напомнило процесс построения аксиоматической теории на базе некоторой системы аксиом. Сначала были выбраны простейшие функции, эффективная вычисляемость которых была очевидна (своего рода "аксиомы"). Затем сформулированы некоторые правила (названные операторами), на основе которых можно строить новые функции из уже имеющихся (своего рода "правила вывода"). Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов. Наша цель будет состоять в том, чтобы доказать, что этот класс функций совпадет с классом функций, вычислимых с помощью машин Тьюринга. Идея доказательства этого утверждения в одну сторону проста: сначала доказать вычислимость по Тьюрингу простейших функций, а затем вычислимость по Тьюрингу функций, получающихся из вычислимых по Тьюрингу функций с помощью выбранных операторов. Основные понятия теории рекурсивных функций и тезис ЧёрчаПриступим к построению класса рекурсивных функций в соответствии с изложенными принципами. Напомним, что рассматриваются функции, заданные на множестве натуральных чисел и принимающие натуральные значения. Функции предполагается брать частичные, т. е. определенные, вообще говоря, не для всех значений аргументов. В качестве исходных простейших функций выберем следующие: [math]S(x)=x+1[/math] (функция следования); [math]O(x)=0[/math] (нуль-функция); [math]I_m^n(x_1,x_2,\ldots,x_n)=x_m[/math] (функции-проекторы, [math]1\leqslant m\leqslant n[/math]). Вычислимость (более того, правильная вычислимость) этих функций с помощью машины Тьюринга установлена в примерах 32.7 и 32.10. Далее, в качестве операторов, с помощью которых будут строиться новые функции, выберем следующие три: операторы суперпозиции, примитивной рекурсии и минимизации. Определение 33.1 (оператор суперпозиции). Будем говорить, что n-местная функция [math]\varphi[/math] получена из m-местной функции [math]f[/math] и n-местных функций [math]g_1, \ldots,g_m[/math] с помощью оператора суперпозиции, если для всех [math]x_1,\ldots,x_n[/math], справедливо равенство: [math]\varphi(x_1,\ldots,x_n)= f \bigl(g_1(x_1,\ldots,x_n),\,\ldots,\, g_m(x_1,\ldots,x_n)\bigr).[/math] Понятие суперпозиции функций и сложной функции хорошо известно, но нас сейчас этот оператор интересует с точки зрения его взаимоотношений с процессом вычислимости функций с помощью машин Тьюринга. Теорема 33.2. Если функции [math]f(x_1,\ldots,x_m),\, g_1(x_1,\ldots,x_n),\ldots, g_m(x_1,\ldots,x_n)[/math] правильно вычислимы по Тьюрингу, то правильно вычислима и сложная функция (суперпозиция функций): [math]\varphi(x_1,\ldots,x_n)= f \bigl(g_1(x_1,\ldots,x_n),\,\ldots,\, g_m(x_1,\ldots,x_n)\bigr).[/math] ▼ Доказательство
Определение 33.3. Говорят, что (n+1)-местная функция [math]\varphi[/math] получена из n-местной функции [math]f[/math] и (n +2)-местной функции [math]g[/math] с помощью оператора примитивной рекурсии, если для любых [math]x_1,\ldots,x_n,y[/math] справедливы равенства: [math]\begin{gathered}\varphi(x_1,\ldots,x_n,0)= f(x_1,\ldots,x_n);\\ \varphi(x_1,\ldots,x_n, y+1)= g \bigl(x_1,\ldots,x_n, y, \varphi(x_1,\ldots,x_n,y)\bigr). \end{gathered}[/math] Пара этих равенств называется схемой примитивной рекурсии. Здесь важно отметить то, что, независимо от числа аргументов в [math]\varphi[/math], рекурсия ведется только по одной переменной [math]y[/math]; остальные [math]n[/math] переменных [math]x_1,\ldots,x_n[/math], на момент применения схемы примитивной рекурсии зафиксированы и играют роль параметров. Кроме того, схема примитивной рекурсии выражает каждое значение определяемой функции [math]\varphi[/math] не только через данные функции [math]f[/math] и [math]g[/math], но и через так называемые предыдущие значения определяемой функции [math]\varphi\colon[/math] прежде чем получить значение [math]\varphi(x_1,\ldots,x_n,k)[/math], придется проделать [math]k+1[/math] вычисление по указанной схеме — для [math]y=0,1,\ldots,k[/math]. Определение 33.4. Функция называется примитивно рекурсивной, если она может быть получена из простейших функций [math]O,\,S,\,I_m^n[/math] с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Наконец, введем заключительный, третий, оператор. Определение 33.5 (оператор минимизации). Будем говорить, что n-местная функция [math]\varphi[/math] получается из (n+1)-местных функций [math]f_1[/math] и [math]f_2[/math] с помощью оператора минимизации, или оператора наименьшего числа, если для любых [math]x_1,\ldots,x_n,y[/math] равенство [math]\varphi(x_1,\ldots,x_n)=y[/math] выполнено тогда и только тогда, когда значения [math]f_i(x_1,\ldots,x_n,0), \ldots, f_i(x_1,\ldots,x_n,y-1)[/math] [math](i=1;2)[/math] определены и попарно неравны: [math]f_1(x_1,\ldots,x_n,0)\ne f_2(x_1,\ldots,x_n,0), \ldots, f_1(x_1,\ldots,x_n,y-1)\ne f_2(x_1,\ldots,x_n,y-1),[/math] а [math]f_1(x_1,\ldots,x_n,y)=f_2(x_1,\ldots,x_n,y)[/math]. Коротко говоря, величина [math]\varphi(x_1,\ldots,x_n)[/math] равна наименьшему значению аргумента [math]y[/math], при котором выполняется последнее равенство. Используется следующее обозначение: [math]\varphi(x_1,\ldots,x_n)= \mu y \bigl[f_1(x_1,\ldots,x_n,y)= f_2(x_1,\ldots,x_n,y)\bigr].[/math] В частном случае может быть [math]f_2=0[/math]. Тогда [math]\varphi(x_1,\ldots,x_n)= \mu y \bigl[f(x_1,\ldots,x_n,y)=0\bigr][/math]. Оператор минимизации называется также µ-оператором. Этот оператор предназначен для порождения следующего важного класса рекурсивных функций. Определение 33.6. Функция называется частично рекурсивной, если она может быть получена из простейших функций [math]O,\,S,\,I_m^n[/math] с помощью конечного числа применений суперпозиции, примитивной рекурсии и µ-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной. (Отметим, что не всегда частично рекурсивную функцию можно эффективно доопределить до общерекурсивной.) Ясно, что всякая примитивно рекурсивная функция будет и частично рекурсивной (и даже общерекурсивной, так как каждая примитивно рекурсивная функция всюду определена), поскольку для построения частично рекурсивных функций из простейших используется больше средств, чем для построения примитивно рекурсивных функций. В то же время класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются и функции не всюду определенные. Понятие частично рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. При построении аксиоматической теории высказываний исходные формулы (аксиомы) и правила вывода выбирались так, чтобы полученные в теории формулы исчерпали бы все тавтологии алгебры высказываний. К чему же стремимся мы в теории рекурсивных функций, почему именно так выбрали простейшие функции и операторы для получения новых функций? Рекурсивными функциями мы стремимся исчерпать все мыслимые функции, поддающиеся вычислению с помощью какой-нибудь определенной процедуры механического характера. Подобно тезису Тьюринга, в теории рекурсивных функций выдвигается соответствующая естественно-научная гипотеза, носящая название тезиса Чёрча: Числовая функция тогда и только тогда алгоритмически (или машинно) вычислима, когда она частично рекурсивна. И эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом, ибо призвана увязать практику и теорию. Все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле, оказывались частично рекурсивными. Теперь мы рассмотрим более подробно классы примитивно рекурсивных функций и частично рекурсивных функций и докажем, что все функции из каждого из этих классов вычислимы на подходящих машинах Тьюринга. Примитивно рекурсивные функцииИтак, функция примитивно рекурсивна, если она может быть получена из простейших функций [math]O,\,S,\,I_m^n[/math] с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Рассмотрим ряд примеров примитивно рекурсивных функций. ▼ Примеры 33.7-33.9
Теорема 33.10. Функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна. Доказательство. В самом деле, компоненты этой функции получены из простейших функций [math]O,\,S,\,I_m^n[/math] с помощью конечного числа применений операторов суперпозиции и примитивной рекурсии. Чтобы получить рассматриваемую функцию, нужно добавить еще одну суперпозицию. В итоге эта функция также получается из простейших функций в результате конечного числа применений операторов суперпозиции и примитивной рекурсии, т.е. является примитивно рекурсивной. Примитивная рекурсивность предикатовОпределив ранее понятие предиката, мы отметили, что к этому понятию возможен и еще один подход. Предикат [math]P(x_1,\ldots,x_n)[/math], заданный над множествами [math]M_1,\ldots, M_n[/math], есть функция, заданная на указанных множествах и принимающая значения в двухэлементном множестве [math]\{0;1\}[/math]. В теории алгоритмов принято различать предикат [math]P[/math] и функцию, связанную с ним, а саму функцию называют характеристической функцией предиката [math]P[/math] и обозначают [math]\chi_{{}_P}[/math]. Таким образом, [math]\chi_{{}_P}(x_1,\ldots,x_n)= \begin{cases}0,& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~true},\\ 1,& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~false}. \end{cases}[/math] Если [math]M_1=\ldots= M_n=N[/math], то [math]\chi_{{}_P}[/math] — функция, входящая в круг наших рассмотрений, и имеет смысл поставить вопрос о ее примитивной рекурсивности. Определение 33.11. Предикат [math]P[/math] называется примитивно рекурсивным, если его характеристическая функция [math]\chi_{{}_P}[/math] примитивно рекурсивна. Отметим еще одно важное свойство, связанное с примитивной рекурсивностью функций. Мы используем его в последующих рассмотрениях. Одним из часто встречающихся, особенно в теории алгоритмов, способов задания функций является их задание с помощью так называемого оператора условного перехода. Этот оператор по функциям [math]f_1(x_1,\ldots,x_n),\,f_2(x_1,\ldots,x_n)[/math] и предикату [math]P(x_1,\ldots,x_n)[/math] строит функцию [math]\varphi\colon[/math] [math]\varphi(x_1,\ldots,x_n)= \begin{cases}f_1(x_1,\ldots,x_n),& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~true},\\ f_2(x_1,\ldots,x_n),& \text{if}~~ P(x_1,\ldots,x_n)~~\text{is~false}. \end{cases}[/math] Нетрудно понять, что с помощью характеристических функций предиката [math]P[/math] и его отрицания [math]\lnot P[/math] функцию [math]\varphi[/math] можно выразить следующим образом: [math]\varphi(x_1,\ldots,x_n)= f_1(x_1,\ldots,x_n)\cdot \chi_{{}_P}(x_1,\ldots,x_n)+ f_2(x_1,\ldots,x_n)\cdot \chi_{{}_{\lnot P}}(x_1,\ldots,x_n).[/math] Из этого выражения вытекает следующее утверждение. Теорема 33.12. Если функции [math]f_1,\,f_2[/math] и предикат [math]P[/math] примитивно рекурсивны, то и функция [math]\varphi[/math], построенная из [math]f_1,\,f_2,\,P[/math] с помощью оператора Условного перехода, примитивно рекурсивна. Этот факт выражают также говоря, что оператор условного перехода примитивно рекурсивен. Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом предикатов [math]P_1,\ldots,P_k[/math], из которых истинен всегда один и только один предикат. Ясно, что и в такой форме оператор условного перехода примитивно рекурсивен, так как и в этом случае производимую им функцию можно представить в аналогичном виде: [math]\varphi(x_1,\ldots,x_n)= f_1\cdot \chi_{{}_{P1}}+ \ldots+ f_k\cdot \chi_{{}_{Pk}}.[/math] Заметим, что это соотношение определяет [math]\varphi[/math] и в том случае, когда ни один из [math]P_1,\ldots,P_k[/math] не истинен: в этом случае [math]\varphi[/math] равно нулю. Последнее замечание позволяет доказать примитивную рекур-сивность функций, заданных на конечных множествах, ибо все их можно задать с помощью оператора условного перехода. Правда, при этом их придется доопределить с помощью какой-либо константы на всех остальных натуральных числах, на которых она не определена. Например, функцию ф, определенную на множестве [math]\{1,3,9,17\}[/math] равенствами [math]\varphi(1)=8,~ \varphi(3)=0,[/math] [math]\varphi(9)=4,~ \varphi(17)=6,[/math], с помощью оператора условного перехода можно описать так: [math]\varphi(x)= \begin{cases}8,&\text{if}\quad x=1,\\ 0,&\text{if}\quad x=3,\\ 4,&\text{if}\quad x=9,\\ 6,&\text{otherwise}. \end{cases}[/math] Таким образом, [math]\varphi(x)=6[/math] вне исходной области задания. В заключение обсуждения примитивно рекурсивных функций сделаем два важных замечания. Во-первых, все примитивно рекурсивные функции всюду определены. Это следует из того, что всюду определены простейшие функции, а операторы суперпозиции и примитивной рекурсии это свойство сохраняют. Во-вторых, строго говоря, мы имеем дело не с функциями, а с их примитивно рекурсивными описаниями. Различие здесь точно такое же, как и различие между булевыми функциями и их представлениями в виде формул. Примитивно рекурсивные описания также разбиваются на классы эквивалентности: в один класс входят все описания, задающие одну и ту же функцию. Но задача распознавания эквивалентности примитивно рекурсивных описаний являет собой еще один пример алгоритмически неразрешимой задачи. Вычислимость по Тьюрингу примитивно рекурсивных функцийТеперь мы готовы к тому, чтобы сделать еще один шаг на пути (в каком-то смысле аксиоматического) описания всех функций, вычислимых с помощью машины Тьюринга. Мы докажем, что всякая примитивно рекурсивная функция вычислима с помощью машины Тьюринга. Для этого остается доказать следующую теорему. Теорема 33.13. Функция [math]\varphi[/math], возникающая примитивной рекурсией из правильно вычислимых на машине Тьюринга функций [math]f[/math] и [math]g[/math], сама правильно вычислима на машине Тьюринга. ▼ Доказательство
Следствие 33.14. Всякая примитивно рекурсивная функция вычислима по Тьюрингу. Доказательство. Утверждение следует (ввиду определения 33.4 примитивно рекурсивной функции) из вычислимости по Тьюрингу простейших функций и свойств сохранения такой вычислимости операторами суперпозиции (теорема 33.2) и примитивной рекурсии (теорема 33.13). Функции АккерманаНапомним, что мы поставили задачу охарактеризовать вычислимые (с помощью какого-либо алгоритма) функции. Учитывая тезис Тьюринга, под алгоритмом достаточно понимать машину Тьюринга. После того как в предыдущем пункте было доказано, что всякая примитивно рекурсивная функция вычислима (по Тьюрингу), возникает обратный вопрос: исчерпывается ли класс вычислимых (по Тьюрингу) функций примитивно рекурсивными функциями, т.е. всякая ли вычислимая (по Тьюрингу) функция будет непременно примитивно рекурсивной? Применив теоретико-множественное понятие о мощности, достаточно легко ответить отрицательно на более общий вопрос: исчерпывается ли класс всех функций примитивно рекурсивными функциями, т. е. все ли функции являются примитивно рекурсивными? Теорема 33.15. Существуют функции, не являющиеся примитивно рекурсивными. Доказательство. В самом деле, нетрудно понять, что множество всех примитивно рекурсивных функций счетно. Это объясняется тем, что каждая примитивно рекурсивная функция имеет конечное описание, т.е. задается конечным словом в некотором (фиксированном для всех функций) алфавите. Множество всех конечных слов счетно. Поэтому и примитивно рекурсивных функций имеется не более, чем счетное множество. В то же время множество всех функций даже от одного аргумента из [math]N[/math] в [math]N[/math] имеет мощность континуума. Тем более, континуально множество функций из [math]N[/math] в [math]N[/math] от любого конечного числа аргументов. Таким образом непременно существуют функции, не являющиеся примитивно рекурсивными. Отрицательным будет также ответ и на более узкий вопрос, поставленный в предыдущем пункте: все ли вычислимые (а в силу тезиса Тьюринга — вычислимые по Тьюрингу) функции можно описать как примитивно рекурсивные? Чтобы это установить, необходимо привести пример вычислимой функции, не являющейся примитивно рекурсивной. Идея примера состоит в том, чтобы построить такую вычислимую функцию, которая обладала бы свойством, каким не обладает ни одна примитивно рекурсивная функция. Таким свойством может служить скорость роста функции. Итак, необходимо указать такую вычислимую функцию, которая растет быстрее любой примитивно рекурсивной функции и поэтому примитивно рекурсивной не является. Пример 33.16. Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей. ▼ Доказательство
Оператор минимизацииЭто — оператор наименьшего числа в определении 33.5. В более общем виде его можно определить как оператор, применяемый к произвольному (n+1)-местному предикату [math]P(x_1,\ldots, x_n,y)[/math] и дающий в результате n-местную функцию [math]\varphi(x_1,\ldots,x_n)[/math]. Значение [math]\varphi(a_1,\ldots,a_n)[/math] этой функции на наборе аргументов [math]a_1,\ldots,a_n[/math] равно наименьшему из таких чисел [math]y[/math], что высказывание [math]\mu y P(a_1,\ldots,a_n,y)[/math] истинно. Оно обозначается [math]\mu y P(a_1,\ldots,a_n,y)[/math]. Если же наименьшего среди таких чисел не существует, то значение функции [math]\varphi(x_1,\ldots,x_n)[/math] на этом наборе [math]a_1,\ldots,a_n[/math] не определено. (Это означает, что оператор минимизации может породить частичную, т. е. не всюду определенную функцию.) Таким образом, [math]\varphi(x_1,\ldots,x_n)= \mu yP(x_1,\ldots, x_n,y)[/math]. Оператор минимизации называется также оператором наименьшего числа, или µ-оператором. Предикат [math]P(x_1,\ldots,x_n,y)[/math] (заданный над [math]N[/math]), к которому при. меняется оператор минимизации, может быть сконструирован из двух числовых функций следующим образом: "[math]f_1(x_1,\ldots,x_n,y)= f_2(x_1,\ldots,x_n,y)[/math]", или из одной: "[math]f(x_1,\ldots, x_n,y)=0[/math]". Так что оператор минимизации можно рассматривать как оператор, заданный на множестве числовых функций и принимающий значения в нем же. В этом своем качестве оператор минимизации является удобным средством для построения обратных функций. Действительно, функция [math]f^{-1}(x)= \mu y[f(y)=x][/math] (наименьший [math]y[/math] такой, что [math]f(y)=x[/math]) является обратной для функции [math]f(x)[/math]. (Поэтому в применении к одноместным функциям оператор минимизации иногда называют оператором обращения.) Рассмотрим примеры действия оператора минимизации для получения обратных функций. ▼ Примеры 33.17-33.18
Общерекурсивные и частично рекурсивные функцииИтак, функция называется частично рекурсивной (определение 33.6), если она может быть построена из простейших функций [math]O,\,S,\,I_m^n[/math] с помощью конечного числа применений суперпозиции, примитивной рекурсии и µ-оператора. Если функция всюду определена и частично рекурсивна, то она называется общерекурсивной. Мы уже отмечали, что класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются функции, не всюду определенные, например функции [math]d(x,y)[/math] и [math]q(x,y)[/math], рассмотренные в примерах 33.17, 33.18, а также, например, нигде не определенная функция [math]f(x)= \mu y[x+1+y=0][/math]. Примером общерекурсивной, но не примитивно рекурсивной функции может служить и функция Аккермана [math]A(x)[/math]. Продолжим теперь продвижение к поставленной цели — к описанию всех функций, вычислимых на машинах Тьюринга. Следующий шаг — доказательство того, что все частично рекурсивные Функции вычислимы по Тьюрингу. Вычислимость по Тьюрингу частично рекурсивных функцийТеорема 33.19. Если функция [math]f(x,y)[/math] правильно вычислима на машине Тьюринга, то и функция [math]\varphi(x)= \mu y[f(x,y)=0][/math]. получающаяся с помощью оператора минимизации из функции [math]f(x,y)[/math], также правильно вычислима на машине Тьюринга. ▼ Доказательство
Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу. Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и операторы суперпозиции и примитивной рекурсии), простейшие функции [math]O,\,S,\,I_m^n[/math] вычислимы по Тьюрингу, а всякая частично рекурсивная функция получается из простейших с помощью применения конечного числа раз трех указанных операторов, то всякая частично рекурсивная функция вычислима по Тьюрингу. Частичная рекурсивность функций, вычислимых по ТьюрингуНаконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию [math]f(x_1,\ldots, x_n)[/math], можно построить рекурсивное описание этой функции. Эта теорема впервые была доказана Тьюрингом. Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна. ▼ Доказательство
Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме. Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна. Итог рассмотрений настоящей лекции состоит в том, что мы дали некую альтернативную характеристику вычислимым по Тьюрингу функциям: это те и только те функции, которые частично рекурсивны. Другими словами, класс функций, вычислимых по Тьюрингу, совпадает с классом частично рекурсивных функций. Совпадение этих двух классов вычислимых функций, в основе построения которых лежали совершенно разные подходы к формализации понятия вычислимости функции, говорит о том, что эти подходы оказались весьма состоятельными, и служит косвенным подтверждением того, что как тезис Тьюринга, так и тезис Чёрча не только не безосновательны, но и имеют все права на признание. |
Часовой пояс: UTC + 4 часа [ Летнее время ] |