Математический форум Math Help Planet
Обсуждение и решение задач по математике, физике, химии, экономике Теоретический раздел |
Часовой пояс: UTC + 3 часа [ Летнее время ] |
новый онлайн-сервис число, сумма и дата прописью |
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |
Рекурсивные функции | |
---|---|
Онлайн-сервисы
Нахождение НОД и НОК
Разложение числа на простые множители
Сравнения по модулю
Операции над множествами
Операции над векторами
Разложение вектора по базису. Доказательство, что векторы образуют базис
Чертёж треугольника по координатам вершин
Решение треугольника
Решение Пирамиды
Построение Пирамиды по координатам вершин
Чертёж многоугольника по координатам вершин
Решение систем методом Крамера и Матричным
Онлайн построение графика кривой 2-го порядка
Определение вида кривой или поверхности 2-го порядка по инвариантам
МНК и регрессионный анализ Онлайн + графики
Онлайн число, сумма и дата прописью
Алгоритмы JavaScript
Алгоритмы поиска
Алгоритмы сортировки
Уникальные элементы массива
Объединение, пересечение и разность массивов
НОД и НОК
Операции над матрицами
Дата прописью
Введение в анализ
Функции: понятие, определение, графики
Непрерывность функции
Исследование функции и построение графика
Теория множеств
Множества: понятие, определение, примеры
Точечные множества
Замкнутые и открытые множества
Мера множества
Группы, кольца, поля в математике
Поле комплексных чисел
Кольцо многочленов
Основная теорема алгебры и ее следствия
Математическая логика
Алгебра высказываний
Аксиоматика и логические рассуждения
Методы доказательств теорем
Алгебра высказываний и операции над ними
Формулы алгебры высказываний
Тавтологии алгебры высказываний
Логическая равносильность формул
Нормальные формы для формул высказываний
Логическое следование формул
Приложение алгебры высказываний для теорем
Дедуктивные и индуктивные умозаключения
Решение логических задач
Принцип полной дизъюнкции
Булевы функции
Множества, отношения и функции в логике
Булевы функции от одного и двух аргументов
Булевы функции от n аргументов
Системы булевых функций
Применение булевых функций к релейно-контактным схемам
Релейно-контактные схемы в ЭВМ
Практическое применение булевых функций
Теория формального
Формализованное исчисление высказываний
Полнота и другие свойства формализованного исчисления высказываний
Независимость системы аксиом формализованного исчисления высказываний
Логика предикатов
Логика предикатов
Логические операции над предикатами
Кванторные операции над предикатами
Формулы логики предикатов
Тавтологии логики предикатов
Преобразования формул и следование их предикатов
Проблемы разрешения для общезначимости и выполнимости формул
Применение логики предикатов в математике
Строение математических теорем
Аристотелева силлогистика и методы рассуждений
Принцип полной дизъюнкции в предикатной форме
Метод полной математической индукции
Необходимые и достаточные условия
Логика предикатов и алгебра множеств
Формализованное исчисление предикатов
Неформальные и формаль-ные аксиоматические теории
Неформальные аксиоматические теории
Свойства аксиоматических теорий
Формальные аксиоматические теории
Формализация теории аристотелевых силлогизмов
Свойства формализованного исчисления предикатов
Формальные теории первого порядка
Формализация математической теории
Теория алгоритмов
Интуитивное представление об алгоритмах
Машины Тьюринга и тезис
Рекурсивные функции
Нормальные алгоритмы Маркова
Разрешимость и перечислимость множеств
Неразрешимые алгоритмические проблемы
Теорема Гёделя о неполноте формальной арифметики
Математическая логика и компьютеры
Дискретная математика
Множества и отношения
Теория множеств: понятия и определения
Операции над множествами
Кортеж и декартово произведение множеств
Соответствия и бинарные отношения на множествах
Операции над соответствиями на множествах
Семейства множеств
Специальные свойства бинарных отношений
Отношения эквивалентности на множестве
Упорядоченные множества
Теорема о неподвижной точке
Мощность множества
Парадокс Рассела
Метод характеристических функций
Группы и кольца
Алгебраические структуры и операции
Группоиды, полугруппы, группы
Кольца, тела, поля
Области целостности в теории колец
Модули и линейные пространства
Подгруппы и подкольца
Теорема Лагранжа о порядке конечной группы
Гомоморфизмы групп и нормальные делители
Гомоморфизмы и изоморфизмы колец
Алгебра кватернионов
Полукольца и булевы алгебры
Полукольца: определение, аксиомы, примеры
Замкнутые полукольца
Полукольца и системы линейных уравнений
Булевы алгебры и полукольца
Решетки и полурешетки
Алгебраические системы
Алгебраические системы: модели и алгебры
Подсистемы алгебраических систем
Конгруэнции и фактор-системы
Гомоморфизмы алгебраических систем
Прямые произведения алгебраических систем
Конечные булевы алгебры
Многосортные алгебры
Теория графов
Теория графов: основные понятия и определения
Способы представления графов
Неориентированные и ориентированные деревья
Остовное дерево и алгоритм Краскала
Методы систематического обхода вершин графа
Алгоритмы поиска в глубину и ширину в графах
Задача о путях во взвешенных ориентированных графах
Изоморфизм, гомоморфизм и автоморфизм графов
Топологическая сортировка вершин графа
Элементы цикломатики в теории графов
Булева алгебра и функции
Булевы функции и булев куб
Таблицы булевых функций и булев оператор
Равенство булевых функций. Фиктивные переменные
Формулы и суперпозиции булевых функций
Дизъюнктивные и конъюнктивные нормальные формы
Построение минимальных ДНФ
Теорема Поста и классы
Критерий Поста
Схемы из функциональных элементов
Конечные автоматы и регулярные языки
Конечные автоматы и регулярные языки
Алфавит, слово, язык в программировании
Порождающие грамматики (грамматики Хомского)
Классификация грамматик и языков
Регулярные языки и регулярные выражения
Конечные автоматы
Допустимость языка конечным автоматом
Теорема Клини
Детерминизация конечных автоматов
Минимизация конечных автоматов
Лемма о разрастании для регулярных языков
Обоснование алгоритма детерминизации автоматов
Конечные автоматы с выходом
Морфизмы и конечные подстановки
Машины Тьюринга
Контекстно-свободные языки
Контекстно-свободные языки и грамматики
Приведенная форма КС-грамматики
Лемма о разрастании для КС-языков
Магазинные автоматы (автомат с магазинной памятью)
Алгоритм построения МП-автомата по КС-грамматике
Алгоритм построения КС-грамматики по МП-автомату
Алгебраические свойства КС-языков
Основное свойство суперпозиции КС-языков
Пересечение контекстно-свободных языков
Методы синтаксического анализа КС-языков
Восходящий синтаксический анализ и LR(k)-грамматики
Семантика формальных языков
Принцип индукции по неподвижной точке
Графовое представление МП-автоматов
Интегральное исчисление
Неопределённый и определённый
Неопределенный и определенный интегралы
Свойства интегралов
Интегрирование по частям
Интегрирование методом замены переменной
Интегрирование различных рациональных функций
Интегрирование различных иррациональных функций
Интегрирование различных тригонометрических функций
Определенный интеграл и его основные свойства
Необходимое и достаточное условие интегрируемости
Теоремы существования первообразной
Свойства определенных интегралов
Несобственные интегралы
Интегральное определение логарифмической функции
Приложения интегралов
Вычисление площадей плоских фигур
Площади фигур в различных координатах
Вычисление объемов тел с помощью интегралов
Объём тела вращения
Вычисление длин дуг кривых
Формулы длины дуги регулярной кривой
Кривизна плоской кривой
Площадь поверхности вращения тела
Интегралы в физике
Статические моменты и координаты центра тяжести
Теоремы Гульдина–Паппа
Вычисление моментов инерции
Другие приложения интегралов в физике
Основные интегралы
Вариационное исчисление
Примеры вариационных задач
Дифференциальное уравнение Эйлера
Функционалы, зависящие от нескольких функций
Задача о минимуме кратного интеграла
Финансовый анализ
Анализ эффективности
Критерии и показатели эффективности предприятия
Методы анализа эффективности деятельности
Факторный анализ прибыли от операционной деятельности
Анализ безубыточности предприятия
Операционный рычаг и эффект финансового рычага
Анализ и оценка состава, структуры и динамики доходов и расходов
Анализ рентабельности и резервов устойчивого роста капитала
Анализ распределения прибыли предприятия
Анализ и оценка чувствительности показателей эффективности
Анализ устойчивости
Финансовая устойчивость и долгосрочная платежеспособность
Характеристика типов финансовой устойчивости
Рыночная активность
Финансовый анализ рыночной активности
Методика анализа рыночной активности
Анализ и оценка дивидендного дохода на одну акцию
Инвестиционная деятельность
Инвестиции: экономическая сущность и классификация
Государственное регулирование инвестиционной деятельности
Источники финансовых ресурсов на капитальные вложения
Инвестиции в основные фонды
Оценка состояния основных фондов
Амортизация основных фондов
Капитальное строительство в инвестиционном процессе
Планирование инвестиций в форме капитальных вложений
Экономическая эффективность инвестиций
Финансирование капитальных вложений
Кредитование капитальных вложений
Кредитоспособность
Финансирование и кредитование затрат
Финансирование и кредитование инвестиционной деятельности потребительской кооперации
Финансирование и кредитование капитальных вложений потребительской кооперации
Инвестиционное строительное проектирование
Анализ инвестиций
Инвестиции и инвестиционная деятельность предприятия
Задачи финансового анализа инвестиций предприятия
Учет фактора времени в инвестиционной деятельности
Аннуитет и финансовая рента в инвестициях
Учет фактора инфляции при инвестировании
Оценка фактора риска инвестиционного проекта
Методы оценки эффективности инвестиций
Показатели эффективности инвестиционного проекта
Стоимость компании
Концепция построения международных стандартов финансовой отчетности (МСФО)
Экономическое содержание международных стандартов финансовой отчётности
Цели и принципы оценки стоимости акций и активов компании
Оценка акций и активов предприятия по справедливой стоимости
Методы оценки справедливой стоимости акций предприятия
Затратный подход к оценки стоимости компаний и акций
Сравнительный подход к оценки стоимости предприятий и акций
Доходный подход к оценке стоимости компании и акций
Выбор ставки дисконтирования при инвестировании в акции
Метод капитализации прибыли
Сравнение подходов к оценке стоимости компаний и пакетов акций
Форвардные контракты
Форвардный контракт и цена
Форвардная цена акции на бирже
Цена форвардного контракта инвестора
Форвардная цена акции с учетом величины дивиденда
Форвардная цена акции с учетом ставки дивиденда
Форвардная цена валюты на рынке форекс
Форвардный валютный курс и инфляция на рынке
Форвардная цена товара и спотовый рынок
Форвардная цена при различии ставок по кредитам и депозитам
Синтетический форвардный контракт на акции и валюту
Теория вероятностей
Основные понятия теории вероятностей
Зависимые и независимые случайные события
Повторные независимые испытания
Формула Бернулли
Одномерные случайные величины
Многомерные случайные величины
Функции случайных величин
Законы распределения целочисленных случайных величин
Законы распределения непрерывных случайных величин
Предельные теоремы теории вероятностей
Закон больших чисел и предельные теоремы
Вероятностные закономерности
Математическая статистика
Элементы математической статистики
Выборочный метод
Оценки параметров генеральной совокупности
Статистические гипотезы
Критерии согласия
Теоретические и эмпирические частоты
Теория очередей (СМО)
Определение системы массового обслуживания
Уравнения Колмогорова
Предельные вероятности состояний
Определение СМО с отказами
Определение СМО с ожиданием (очередью)
Аналитическая геометрия
Векторная алгебра
Метрические понятия и аксиомы геометрии
Равенство и подобие геометрических фигур
Бинарные отношения
Вектор, его направление и длина
Линейные операции над векторами
Линейная зависимость и независимость векторов
Отношение коллинеарных векторов
Проекции векторов на прямую и на плоскость
Угол между векторами
Ортогональные проекции векторов
Координата вектора на прямой и базис
Координаты вектора на плоскости и базис
Координаты вектора в пространстве и базис
Операции над векторами в координатной форме
Ортогональный и ортонормированный базисы
Cкалярное произведение векторов и его свойства
Выражение скалярного произведения через координаты векторов
Векторное произведение векторов и его свойства
Смешанное произведение векторов и его свойства
Ориентированные площади и объемы
Двойное векторное произведение и его свойства
Применение векторов в задачах на аффинные свойства фигур
Применение произведений векторов при решении геометрических задач
Применение векторной алгебры в механике
Системы координат
Прямоугольные координаты
Преобразования прямоугольных координат
Полярная система координат
Цилиндрическая система координат
Сферические координаты
Аффинные координаты
Аффинные преобразования координат
Аффинные преобразования плоскости
Примеры аффинных преобразований плоскости
Аффинные преобразования пространства
Многомерное координатное пространство
Линейные и аффинные подпространства
Скалярное произведение n-мерных векторов
Преобразования систем координат
Геометрия на плоскости
Алгебраические линии на плоскости
Общие уравнения геометрических мест точек
Алгебраические уравнения линий на плоскости
Уравнения прямой, проходящей через точку перпендикулярно вектору
Уравнения прямой, проходящей через точку коллинеарно вектору
Уравнения прямой, проходящей через две точки
Уравнения прямой с угловым коэффициентом
Взаимное расположение прямых
Примеры задач с прямыми на плоскости
Системы неравенств с двумя неизвестными
Системы линейных уравнений с двумя неизвестными
Линии 2-го порядка
Канонические уравнения линий второго порядка
Порядок приведения уравнения линии к каноническому виду
Эллипс
Гипербола
Парабола
Квадратичные неравенства с двумя неизвестными
Применение линий 1-го и 2-го порядков в задачах на экстремум функций
Инварианты линий
Классификация линий 2-го порядка по инвариантам
Приведение уравнения линии к каноническому виду по инвариантам
Геометрия в пространстве
Способы задания ГМТ в пространстве
Алгебраические уравнения поверхностей
Уравнения плоскости, проходящей через точку перпендикулярно вектору
Уравнения плоскости, компланарной двум неколлинеарным векторам
Уравнения плоскости, проходящей через три точки
Взаимное расположение плоскостей
Типовые задачи с плоскостями
Уравнения прямых в пространстве
Взаимное расположение прямых в пространстве
Типовые задачи с прямыми в пространстве
Поверхности 2-го порядка
Канонические уравнения поверхностей
Порядок приведения уравнения поверхности к каноническому виду
Поверхности второго порядка
Эллипсоиды
Гиперболоиды
Конусы
Параболоиды
Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций
Инварианты поверхностей
Линейная алгебра
Матрицы и операции
Линейные операции над матрицами
Умножение матриц
Возведение матриц в степень
Многочлены от матриц
Транспонирование и сопряжение матриц
Блочные матрицы
Произведение и сумма матриц Кронекера
Метод Гаусса приведения матрицы к ступенчатому виду
Элементарные преобразования матриц
Определители
Определители матриц и их основные свойства
Формула полного разложения определителя
Формула Лапласа полного разложения определителя
Определитель произведения матриц
Методы вычисления определителей
Ранг матрицы
Линейная зависимость и линейная независимость строк (столбцов) матрицы
Ранг матрицы и базисный минор матрицы
Методы вычисления ранга матрицы
Ранг системы столбцов (строк)
Обратная матрица
Обратные матрицы и их свойства
Ортогональные и унитарные матрицы
Способы нахождения обратной матрицы
Матричные уравнения
Односторонние обратные матрицы
Скелетное разложение матрицы
Полуобратная матрица
Псевдообратная матрица
Системы уравнений
Системы линейных алгебраических уравнений
Метод Гаусса решения систем линейных уравнений
Структура общего решения системы уравнений
Решение систем с помощью полуобратных матриц
Псевдорешения системы линейных уравнений
Функциональные матрицы
Функциональные матрицы скалярного аргумента
Производные матриц по векторному аргументу
Линейные и квадратичные формы и их преобразования
Приведение форм к каноническому виду
Закон инерции вещественных квадратичных форм
Знакоопределенность форм вещественных квадратичных
Формы и исследование функций на экстремум
Многочленные матрицы
Многочленные матрицы (лямбда-матрицы)
Операции над лямбда-матрицами
Простые преобразования многочленных матриц
Инвариантные множители многочленной матрицы
Функции от матриц
Собственные векторы и значения матрицы
Подобие числовых матриц
Характеристический многочлен матрицы
Минимальный многочлен матрицы
Теорема Гамильтона-Кэли
Жорданова форма матрицы
Приведение матрицы к жордановой форме
Многочлены от матриц
Применение многочленов от матриц
Функции от матриц
Линейные пространства
Линейные пространства: определение и примеры
Линейная зависимость и независимость n-мерных векторов
Размерность и базис линейного пространства
Преобразования координат в линейном пространстве
Изоморфизм линейных пространств
Подпространства
Подпространства линейного пространства
Пересечение и сумма подпространств
Способы описания подпространств
Нахождение дополнения и суммы подпространств
Нахождение пересечения подпространств
Линейные отображения
Линейные многообразия
Линейные отображения
Матрица линейного отображения
Ядро и образ линейного отображения
Линейные операторы
Линейные операторы (преобразования)
Инвариантные подпространства
Собственные векторы и значения оператора
Свойства собственных векторов операторов
Канонический вид линейного оператора
Методика приведения линейного преобразования к каноническому виду
Евклидовы пространства
Евклидовы пространства
Ортогональные векторы евклидова пространства
Ортогональный базис евклидова пространства
Ортонормированный базис евклидова пространства
Ортогональные дополнения в евклидовом пространстве
Задача о перпендикуляре
Матрица и определитель Грама и его свойства
Линейные преобразования евклидовых пространств
Канонический вид ортогонального оператора евклидова пространства
Сопряженные операторы евклидова пространства
Самосопряженные операторы евклидова пространства
Приведение квадратичной формы к главным осям
Унитарные пространства и их линейные преобразования
Комплексный анализ
Комплексные числа
Комплексные числа в алгебраической форме
Комплексные числа в тригонометрической и показательной формах
Множества на комплексной плоскости
Последовательности и ряды комплексных чисел
Комплексные функции
Функции комплексного переменного. Предел, непрерывность и производная
Элементарные функции комплексного переменного
Дифференцирование функций комплексного переменного
Аналитические функции и их свойства
Конформные отображения
Функциональные ряды в комплексной области
и их свойства Интегрирование функций комплексного переменного
Функциональные ряды и последовательности
Степенные ряды и их свойства
Разложение функций в степенные ряды
Нули аналитических функций
Ряд Лорана и разложение функций по целым степеням
Особые точки, Вычеты
Изолированные особые точки функций и полюсы
Вычеты и их применение
Вычисление интегралов с помощью вычетов
Вычеты и расположение нулей многочлена
Операционное исчисление
Дифференциальные уравнения
ДУ первого порядка
Основные понятия и определения ДУ
Метод изоклин для ДУ 1-го порядка
Метод последовательных приближений
ДУ с разделяющимися переменными
Однородные ДУ
Линейные ДУ 1-го порядка
Дифференциальное уравнение Бернулли
ДУ в полных дифференциалах
Интегрирующий множитель
ДУ, не разрешенные относительно производной
Дифференциальное уравнение Риккати
Составление ДУ семейств линий
Задачи на траектории
Особые решения ДУ
ДУ высших порядков
Понятия и определения ДУ высших порядков
ДУ, допускающие понижение порядка
Линейная независимость функций
Определители Вронского и Грама
Однородные и неоднородные дифференциальные уравнения
Задача Коши и Уравнение Эйлера
Линейные ДУ с переменными коэффициентами
Метод Лагранжа решения ДУ
Краевые задачи для ДУ высших порядков
Разложение решения ДУ в степенной ряд
Разложение решения ДУ в обобщенный степенной ряд
Нахождение периодических решений ДУ
Асимптотическое интегрирование ДУ
Системы ДУ
Системы ДУ: понятия и определения
Сведение системы ДУ к одному уравнению
Нахождение интегрируемых комбинаций
Интегрирование однородных линейных систем ДУ
Методы интегрирования неоднородных систем ДУ
Преобразование Лапласа и решение ДУ и систем
Теория устойчивости
Численные методы
Методы алгебры
Численные методы линейной алгебры
Численные методы решения СЛАУ
Итерационный метод Шульца обратной матрицы
Методы решения задач о собственных значениях и векторах матрицы
Методы решения нелинейных уравнений
Методы решения систем нелинейных уравнений
Методы теории приближений
Методы приближения сеточных функций
Методы функциональной интерполяции
Методы интегрально-дифференциальной интерполяции
Методы интегрального сглаживания
Методы интерполяции и сглаживания сплайнами
Методы численного дифференцирования и интегрирования
Методы численного дифференцирования
Методы численного интегрирования
Методы решения обыкновенных ДУ
Численные методы решения задачи Коши
Разностные схемы для решения задачи Коши
Составные схемы для решения задачи Коши
Экстраполяционные методы решения задачи Коши
Непрерывно-дискретные методы решения задачи Коши
Численные методы решения краевых задач
Методы решения ДУ в частных производных
Численные методы решения уравнений математической физики с двумя переменными
Принципы построения разностных схем для уравнений в частных производных
Разностные схемы решения уравнений в частных производных 1-го порядка
Разностные схемы решения уравнений в частных производных 2-го порядка
Численные методы решения уравнений в частных производных
Численные методы решения уравнений математической физики с тремя переменными
|
Рекурсивные функцииПонятие машины Тьюринга — не единственный известный путь уточнения понятия алгоритма. В настоящем и следующем параграфах будут рассмотрены еще два способа такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова. Происхождение рекурсивных функцийВсякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий. Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 1930-х гг. теории рекурсивных функций. При этом класс вычислимых функций (названных здесь рекурсивными) получил такое описание, которое весьма напомнило процесс построения аксиоматической теории на базе некоторой системы аксиом. Сначала были выбраны простейшие функции, эффективная вычисляемость которых была очевидна (своего рода "аксиомы"). Затем сформулированы некоторые правила (названные операторами), на основе которых можно строить новые функции из уже имеющихся (своего рода "правила вывода"). Тогда требуемым классом функций будет совокупность всех функций, получающихся из простейших с помощью выбранных операторов. Наша цель будет состоять в том, чтобы доказать, что этот класс функций совпадет с классом функций, вычислимых с помощью машин Тьюринга. Идея доказательства этого утверждения в одну сторону проста: сначала доказать вычислимость по Тьюрингу простейших функций, а затем вычислимость по Тьюрингу функций, получающихся из вычислимых по Тьюрингу функций с помощью выбранных операторов. Основные понятия теории рекурсивных функций и тезис ЧёрчаПриступим к построению класса рекурсивных функций в соответствии с изложенными принципами. Напомним, что рассматриваются функции, заданные на множестве натуральных чисел и принимающие натуральные значения. Функции предполагается брать частичные, т. е. определенные, вообще говоря, не для всех значений аргументов. В качестве исходных простейших функций выберем следующие: Вычислимость (более того, правильная вычислимость) этих функций с помощью машины Тьюринга установлена в примерах 32.7 и 32.10. Далее, в качестве операторов, с помощью которых будут строиться новые функции, выберем следующие три: операторы суперпозиции, примитивной рекурсии и минимизации. Определение 33.1 (оператор суперпозиции). Будем говорить, что n-местная функция Понятие суперпозиции функций и сложной функции хорошо известно, но нас сейчас этот оператор интересует с точки зрения его взаимоотношений с процессом вычислимости функций с помощью машин Тьюринга. Теорема 33.2. Если функции ДоказательствоРуководствуясь определением 32.9 композиции машин Тьюринга, нетрудно понять, что если машина Рассмотрим более сложную суперпозицию вычислимых функций: Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию Подстановки указанного вида достаточно специфичны (все функции Поэтому можно считать, что теорема полностью доказана. Определение 33.3. Говорят, что (n+1)-местная функция Пара этих равенств называется схемой примитивной рекурсии. Здесь важно отметить то, что, независимо от числа аргументов в Определение 33.4. Функция называется примитивно рекурсивной, если она может быть получена из простейших функций Наконец, введем заключительный, третий, оператор. Определение 33.5 (оператор минимизации). Будем говорить, что n-местная функция а В частном случае может быть Определение 33.6. Функция называется частично рекурсивной, если она может быть получена из простейших функций Ясно, что всякая примитивно рекурсивная функция будет и частично рекурсивной (и даже общерекурсивной, так как каждая примитивно рекурсивная функция всюду определена), поскольку для построения частично рекурсивных функций из простейших используется больше средств, чем для построения примитивно рекурсивных функций. В то же время класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются и функции не всюду определенные. Понятие частично рекурсивной функции оказалось исчерпывающей формализацией понятия вычислимой функции. При построении аксиоматической теории высказываний исходные формулы (аксиомы) и правила вывода выбирались так, чтобы полученные в теории формулы исчерпали бы все тавтологии алгебры высказываний. К чему же стремимся мы в теории рекурсивных функций, почему именно так выбрали простейшие функции и операторы для получения новых функций? Рекурсивными функциями мы стремимся исчерпать все мыслимые функции, поддающиеся вычислению с помощью какой-нибудь определенной процедуры механического характера. Подобно тезису Тьюринга, в теории рекурсивных функций выдвигается соответствующая естественно-научная гипотеза, носящая название тезиса Чёрча: Числовая функция тогда и только тогда алгоритмически (или машинно) вычислима, когда она частично рекурсивна. И эта гипотеза не может быть доказана строго математически, она подтверждается практикой, опытом, ибо призвана увязать практику и теорию. Все рассматривавшиеся в математике конкретные функции, признаваемые вычислимыми в интуитивном смысле, оказывались частично рекурсивными. Теперь мы рассмотрим более подробно классы примитивно рекурсивных функций и частично рекурсивных функций и докажем, что все функции из каждого из этих классов вычислимы на подходящих машинах Тьюринга. Примитивно рекурсивные функцииИтак, функция примитивно рекурсивна, если она может быть получена из простейших функций ▼ Примеры 33.7-33.9
Теорема 33.10. Функция, полученная суперпозицией примитивно рекурсивных функций, сама примитивно рекурсивна. Доказательство. В самом деле, компоненты этой функции получены из простейших функций Примитивная рекурсивность предикатовОпределив ранее понятие предиката, мы отметили, что к этому понятию возможен и еще один подход. Предикат Если Определение 33.11. Предикат Отметим еще одно важное свойство, связанное с примитивной рекурсивностью функций. Мы используем его в последующих рассмотрениях. Одним из часто встречающихся, особенно в теории алгоритмов, способов задания функций является их задание с помощью так называемого оператора условного перехода. Этот оператор по функциям Нетрудно понять, что с помощью характеристических функций предиката Из этого выражения вытекает следующее утверждение. Теорема 33.12. Если функции Оператор условного перехода может иметь и более общую форму, когда переход носит не двузначный, а многозначный характер и определяется конечным числом предикатов Заметим, что это соотношение определяет Последнее замечание позволяет доказать примитивную рекур-сивность функций, заданных на конечных множествах, ибо все их можно задать с помощью оператора условного перехода. Правда, при этом их придется доопределить с помощью какой-либо константы на всех остальных натуральных числах, на которых она не определена. Например, функцию ф, определенную на множестве Таким образом, В заключение обсуждения примитивно рекурсивных функций сделаем два важных замечания. Во-первых, все примитивно рекурсивные функции всюду определены. Это следует из того, что всюду определены простейшие функции, а операторы суперпозиции и примитивной рекурсии это свойство сохраняют. Во-вторых, строго говоря, мы имеем дело не с функциями, а с их примитивно рекурсивными описаниями. Различие здесь точно такое же, как и различие между булевыми функциями и их представлениями в виде формул. Примитивно рекурсивные описания также разбиваются на классы эквивалентности: в один класс входят все описания, задающие одну и ту же функцию. Но задача распознавания эквивалентности примитивно рекурсивных описаний являет собой еще один пример алгоритмически неразрешимой задачи. Вычислимость по Тьюрингу примитивно рекурсивных функцийТеперь мы готовы к тому, чтобы сделать еще один шаг на пути (в каком-то смысле аксиоматического) описания всех функций, вычислимых с помощью машины Тьюринга. Мы докажем, что всякая примитивно рекурсивная функция вычислима с помощью машины Тьюринга. Для этого остается доказать следующую теорему. Теорема 33.13. Функция ДоказательствоДля краткости записей будем считать, что функция Начальная конфигурация такова: На последнем шаге, применив машину, вычисляющую функцию Теперь мы можем приступить к вычислению Теперь мы можем применить машину Применим к этой конфигурации команду: Начинается следующий цикл, осуществляемый командами идущими после первого появления состояния Дополнительные команды Следствие 33.14. Всякая примитивно рекурсивная функция вычислима по Тьюрингу. Доказательство. Утверждение следует (ввиду определения 33.4 примитивно рекурсивной функции) из вычислимости по Тьюрингу простейших функций и свойств сохранения такой вычислимости операторами суперпозиции (теорема 33.2) и примитивной рекурсии (теорема 33.13). Функции АккерманаНапомним, что мы поставили задачу охарактеризовать вычислимые (с помощью какого-либо алгоритма) функции. Учитывая тезис Тьюринга, под алгоритмом достаточно понимать машину Тьюринга. После того как в предыдущем пункте было доказано, что всякая примитивно рекурсивная функция вычислима (по Тьюрингу), возникает обратный вопрос: исчерпывается ли класс вычислимых (по Тьюрингу) функций примитивно рекурсивными функциями, т.е. всякая ли вычислимая (по Тьюрингу) функция будет непременно примитивно рекурсивной? Применив теоретико-множественное понятие о мощности, достаточно легко ответить отрицательно на более общий вопрос: исчерпывается ли класс всех функций примитивно рекурсивными функциями, т. е. все ли функции являются примитивно рекурсивными? Теорема 33.15. Существуют функции, не являющиеся примитивно рекурсивными. Доказательство. В самом деле, нетрудно понять, что множество всех примитивно рекурсивных функций счетно. Это объясняется тем, что каждая примитивно рекурсивная функция имеет конечное описание, т.е. задается конечным словом в некотором (фиксированном для всех функций) алфавите. Множество всех конечных слов счетно. Поэтому и примитивно рекурсивных функций имеется не более, чем счетное множество. В то же время множество всех функций даже от одного аргумента из Отрицательным будет также ответ и на более узкий вопрос, поставленный в предыдущем пункте: все ли вычислимые (а в силу тезиса Тьюринга — вычислимые по Тьюрингу) функции можно описать как примитивно рекурсивные? Чтобы это установить, необходимо привести пример вычислимой функции, не являющейся примитивно рекурсивной. Идея примера состоит в том, чтобы построить такую вычислимую функцию, которая обладала бы свойством, каким не обладает ни одна примитивно рекурсивная функция. Таким свойством может служить скорость роста функции. Итак, необходимо указать такую вычислимую функцию, которая растет быстрее любой примитивно рекурсивной функции и поэтому примитивно рекурсивной не является. Пример 33.16. Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей. ДоказательствоНачнем с построения такой последовательности. Мы знаем, что произведение растет быстрее суммы, а степень — быстрее произведения. Начнем построение последовательности именно с этих функций, введя для них единообразные обозначения: Эти функции связаны между собой следующими рекурсивными соотношениями: Продолжим эту последовательность, положив по определению для (1) (Первое из равенств (1) предназначено для того, чтобы функции Зафиксируем теперь значение Для функции (2) которые позволяют вычислять значение функции то вычислению Итак, функция Идея доказательства этого утверждения состоит в следующем. Сначала доказываются два свойства функции Затем вводится понятие B-мажорируемой функции. Функция Доказывается, что все примитивно рекурсивные функции B-мажорируемы. (Сначала устанавливается B-мажорируемость простейших функций Наконец, рассмотрим произвольную примитивно рекурсивную функцию Итак, функция Аккермана Оператор минимизацииЭто — оператор наименьшего числа в определении 33.5. В более общем виде его можно определить как оператор, применяемый к произвольному (n+1)-местному предикату Предикат В этом своем качестве оператор минимизации является удобным средством для построения обратных функций. Действительно, функция Рассмотрим примеры действия оператора минимизации для получения обратных функций. ▼ Примеры 33.17-33.18
Общерекурсивные и частично рекурсивные функцииИтак, функция называется частично рекурсивной (определение 33.6), если она может быть построена из простейших функций Мы уже отмечали, что класс частично рекурсивных функций шире класса примитивно рекурсивных функций, так как все примитивно рекурсивные функции всюду определены, а среди частично рекурсивных функций встречаются функции, не всюду определенные, например функции Продолжим теперь продвижение к поставленной цели — к описанию всех функций, вычислимых на машинах Тьюринга. Следующий шаг — доказательство того, что все частично рекурсивные Функции вычислимы по Тьюрингу. Вычислимость по Тьюрингу частично рекурсивных функцийТеорема 33.19. Если функция ДоказательствоОбозначим Далее подбираем команды, которые при условии Последняя команда зацикливает программу, и машина от конфигурации Теорема доказана. Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу. Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и операторы суперпозиции и примитивной рекурсии), простейшие функции Частичная рекурсивность функций, вычислимых по ТьюрингуНаконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна. ДоказательствоПрежде чем приступить к доказательству теоремы, обратим внимание на следующее обстоятельство. Машина Тьюринга, преобразовывающая слова в алфавите Разделим доказательство на этапы (их будет пять). Первый этап. Арифметизация машин Тьюринга начинается с того, что мы вводим в машину своего рода арифметическую систему координат. Эта система координат предназначена для конфигураций машины. Как известно, в каждый момент времени конфигурация на ленте машины Тьюринга имеет вид Завершим кодирование элементов машины Тьюринга. Символу Тогда, например, если мы имеем машину Тьюринга с внешним алфавитом Далее, Второй этап. При таком кодировании система команд машины Тьюринга с алфавитом Например, если среди команд машины Тьюринга имеется команда где Отметим, что все эти функции Третий этап. Выполнив одну команду, машина Тьюринга преобразует имеющуюся на ленте конфигурацию Например, при команде Так будет происходить почти со всеми конфигурациями, связанными с алфавитами При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага. Иначе говоря, Рассмотрим теперь функцию Итак, для функции Совершенно аналогичная, но в определенном смысле двойственная картина наблюдается и для функции Наконец, рассмотрим функцию Теперь сделаем выводы. В полученных выражениях для функций Итак, мы доказали, что на каждом шаге любая машина Тьюринга осуществляет примитивно рекурсивное вычисление. Четвертый этап. Рассмотрим теперь с точки зрения введенной арифметизации работу машины Тьюринга в целом. Пусть задана начальная конфигурация (В записях для функций Эти соотношения представляют собой схемы примитивной рекурсии, определяющие функции Пятый этап. Наконец, на заключительном шаге доказательства покажем, что результат работы машины Тьюринга (т.е. вычисляемая машиной функция) носит рекурсивный характер. (Обратите внимание: не примитивно рекурсивный, а рекурсивный, т. е. здесь придется использовать оператор минимизации Здесь мы докажем утверждение, обратное тому, которое было доказано в предыдущем пункте: всякая функция, правильно вычислимая на машине Тьюринга, частично рекурсивна. Пусть Учитывая, что где Этим и завершается доказательство того, что всякая вычислимая по Тьюрингу функция частично рекурсивна. Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме. Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна. Итог рассмотрений настоящей лекции состоит в том, что мы дали некую альтернативную характеристику вычислимым по Тьюрингу функциям: это те и только те функции, которые частично рекурсивны. Другими словами, класс функций, вычислимых по Тьюрингу, совпадает с классом частично рекурсивных функций. Совпадение этих двух классов вычислимых функций, в основе построения которых лежали совершенно разные подходы к формализации понятия вычислимости функции, говорит о том, что эти подходы оказались весьма состоятельными, и служит косвенным подтверждением того, что как тезис Тьюринга, так и тезис Чёрча не только не безосновательны, но и имеют все права на признание.
Математический форум (помощь с решением задач, обсуждение вопросов по математике).
Если заметили ошибку, опечатку или есть предложения, напишите в комментариях.
|
Часовой пояс: UTC + 3 часа [ Летнее время ] |