Часовой пояс: UTC + 4 часа [ Летнее время ]

Рекурсивные функции
Онлайн-сервисы Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики Алгоритмы JavaScript Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами Введение в анализ Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика Теория множеств Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия Математическая логика Алгебра высказываний Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции Булевы функции Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций Теория формального Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний Логика предикатов Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов Неформальные и формаль- ные аксиоматические теории Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории Теория алгоритмов Интуитивное представление об алгоритмах Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики Математическая логика и компьютеры Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект Дискретная математика Множества и отношения Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций Группы и кольца Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов Полукольца и булевы алгебры Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки Алгебраические системы Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры Теория графов Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов Булева алгебра и функции Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов Конечные автоматы и регулярные языки Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга Контекстно-свободные языки Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов Интегральное исчисление Неопределённый и определённый Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции Приложения интегралов Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела Интегралы в физике Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике Основные интегралы Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега Вариационное исчисление Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла Финансовый анализ Анализ эффективности Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности Анализ устойчивости Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости Рыночная активность Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию Инвестиционная деятельность Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование Анализ инвестиций Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта Стоимость компании Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций Форвардные контракты Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту Теория вероятностей Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности Мат. статистика Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты Теория очередей (СМО) Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью) Аналитическая геометрия Векторная алгебра Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике Системы координат Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат Геометрия на плоскости Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными Линии 2-го порядка Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций Инварианты линий Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам Геометрия в пространстве Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве Поверхности 2-го порядка Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций Инварианты поверхностей Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам Линейная алгебра Матрицы и операции Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц Определители Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей Ранг матрицы Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк) Обратная матрица Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица Системы уравнений Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений Функциональные матрицы Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум Многочленные матрицы Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы Функции от матриц Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц Линейные пространства Линейные пространства: определение и примеры Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств Подпространства Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств Линейные отображения Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения Линейные операторы Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду Евклидовы пространства Евклидовы пространства Ортогональные векторы евклидова пространства Ортогональный базис евклидова пространства Ортонормированный базис евклидова пространства Ортогональные дополнения в евклидовом пространстве Задача о перпендикуляре Матрица и определитель Грама и его свойства Линейные преобразования евклидовых пространств Канонический вид ортогонального оператора евклидова пространства Сопряженные операторы евклидова пространства Самосопряженные операторы евклидова пространства Приведение квадратичной формы к главным осям Унитарные пространства и их линейные преобразования Комплексный анализ Комплексные числа Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел Комплексные функции Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения и их свойства Интегрирование функций комплексного переменного Функциональные ряды в комплексной области Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням Особые точки, Вычеты Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена Операционное исчисление Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства Дифференциальные уравнения ДУ первого порядка Основные понятия и определения ДУ Метод изоклин для ДУ 1-го порядка Метод последовательных приближений ДУ с разделяющимися переменными Однородные ДУ Линейные ДУ 1-го порядка Дифференциальное уравнение Бернулли ДУ в полных дифференциалах Интегрирующий множитель ДУ, не разрешенные относительно производной Дифференциальное уравнение Риккати Составление ДУ семейств линий Задачи на траектории Особые решения ДУ ДУ высших порядков Понятия и определения ДУ высших порядков ДУ, допускающие понижение порядка Линейная независимость функций Определители Вронского и Грама Однородные и неоднородные дифференциальные уравнения Задача Коши и Уравнение Эйлера Линейные ДУ с переменными коэффициентами Метод Лагранжа решения ДУ Краевые задачи для ДУ высших порядков Разложение решения ДУ в степенной ряд Разложение решения ДУ в обобщенный степенной ряд Нахождение периодических решений ДУ Асимптотическое интегрирование ДУ Системы ДУ Системы ДУ: понятия и определения Сведение системы ДУ к одному уравнению Нахождение интегрируемых комбинаций Интегрирование однородных линейных систем ДУ Методы интегрирования неоднородных систем ДУ Преобразование Лапласа и решение ДУ и систем Теория устойчивости Устойчивость решений ДУ по Ляпунову Простейшие типы точек покоя Метод функций Ляпунова Устойчивость решений ДУ по первому приближению Критерии устойчивости Рауса–Гурвица и Михайлова ДУ с малым параметром при производной Численные методы Методы алгебры Численные методы линейной алгебры Численные методы решения СЛАУ Итерационный метод Шульца обратной матрицы Методы решения задач о собственных значениях и векторах матрицы Методы решения нелинейных уравнений Методы решения систем нелинейных уравнений Методы теории приближений Методы приближения сеточных функций Методы функциональной интерполяции Методы интегрально-дифференциальной интерполяции Методы интегрального сглаживания Методы интерполяции и сглаживания сплайнами Методы численного дифференцирования и интегрирования Методы численного дифференцирования Методы численного интегрирования Методы решения обыкновенных ДУ Численные методы решения задачи Коши Разностные схемы для решения задачи Коши Составные схемы для решения задачи Коши Экстраполяционные методы решения задачи Коши Непрерывно-дискретные методы решения задачи Коши Численные методы решения краевых задач	Рекурсивные функции Содержание 1. Происхождение рекурсивных функций 2. Основные понятия теории рекурсивных функций и тезис Чёрча 3. Примитивно рекурсивные функции 4. Примитивная рекурсивность предикатов 5. Вычислимость по Тьюрингу примитивно рекурсивных функций 6. Функции Аккермана 7. Оператор минимизации 8. Общерекурсивные и частично рекурсивные функции 9. Вычислимость по Тьюрингу частично рекурсивных функций 10. Частичная рекурсивность функций, вычислимых по Тьюрингу Понятие машины Тьюринга — не единственный известный путь уточнения понятия алгоритма. В настоящем и следующем параграфах будут рассмотрены еще два способа такого уточнения: рекурсивные функции и нормальные алгоритмы Маркова. Происхождение рекурсивных функций Всякий алгоритм однозначно сопоставляет допустимым начальным данным результат. Это означает, что с каждым алгоритмом однозначно связана функция, которую он вычисляет. В предыдущем параграфе были рассмотрены примеры функций, которые вычисляются с помощью алгоритма, названного машиной Тьюринга. Возникает естественный вопрос, для всякой ли функции существует вычисляющий ее алгоритм. Учитывая сформулированный ранее тезис Тьюринга, утверждающий, что функция вычислима с помощью какого-нибудь алгоритма тогда и только тогда, когда она вычислима с помощью машины Тьюринга, данный вопрос трансформируется в следующий. Для всякой ли функции можно указать вычисляющую ее машину Тьюринга? Если нет, то для каких функций существует вычисляющий их алгоритм (машина Тьюринга), как описать такие, как говорят, алгоритмически или эффективно вычислимые функции? Исследование этих вопросов привело к созданию в 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] ▼ Доказательство Руководствуясь определением 32.9 композиции машин Тьюринга, нетрудно понять, что если машина [math]F[/math] правильно вычисляет функцию [math]f(y)[/math], а машина [math]G[/math] правильно вычисляет функцию [math]g(x)[/math], то композиция этих машин [math]F\cdot G[/math] правильно вычисляет суперпозицию этих функций [math]f(g(x))\colon[/math] [math]\begin{array}{ll}&\qquad q_101^x\,;\\ G\colon&\qquad q01^{g(x)}\,;\\ F\colon&\qquad q01^{f(g(x))}\,. \end{array}[/math] Рассмотрим более сложную суперпозицию вычислимых функций: [math]\varphi(x,y)= f(g_1(x,y), g_2(x,y))[/math]. Пусть машины [math]F,\,G_1,\,G_2[/math] правильно вычисляют функции [math]f,\,g_1,\,g_2[/math] соответственно. Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию [math]\varphi(x,y)[/math], пользуясь введенными в предыдущей лекции машинами сдвига, транспозиции, копирования и нулевой функции: G_1\colon&\qquad 01^x01^yq01^{g_1(x,y)};\\[2pt] C\colon&\qquad 01^{g_1(x,y)}q01^x01^y\,;\\[2pt] G_2\colon&\qquad 01^{g_1(x,y)}q01^{g_2(x,y)};\\[2pt] B\colon&\qquad q01^{g_1(x,y)}01^{g_2(x,y)};\\[2pt] F\colon&\qquad q01^{f(g_1(x,y), g_2(x,y))};\\[2pt] q0\to q_00\colon&\qquad q_001^{f(g_1,g_2)}. \end{array}">[math]\begin{array}{ll} &\qquad q_101^x01^y\,;\\[2pt] K_2\colon&\qquad 01^x01^yq01^x01^y\,;\\[2pt] G_1\colon&\qquad 01^x01^yq01^{g_1(x,y)};\\[2pt] C\colon&\qquad 01^{g_1(x,y)}q01^x01^y\,;\\[2pt] G_2\colon&\qquad 01^{g_1(x,y)}q01^{g_2(x,y)};\\[2pt] B\colon&\qquad q01^{g_1(x,y)}01^{g_2(x,y)};\\[2pt] F\colon&\qquad q01^{f(g_1(x,y), g_2(x,y))};\\[2pt] q0\to q_00\colon&\qquad q_001^{f(g_1,g_2)}. \end{array}[/math] Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию [math]\varphi(x,y)= f \bigl(g_1(x,y),\, g_2(x,y),\, g_3(x,y)\bigr).[/math] Подстановки указанного вида достаточно специфичны (все функции [math]g[/math] имеют одно и то же число аргументов) и не исчерпывают всевозможных подстановок, которые можно производить над функциями. Но благодаря функциям-проекторам [math]I_m^n[/math] этот недостаток легко устраняется: любая суперпозиция функций в функции может быть выражена через суперпозиции указанного вида и функции-проекторы. В самом деле, например, суперпозиция [math]f(g_1(x_1,x_2), g_2(x_1))[/math] может быть в требуемом виде представлена так: [math]f\bigl(g_1(x_1,x_2),\, I_1^2(g_2(x_1), g_3(x_1))\bigr)[/math] — любая функция от [math]x_1[/math]. В свою очередь, используя подстановку и функции-проекторы, можно переставлять аргументы в функции: [math]\begin{gathered}f(x_2,x_1,x_3,\ldots,x_n)= f \bigl(I_2^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\\ f(x_1,x_1,x_3,\ldots,x_n)= f \bigl(I_1^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\end{gathered}[/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.7. Покажем, как, исходя из простейших функций, с помощью оператора примитивной рекурсии получить следующую функцию, называемую усеченной разностью: [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y= \begin{cases}x-y,&\text{if}\quad x \geqslant y,\\ 0,&\text{if}\quad x<y. \end{cases}[/math] Во-первых, отметим, что функция [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1[/math], получающаяся из функции [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y[/math] фиксированием второго аргумента, удовлетворяет следующим соотношениям: [math]\begin{aligned}& 0 \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=0=O(x);\\ & (x+1) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=x= I_1^2(x,y),\end{aligned}[/math] т.е. получена из простейших функций [math]O(x)[/math] и [math]I_1^2(x,y)[/math] с помощью оператора примитивной рекурсии. Во-вторых, нетрудно понять, исходя из определения усеченной разности, что эта функция удовлетворяет также равенствам: [math]\begin{aligned}& x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 0=x= I_1^2(x,y);\\ & x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; (y+1)= (x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1= h(x,y,x -.1 y)\end{aligned}[/math] для любых [math]x[/math] и [math]y[/math]. Тождества показывают, что двухместная функция [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y[/math] получена с помощью оператора примитивной рекурсии из простейшей функции [math]I_1^2(x,y)[/math] и функции [math]h(x,y,z)= z \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1[/math]. Пример 33.8. Покажем, что функция [math]s(x,y)=x+y[/math] может быть получена из простейших с помощью оператора примитивной рекурсии. Для функции верны следующие тождества: [math]\begin{aligned}& x+0=x;\\ & x+(y+1)= (x+y)+1, \end{aligned}[/math] которые можно записать в виде [math]\begin{aligned}s(x,0)=x;\\ s(x,y+1)= s(x,y)+1\end{aligned}[/math] или [math]\begin{aligned}s(x,0)= I_1^1(x);\\ s(x.y+1)= S(s(x,y)),\end{aligned}[/math], а это и есть схема примитивной рекурсии, основывающаяся на простейших функциях [math]I_1^1[/math] и [math]S[/math]. Пример 33.9. Аналогично операции сложения, очевидные соотношения для операции умножения [math]p(x,0)= x\cdot0=0= O(x),\quad p(x,x+1)= x\cdot y+x= p(x,y)+x= x+p(x,y)= s(x,p(x,y))[/math] говорят о том, что функция [math]p(x,y)=x\cdot y[/math] получена из простейшей функции [math]O(x,y)[/math] и функции [math]s(x,y)=x+y[/math] с помощью оператора примитивной рекурсии. Теорема 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], сама правильно вычислима на машине Тьюринга. ▼ Доказательство Для краткости записей будем считать, что функция [math]\varphi[/math] связана с функциями [math]f[/math] и [math]g[/math] следующим образом: [math]\varphi(x,0)= f(x),~ \varphi(x,i+1)= g(x,\varphi(x,i))[/math]. Обозначим [math]F[/math] и [math]G[/math] — машины Тьюринга, правильно вычисляющие функции [math]f[/math] и [math]g[/math] соответственно. Пусть [math]x,\,y[/math] — произвольные натуральные числа. Требуется сконструировать машину Тьюринга, вычисляющую значение [math]\varphi(x,y)[/math]. Как мы уже отмечали, для вычисления [math]\varphi(x,y)[/math] предстоит вычислить [math]y+1[/math] значений [math]\varphi(x,0), \varphi(x,1),\ldots,\varphi(x,y-1),\varphi(x,y)[/math]. Начальная конфигурация такова: [math]q_101^x01^y0[/math]. Применим к ней следующую последовательность машин Тьюринга: [math]B^{+}V \Gamma VB^{+}F[/math]. В результате получим последовательность конфигураций: [math]\begin{aligned}q_101^x01^y0\quad \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^xq01^y0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^yq01^x0 \\ \mathop{\Rightarrow}\limits^{\Gamma}&\quad 01^yq01^x01^x0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^xq01^y01^x0\\ \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^x01^yq01^x0\\ \mathop{\Rightarrow}\limits^{F}&\quad 01^x01^yq_{\alpha}01^{\varphi(x,0)}0. \end{aligned}[/math] На последнем шаге, применив машину, вычисляющую функцию [math]f(x)[/math], к конфигурации [math]q01^x[/math], мы получим значение [math]f(x)[/math], которое, согласно схеме примитивной рекурсии для [math]\varphi[/math], есть [math]\varphi(x,0)[/math]. (Промежуточным состояниям [math]q[/math] мы намеренно не приписывали никаких индексов. Индекс [math]\alpha[/math] получило лишь последнее в этой последовательности состояние.) Теперь мы можем приступить к вычислению [math]\varphi(x,1)[/math], используя второе соотношение схемы примитивной рекурсии: [math]\varphi(x,1)= g(x,\varphi(x,0))[/math]. Для этого применим сначала к последней конфигурации команды: [math]q_{\alpha}0\to q_{\alpha+1}0L,~ q_{\alpha+1}\to q_{\alpha+2}0[/math]. В результате получим конфигурацию: [math]01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0[/math]. Теперь нужно подготовить ленту машины к применению машины [math]G[/math], вычисляющей значение [math]g(x,\varphi(x,0))[/math], т.е. необходимо получить на ленте конфигурацию [math]q01^x01^{\varphi(x,0)}[/math]. Для этого применим к конфигурации [math]01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0[/math] последовательность машин [math]AB^{-}VB^{+}V\Gamma VB^{-} VB^{+}B^{+} VB^{-}[/math]. Получим последовательность конфигураций: [math]\begin{aligned}&01^x01^{y-1}q_{\alpha+2}001^{\varphi(x,0)}0 \quad \mathop{\Rightarrow}\limits^{A}\quad 01^x01^{y-1}q01^{\varphi(x,0)}00 \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^xq01^{y-1}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V} \\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{\Gamma}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{\Gamma}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}q01^{y-1}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{x}01^{y-1}q01^{x}01^{\varphi(x,0)}. \end{aligned}[/math] Теперь мы можем применить машину [math]G[/math] и вычислить значение [math]\varphi(x,1)= g\bigl(x,\varphi(x,0)\bigr)\,\colon 01^x01^{y-1} q_{\beta}01^{\varphi(x,0)}.[/math] Применим к этой конфигурации команду: [math]q_{\beta}0\to q_{\alpha}0[/math], зацикливающую программу. Получим конфигурацию: [math]01^x01^{y-1}q_{\alpha}01^{\varphi(x,1)}[/math]. Начинается следующий цикл, осуществляемый командами идущими после первого появления состояния [math]q_{\alpha}[/math]. Этот цикл пре' образует конфигурацию вида [math]01^x01^{y-i}q_{\alpha}01^{\varphi(x,1)}[/math] в конфигурации [math]01^x01^{y-(i+1)}q_{\beta}01^{\varphi(x,i+1)}[/math] при условии, что [math]y>i[/math]. Команда [math]q_{\beta}0\to q_{\alpha}0[/math] зацикливает программу, и в результате работы цикла параметр [math]y-i[/math] будет понижаться до тех пор, пока не получится конфигурация [math]01^x0 q_{\alpha}01^{\varphi(x,y)}[/math], которая в силу команды [math]q_{\alpha}0\to q_{\alpha+1}0L[/math] перейдете конфигурацию [math]01^xq_{\alpha+1}001^{\varphi(x,y)}[/math]. Дополнительные команды [math]q_{\alpha+1}0\to q_{\beta+1}0,\, A,\,V,\,O,\,V,\,B^{-},\,A[/math] создают на ленте требуемую конфигурацию [math]q_001^{\varphi(x,y)}[/math], доказывающую, что функция [math]\varphi(x,y)[/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. Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей. ▼ Доказательство Начнем с построения такой последовательности. Мы знаем, что произведение растет быстрее суммы, а степень — быстрее произведения. Начнем построение последовательности именно с этих функций, введя для них единообразные обозначения: [math]P_0(a,y)= a+y;\qquad P_1(a,y)=a\cdot y;\qquad P_2(a,y)=a^y.[/math] Эти функции связаны между собой следующими рекурсивными соотношениями: [math]\begin{aligned}P_1(a,y+1)&= a+ay= P_0(a, P_1(a,y)),\quad P_1(a,1)=a;\\ P_2(a,y+1)&= a\cdot a^y= P_1(a, P_2(a,y)),\quad P_2(a,1)=a. \end{aligned}[/math] Продолжим эту последовательность, положив по определению для [math]n=2,3,\ldots\colon[/math] [math]\left.{\begin{aligned}&P_{n+1}(a,0)=1,\\ &P_{n+1}(a,1)=a,\\ &P_{n+1}(a,y+1)= P_n(a,P_{n+1}(a,y)).\end{aligned}}\right\}[/math] (1) (Первое из равенств (1) предназначено для того, чтобы функции [math]P_n(a,y)[/math] были всюду определены.) Эта схема имеет вид примитивной рекурсии, и, следовательно, все функции [math]P_n(a,y)[/math] примитивно рекурсивны. Растут они крайне быстро. Например, [math]P_3(a,1)=a,~ P_3(a,2)= P_2(a,a)=a^a,~\ldots[/math]. Значение [math]P_3(a,k+1)[/math] получается в результате возведения числа [math]a[/math] в степень [math]a[/math] k-раз. Зафиксируем теперь значение [math]a=2[/math]. Получим последовательность функций от одного аргумента: [math]P_0(2,y),\, P_1(2,y),\,\ldots[/math]. Введен, две новые функции: [math]B(x,y)= P_x(2,y)[/math] (она перечисляет последнюю последовательность) и [math]A(x)= B(x,x)[/math]. Первая из них называется функцией Аккермана, а вторая — диагональной функцией Аккермана. Для функции [math]B(x,y)[/math] на основании введенных выше обозначений и соотношений (1) вытекают следующие равенства: [math]\left.{\begin{aligned}& B(0,y)=2+y,\\ & B(x+1,0)= \operatorname{sg}(x),\\ & B(x+1,y+1)=B(x,B(x+1,y)), \end{aligned}}\right\}[/math] (2) которые позволяют вычислять значение функции [math]B(x,y)[/math], а следовательно, и значения функции [math]A(x)[/math]. При этом в процессе вычисления значения функции [math]B(x,y)[/math] в некоторой точке используются вычисленные ранее ее значения в неких предыдущих точках. Этим схема (2) похожа на схему примитивной рекурсии. Но примитивная рекурсия ведется по одному аргументу, а в схеме (2) рекурсия ведется сразу по двум аргументам (такая рекурсия называется двойной, двухкратной, или рекурсией второй ступени). При этом существенно усложняется характер упорядочения точек, а следовательно, и понятие предшествующей точки. Это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где число [math]n[/math] всегда предшествует числу [math]n+1[/math], а выясняется в ходе вычислений и для каждой схемы (2), вообще говоря, различно. Например, [math]B(3,3)= B(2,B(3,2))[/math], а так как [math]B(3,2)= P_3(2,2)= P_2(2,P_3(2,1))= P_2(2,2)=2^2=4,[/math] то вычислению [math]B[/math] в точке [math](3,3)[/math] по схеме (2) должно предшествовать вычисление [math]B[/math] в точке (2, 4): [math]B(3,3)= B(2,4)= P_2(2,4)=24=16[/math]. Проверьте самостоятельно, что вычислению [math]B[/math] в точке [math](3 4)[/math] должно предшествовать вычисление в точке [math](2,16)[/math]. Итак, функция [math]B(x,y)[/math], а вместе с ней и функция [math]A(x)[/math] вычислимы (по схеме (2)), а значит, в силу гипотезы Тьюринга, вычислимы посредством подходящей машины Тьюринга. Возникает вопрос, можно ли их вычисление свести к вычислению по схеме примитивной рекурсии, т. е. будут ли эти функции примитивно рекурсивными. Именно такова ситуация с функцией Аккермана [math]A(x)[/math]. Идея доказательства того, что функция [math]A(x)[/math] не является примитивно рекурсивной, состоит в доказательстве того, что функция [math]A(x)[/math] растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не может быть примитивно рекурсивной. Более точно, для любой примитивно рекурсивной функции [math]f(x)[/math] от одного аргумента найдется такое [math]n[/math], что для любого [math]x\geqslant n[/math] будет [math]A(x)>f(x)[/math]. (Это доказал Аккерман в 1928 г.) Идея доказательства этого утверждения состоит в следующем. Сначала доказываются два свойства функции [math]B(x,y)[/math], которые используются в дальнейшем: [math]\begin{aligned}& B(x,y+1)> B(x,y)\quad (x,y=1,2,\ldots);\\ & B(x+1,y)\geqslant B(x,y+1)\quad (x \geqslant 1,~ y \geqslant 2). \end{aligned}[/math] Затем вводится понятие B-мажорируемой функции. Функция [math]f(x_1,\ldots,x_n)[/math] называется B-мажорируемой, если [math](\exists m\in \mathbb{N})(\forall x_1,\ldots,x_n) \bigl[\max(x_1,\ldots,x_n)>1\to f(x_1,\ldots,x_n)< B(m,\max(x_1,\ldots,x_n))\bigr].[/math] Доказывается, что все примитивно рекурсивные функции B-мажорируемы. (Сначала устанавливается B-мажорируемость простейших функций [math]O,\,S(x),\,I_m^n(x)[/math]. Затем доказывается, что оператор суперпозиции, примененный к B-мажорируемым функциям, дает B-мажорируемую функцию. Аналогичным свойством обладает и оператор примитивной рекурсии.) Наконец, рассмотрим произвольную примитивно рекурсивную функцию [math]f(x)[/math]. В силу предыдущего утверждения, для некоторого [math]m[/math] и любого [math]x\geqslant 2[/math] имеем [math]f(x)<B(m,x)[/math]. Но тогда [math]A(m+x)= B(m+x,m+x)> B(m,m+x)> f(m+x)[/math]. (Предпоследнее неравенство получено исходя из двух свойств функции [math]B(x,y)[/math], сформулированных вначале.) Это и означает, что [math]A(x)>f(x)[/math], начиная по меньшей мере с [math]x=m+2[/math]. Итак, функция Аккермана [math]A(x)[/math] не может быть вычислена по схеме примитивной рекурсии, но может быть вычислена по более сложной схеме (2). Следовательно, примитивно рекурсивные функции не исчерпывают класса всех вычислимых функций, а свойство функции быть примитивно рекурсивной не равносильно ее свойству быть вычислимой (в том числе по Тьюрингу). Это говорит о том, что если мы не оставляем затеи породить из простейших функций все вычислимые функции, то мы должны ввести какие-то дополнительные средства (методы) порождения. Таким средством явится оператор минимизации. Оператор минимизации Это — оператор наименьшего числа в определении 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.17. Рассмотрим следующую функцию, получающуюся с помощью оператора минимизации: [math]d(x,y)= \mu z[y+z=x]= \mu z \bigl[s(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].[/math] Вычислим, например, [math]d(7,2)[/math]. Для этого нужно положить [math]y=2[/math] и, придавая переменной [math]z[/math] последовательно значения [math]0,1,2,\ldots[/math], каждый раз вычислять сумму [math]y+z[/math]. Как только она станет равной 7, то соответствующее значение [math]z[/math] принять за значение [math]d(7,2)[/math]. Вычисляем: [math]\begin{aligned}&z = 0,~~2+0 = 2 \ne 7 ;\\ &z= 1,~~ 2+ 1 = 3 \ne 7 ;\\ &z=2,~~ 2+2 = 4 \ne 7 ;\\ &z = 3,~~ 2 + 3 = 5\ne 7;\\ &z= 4,~~ 2 + 4 = 6 \ne 7 ;\\ &z = 5,~~ 2 + 5 = 7.\end{aligned}[/math] Таким образом, [math]d(7,2)=5[/math]. Попытаемся вычислить по этому правилу [math]d(3,4)\colon[/math] [math]\begin{aligned}&z = 0,~~ 4 + 0 = 4 > 3 ;\\&z= 1,~~ 4+ 1 = 5 > 3;\\&z = 2,~~ 4 + 2 = 6 > 3 ;\\&\ldots \ldots\ldots\ldots\ldots \end{aligned}[/math] Видим, что данный процесс будет продолжаться бесконечно. Следовательно, [math]d(3,4)[/math] не определено. Пример 33.18. Аналогично, с помощью оператора минимизации можно получить частичную функцию, выражающую частное от деления двух натуральных чисел: [math]x\!\!\not{\phantom{\|}}\,y= q(x,y)= \mu z[y\cdot z=x]= \mu z \bigl[p(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].[/math] Заметим, что обе функции из двух последних примеров не всюду определены, т. е. являются частичными. С помощью µ-оператора можно построить некоторые всюду определенные аналоги рассмотренных функций: [math]\begin{aligned}&[x-y]= \mu z[y+z \geqslant x]= \mu z[y+z+1>x];\\ &[x\!\!\not{\phantom{\|}}\,y]= \mu z[y(z+1)>x].\end{aligned}[/math] Первая из этих функций равна 0, если [math]x<y[/math], и равна [math]x-y[/math], если [math]x\geqslant y[/math]. Вторая представляет собой целую часть функций [math]x\!\!\not{\phantom{\|}}\,y[/math]. Заметим, что механизм проявления неопределенности функции в точке при вычислении ее значения с помощью µ-оператора такой же, как и при вычислении ее на машине Тьюринга: в случае неопределенности процесс вычисления не останавливается, а продолжается неограниченно долго. Общерекурсивные и частично рекурсивные функции Итак, функция называется частично рекурсивной (определение 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], также правильно вычислима на машине Тьюринга. ▼ Доказательство Обозначим [math]F[/math] — машину Тьюринга, правильно вычисляющую функцию [math]f(x,y)[/math]. Используя ее, сконструиру-ем такую машину Тьюринга, которая для заданного значения х вычисляет последовательно значения [math]f(x,0), f(x,1), f(x,2),\ldots[/math] до тех пор, пока в первый раз получится [math]f(x,i)=0[/math]. После этого машина Должна выдать на ленту число [math]i[/math], представляющее собой значение Функции [math]\varphi(x)=i[/math]. Если же для всех [math]i[/math] будет иметь место [math]f(x,i)>0[/math], то машина должна работать вечно, и это будет означать, что функция [math]\varphi[/math] не определена в точке [math]x[/math]. Начальная конфигурация на конструируемой машине такова: [math]q_101^x0[/math]. Будем мыслить ее следующим образом: [math]q_101^x01^0[/math] и начнем с применения к ней машины "копирование" [math]\mathsf{K}_2[/math]. Получим конфигурацию: [math]01^x01^0q01^x01^0[/math]. Теперь вычислим значение [math]f(x,0)[/math], применив машину [math]F\colon\, 01^x01^0q_{\alpha}01^{f(x,0)}[/math]. Далее подбираем команды, которые при условии [math]f(x,i)>0[/math] преобразовывают конфигурацию [math]01^x01^iq01^{f(x,i)}[/math] в конфигурацию [math]01^x01^{i+1}q01^{f(x,i+1)}\colon[/math] [math]\begin{array}{rl}q_{\alpha}0 \to q_{\alpha+1}0\Pi\colon &\qquad 01^x01^0q_{\alpha+1}1^{f(x,0)};\\ q_{\alpha+1}1 \to q_{\alpha+2}0\colon &\qquad 01^x01^0q_{\alpha+2}01^{f(x,0)-1};\\ q_{\alpha+2}0 \to q_{\alpha+3}0L\colon &\qquad 01^x01^0q_{\alpha+3}001^{f(x,0)-1};\\ q_{\alpha+3}0 \to q_{\alpha+4}1\colon &\qquad 01^x01^0q_{\alpha+4}101^{f(x,0)-1};\\ q_{\alpha+4}1 \to q_{\alpha+5}1\Pi\colon &\qquad 01^x01^1q_{\alpha+5}01^{f(x,0)-1};\\ O\colon &\qquad 01^x01^1q0;\\ B^{-}B^{-}\colon &\qquad q01^x01^1;\\ K_2\colon &\qquad 01^x01^1q01^x01^1;\\ F\colon &\qquad 01^x01^1q_{\beta}01^{f(x,1)};\\ q_{\beta}0\to q_{\alpha}0\colon &\qquad 01^x01^1q_{\alpha}01^{f(x,1)}.\end{array}[/math] Последняя команда зацикливает программу, и машина от конфигурации [math]01^x01^1q_{\alpha}01^{f(x,1)}[/math] переходит к конфигурации [math]01^x01^2q_{\alpha}01^{f(x,2)}[/math], затем к конфигурации [math]01^x01^3q_{\alpha}01^{f(x,3)}[/math] и т.д. Допустим, что по истечении некоторого времени машина достигла конфигурации [math]01^x01^iq_{\alpha}01^{f(x,i)}[/math], при которой [math]f(x,i)=0[/math]. Это означает, что [math]f(x,i)=0[/math] и машина должна выдать этот результат. Число [math]i[/math] накоплено в "счетчике" [math]01^i[/math]. Поэтому поступаем следующим образом. Уже имеющаяся команда [math]q_{\alpha}0\to q_{\alpha+1}0\Pi[/math] приведет машину к конфигурации [math]01^x01^i0q_{\alpha+1}0[/math]. Следующие команды выдают на ленту необходимую конфигурацию [math]q_001^i[/math], то есть [math]q_001^{\varphi(x)}\colon[/math] [math]\begin{array}{rl}q_{\alpha+1}0\to q_{\gamma}0\colon &\qquad 01^x01^iq_{\alpha}0;\\ B^{-}B^{-}\colon &\qquad 01^xq01^i;\\ BOB^{-}\colon &\qquad q_{\delta}01^i;\\ q_{\delta}0\to q_00\colon &\qquad q_001^{\varphi(x)}.\end{array}[/math] Теорема доказана. Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу. Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и операторы суперпозиции и примитивной рекурсии), простейшие функции [math]O,\,S,\,I_m^n[/math] вычислимы по Тьюрингу, а всякая частично рекурсивная функция получается из простейших с помощью применения конечного числа раз трех указанных операторов, то всякая частично рекурсивная функция вычислима по Тьюрингу. Частичная рекурсивность функций, вычислимых по Тьюрингу Наконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию [math]f(x_1,\ldots, x_n)[/math], можно построить рекурсивное описание этой функции. Эта теорема впервые была доказана Тьюрингом. Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна. ▼ Доказательство Прежде чем приступить к доказательству теоремы, обратим внимание на следующее обстоятельство. Машина Тьюринга, преобразовывающая слова в алфавите [math]A=\{a_0,a_1,\ldots, a_{m-1}\}[/math], никак не различает природу этого алфавита. В частности, она никак не отличает числа от "нечисел": работая с числами, машина не считает их в смысле известных арифметических правил, а преобразовывает слова, представляющие собой записи чисел на каком-то языке (в какой-то системе счисления). Правила преобразований задаем мы с помощью соответствующей программы, и мы же даем полученному машиной словесному результату числовую интерпретацию. Именно в этом смысле мы говорили о вычислимости машиной Тьюринга тех или иных числовых функций. Чтобы доказать сформулированную теорему, необходимо идею арифметической (числовой) интерпретации работы машины Тьюринга довести до определенного совершенства и показать, что любое преобразование, осуществляемое машиной Тьюринга, если его интерпретировать как вычисление, является частично рекурсивным. Разделим доказательство на этапы (их будет пять). Первый этап. Арифметизация машин Тьюринга начинается с того, что мы вводим в машину своего рода арифметическую систему координат. Эта система координат предназначена для конфигураций машины. Как известно, в каждый момент времени конфигурация на ленте машины Тьюринга имеет вид [math]\alpha q_ia_j \beta[/math], где [math]\alpha[/math] — слово в алфавите [math]A=\{a_0,a_1,\ldots, a_{m-1}\}[/math], записанное на ленте левее обозреваемой в данный момент ячейки; [math]q_i[/math] — состояние, в котором находится в данный момент машина; [math]a_j[/math] — содержимое обозреваемой в данный момент ячейки; [math]\beta[/math] — слово в алфавите [math]A[/math], записанное на ленте правее обозреваемой ячейки. Указанной конфигурации однозначно сопоставляется упорядоченная четверка [math](\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})[/math] чисел, определяемых следующим образом: [math]\widetilde{q}_i=i;~ \widetilde{a}_j=j;~ \widetilde{\alpha}[/math] — число, изображаемое цифрами, полученными кодированием символов слова [math]\alpha[/math] по следующему правилу: эти символы интерпретируются как m-ичные цифры, т.е. цифры m-ичной системы счисления, т.е. [math]a_i[/math] кодируется цифрой [math]i[/math]; [math]\widetilde{\beta}[/math] аналогично получается из [math]\beta[/math], но при этом читается справа налево, т.е. крайняя слева ячейка [math]\beta[/math] содержит самый младший разряд, а крайняя справа — самый старший (это сделано для того, чтобы нули справа от [math]\beta[/math] не влияли на значение [math]\widetilde{\beta}[/math]). Завершим кодирование элементов машины Тьюринга. Символу [math]a_0[/math] пустой ячейки сопоставим число 0, сдвигу вправо [math]\Pi[/math] сопоставим 1, сдвигу влево [math]L[/math] — 2, отсутствию сдвига [math]C[/math] сопоставим 0, буквой [math]z[/math] закодируем заключительное состояние (состояние остановки) [math]q_0[/math]. В итоге алфавит [math]A[/math] закодируется числовым множеством [math]\widetilde{A}[/math], а алфавит [math]Q[/math] — числовым множеством [math]\widetilde{Q}[/math]. Тогда, например, если мы имеем машину Тьюринга с внешним алфавитом [math]A=\{a_0, a_1\}[/math] и на ее ленте имеется конфигурация [math]a_1a_0a_1a_1a_0q_3a_1a_1a_0a_1a_1[/math], то при нашей кодировке (или координатизации) ей соответствует следующая упорядоченная четверка натуральных чисел: [math](22, 3, 1, 13)[/math]. Поясним, как она получилась. В нашей конфигурации [math]\alpha=a_1a_0a_1a_1a_0,[/math] [math]q_i=q_3,~ a_j=a_1,[/math] [math]\beta= a_1a_0a_1a_1[/math]. Поэтому [math]\widetilde{\alpha}=10110[/math] — двоичное число, которое следующим образом переводится в десятичное: [math][10110]_2=1\cdot 2^4+0\cdot 2^3+ 1\cdot 2^2+1\cdot 2^1+ 0\cdot 2^0=22[/math] Далее, [math]\widetilde{q}_3=3,~ \widetilde{a}_1=1[/math] и, наконец, [math]\widetilde{\beta}= [1101]_2=13[/math]. Второй этап. При таком кодировании система команд машины Тьюринга с алфавитом [math]A[/math] и множеством состояний [math]Q[/math] превращается в тройку числовых функций: [math]\varphi_a\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{A}[/math] (функция печатаемого символа); [math]\varphi_q\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{Q}[/math] (функция следующего состояния); [math]\varphi_d\colon~ \widetilde{Q}\times \widetilde{A}\to \{0,1,2\}[/math] (функция сдвига). Например, если среди команд машины Тьюринга имеется команда [math]q_ia_j\to q'_ia'_jX[/math], то [math]\varphi_a(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{a}'_j,\qquad \varphi_q(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{q}'_i,\qquad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)= \xi,[/math] где [math]\xi=0,\,1,\,2[/math], если [math]X=C,\,\Pi,\,L[/math] соответственно. Отметим, что все эти функции [math]\varphi_a,\,\varphi_q,\,\varphi_d[/math] заданы на конечном множестве [math]\widetilde{Q}\times \widetilde{A}[/math] и потому примитивно рекурсивны. Третий этап. Выполнив одну команду, машина Тьюринга преобразует имеющуюся на ленте конфигурацию [math]K=\alpha q_ia_j \beta[/math] в новую конфигурацию [math]K'=\alpha' q'_ia'_j \beta'[/math]. При арифметизации это означает, что упорядоченной четверке чисел [math](\widetilde{\alpha},\widetilde{q}_i,\widetilde{a}_j, \widetilde{\beta})[/math], соответствующей конфигурации [math]K[/math], однозначно сопоставляется упорядоченная четверка чисел [math](\widetilde{\alpha}',\widetilde{q}'_i,\widetilde{a}'_j, \widetilde{\beta}')[/math], соответствующая конфигурации [math]K'[/math]. Например, при команде [math]q_3a_1\to q_4a_0[/math] ранее приведенная конфигурация перейдет в конфигурацию [math]K'= a_1a_0a_1a_1a_0a_0 q_4a_1a_0a_1a_1[/math], которой соответствует четверка чисел [math](44,4,1,6)[/math]. Так будет происходить почти со всеми конфигурациями, связанными с алфавитами [math]A,\,Q[/math]. В итоге на множестве таких конфигураций будет задана (вообще говоря, не всюду определенная, т.е. частичная) нечисловая функция [math]\psi_{\Theta}(K)=K'[/math], обусловленная данной машиной Тьюринга [math]\Theta[/math]. Назовем ее функцией следующего шага. При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага. Иначе говоря, [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] — это числовые функции, каждая из которых зависит от четырех числовых переменных [math]\widetilde{\alpha}, \widetilde{q}, \widetilde{a}, \widetilde{\beta}[/math]. Попытаемся понять, как эти функции связаны с функциями системы команд [math]\varphi_a, \varphi_q, \varphi_a[/math]. Во-первых, ясно, что [math]\widetilde{q}'_i= \varphi_q[/math] и функция [math]\widetilde{q}'[/math] фактически не зависит от [math]\widetilde{\alpha},\, \widetilde{\beta}[/math], а зависит лишь от [math]\widetilde{q},\, \widetilde{a}[/math], то есть [math]\widetilde{q}'(\widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= \varphi_q(\widetilde{q}_i, \widetilde{a}_j)[/math]. Рассмотрим теперь функцию [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})[/math]. Если при рассматриваемом такте работы машины ее головка осталась на месте, т.е. обозреваемая ячейка не изменилась, т.е. [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0[/math], то ясно, что [math]\widetilde{\alpha}'= \widetilde{\alpha}[/math]. Если головка сдвинулась вправо, т.е. [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1[/math], то это означает, что степень каждого разряда числа [math]\widetilde{\alpha}[/math] повысилась на единицу: нулевой разряд стал первым, первый — вторым и т.д., т.е. число [math]\widetilde{\alpha}[/math] увеличилось в [math]m[/math] раз (напомним, что [math]m[/math] — число элементов в алфавите [math]A[/math], т.е. основание системы счисления, в которой рассматривается наша арифметизация): [math]m\widetilde{\alpha}[/math]. Кроме того, в образовавшийся младший (нулевой) разряд помещается та m-ичная цифра, которая соответствует при кодировании только что вписанному на ленту элементу из [math]A[/math]. Эта цифра равна [math]\varphi_a(\widetilde{q}_i, \widetilde{a}_j)[/math]. В итоге получим, что при сдвиге вправо: [math]\widetilde{\alpha}'( \widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= m \widetilde{\alpha}+ \varphi_a(\widetilde{q}_i, \widetilde{a}_j)[/math]. Наконец, при сдвиге на данном шаге головки влево, т.е. при [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2[/math], степень каждого разряда числа [math]\widetilde{\alpha}[/math] понизилась на единицу: первый разряд стал нулевым, второй — первым и т.д., т.е. число [math]\widetilde{\alpha}[/math] уменьшилось в [math]m[/math] раз: [math]\widetilde{\alpha}\!\!\not{\phantom{\|}}\,m[/math]. Но поскольку самый младший (нулевой) разряд оказался фактически как бы "отрубленным", то в итоге получилось не частное [math]\widetilde{\alpha}\!\!\not{\phantom{\|}}\,m[/math] (оно могло бы оказаться дробным), а его целая часть: [math][\widetilde{\alpha}\!\!\not{\phantom{\|}}\,m][/math]. Итак, для функции [math]\widetilde{\alpha}'[/math] мы получаем следующее описание с помощью оператора условного перехода: [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})= \begin{cases}\widetilde{\alpha},& \text{elsi}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0\quad \text{(net sdviga)},\\[2pt] m\widetilde{\alpha}+\varphi_a(\widetilde{q}_i, \widetilde{a}_j),& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1\quad \text{(sdvig vpravo)},\\[2pt] \widetilde{\alpha}\!\!\not{\phantom{\|}}\,m,& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2\quad \text{(sdvig vlevo)}.\end{cases}[/math] Совершенно аналогичная, но в определенном смысле двойственная картина наблюдается и для функции [math]\widetilde{\beta}\colon[/math] при сдвиге вправо (влево) она ведет себя так же, как функция [math]\widetilde{\alpha}[/math] при сдвиге влево (вправо). Так что для нее получаем следующее описание с помощью оператора условного перехода: [math]\widetilde{\beta}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases}\widetilde{\beta},& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ \widetilde{\beta}\!\!\not{\phantom{\|}}\,m,& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ m\widetilde{\beta}+ \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}[/math] Наконец, рассмотрим функцию [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})[/math]. Если сдвига не происходит, то ясно, что [math]\widetilde{\alpha}'= \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j})[/math]. Если происходит сдвиг вправо, то машина приходит к обозрению самого левого разряда (напомним, что это есть младший разряд) — числа [math]\widetilde{\beta}\colon[/math] именно он был отброшен при взятии для [math]\widetilde{\beta}'[/math] целой части частного [math]\widetilde{\beta} \!\!\not{\phantom{\|}}\, m[/math]. Он как раз и представляет собой остаток от деления числа [math]\widetilde{\beta}[/math] на [math]m[/math], т.е. в этом случае [math]\widetilde{\alpha}'= r(m,\widetilde{\beta})[/math]. Если же происходит сдвиг влево, то двойственно получаем: [math]\widetilde{\alpha}'= r(m, \widetilde{\alpha})[/math]. Итак, функция [math]\widetilde{\alpha}'[/math] получает следующее описание: [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases} \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ r(m,\widetilde{\beta}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ r(m, \widetilde{\alpha}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}[/math] Теперь сделаем выводы. В полученных выражениях для функций [math]\widetilde{q}', \widetilde{\alpha}', \widetilde{\beta}, \widetilde{a}'[/math], а задействованы только примитивно рекурсивные функции, и указанные функции получены из этих примитивно рекурсивных функций с помощью оператора условного перехода, который, как мы знаем, сохраняет свойство примитивной рекурсивности, т.е. из примитивно рекурсивных функций создает снова примитивно рекурсивную функцию. Следовательно, все функции [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] примитивно рекурсивны. Итак, мы доказали, что на каждом шаге любая машина Тьюринга осуществляет примитивно рекурсивное вычисление. Четвертый этап. Рассмотрим теперь с точки зрения введенной арифметизации работу машины Тьюринга в целом. Пусть задана начальная конфигурация [math]K(0)= (\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)[/math]. Тогда конфигурация [math]K(t)[/math], возникающая на такте [math]t[/math] работы машины, зависит от величины [math]t[/math] и компонент [math]\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math] начальной конфигурации, т.е. она является векторной функцией [math]K(t)= \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr)[/math], компоненты которой, в свою очередь, являются функциями, зависящими от переменных [math]t, \widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math]. Эти функции определяются следующим образом: [math]\begin{aligned}&K_{\alpha}(0,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)= \widetilde{\alpha}_{0};\\[2pt] &K_{\alpha}(t+1,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)=\\ &\qquad= \widetilde{\alpha} \bigl(K_{\alpha}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{q}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{a}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{\beta} (t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)\bigr);\\[2pt] &K_{q}(0)= \widetilde{q}_{0};\\[2pt] &K_{q}(t+1)= \widetilde{q}'\bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{a}(0)= \widetilde{a}_{0};\\[2pt] &K_{a}(t+1)= \widetilde{a}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{\beta}(0)= \widetilde{\beta}_{0};\\[2pt] &K_{\beta}(t+1)= \widetilde{\beta}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr). \end{aligned}[/math] (В записях для функций [math]K_{q},K_{a},K_{\beta}[/math] аргументы [math]\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math] для краткости опущены.) Эти соотношения представляют собой схемы примитивной рекурсии, определяющие функции [math]K_{\alpha},K_{q},K_{a},K_{\beta}[/math] с помощью функций [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math]. При этом рекурсия ведется по переменной t. Примитивная рекурсивность функций [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] установлена на предыдущем шаге доказательства. Тогда отсюда очевидно следует, что и функции. [math]K_{\alpha}, K_{q}, K_{a}, K_{\beta}[/math] также примитивно рекурсивны. Пятый этап. Наконец, на заключительном шаге доказательства покажем, что результат работы машины Тьюринга (т.е. вычисляемая машиной функция) носит рекурсивный характер. (Обратите внимание: не примитивно рекурсивный, а рекурсивный, т. е. здесь придется использовать оператор минимизации [math]\mu[/math].) Здесь мы докажем утверждение, обратное тому, которое было доказано в предыдущем пункте: всякая функция, правильно вычислимая на машине Тьюринга, частично рекурсивна. Пусть [math]\varphi[/math] — функция, правильно вычисляемая машиной Тьюринга. Такая машина, начав с конфигурации [math]q_1a_0 \beta_0[/math], останавливается в конфигурации вида [math]q_za_z \beta_z[/math], т.е. для такой машины [math]K_{a}(0)=0,~ K_{q}(0)=1[/math], исходное слово на ленте кодируется числом [math]m \widetilde{\beta}_0+\widetilde{\alpha}_0[/math], заключительное слово — числом [math]m \widetilde{\beta}_z+\widetilde{\alpha}_z[/math], т.е. вычисляется значение функции [math]\varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z[/math]. Заключительное слово — это слово, написанное на ленте в тот момент [math]t_z[/math], когда машина впервые перешла в заключительное состояние [math]q_z[/math], т.е. в момент [math]t_z= \mu t[K_{q}(t)=z][/math]. Поэтому [math]\widetilde{\beta}_z= K_{\beta}(t_z),~ \widetilde{\alpha}_z= K_{a}(t_z)[/math] и [math]\varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z= mK_{\beta}(t_z,0,1,\widetilde{\alpha}_0, \widetilde{\beta}_0)+ K_{a}(t_z,0,1, \widetilde{\alpha}_0, \widetilde{\beta}_0).[/math] Учитывая, что [math]\widetilde{\beta}_0= [x\!\!\not{\phantom{\|}}\,m],~ \widetilde{\alpha}_0= r(m,x)[/math], выражение для результирующего значения [math]\varphi(x)[/math] можно со всеми подробностями записать так: [math]\begin{aligned}\varphi(x)&= mK_{\beta} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{\|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{\|}}\,m]\bigr)+\\ &\quad+ K_{a} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{\|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{\|}}\,m]\bigr), \end{aligned}[/math] где [math]m,\,z[/math] — константы, зависящие от конкретной машины. Отсюда непосредственно видно, что функция [math]\varphi(x)[/math], представляющая собой результат работы машины Тьюринга, построена из примитивно рекурсивных функций с помощью оператора минимизации [math]\mu[/math] и, следовательно, является частично рекурсивной. Этим и завершается доказательство того, что всякая вычислимая по Тьюрингу функция частично рекурсивна. Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме. Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна. Итог рассмотрений настоящей лекции состоит в том, что мы дали некую альтернативную характеристику вычислимым по Тьюрингу функциям: это те и только те функции, которые частично рекурсивны. Другими словами, класс функций, вычислимых по Тьюрингу, совпадает с классом частично рекурсивных функций. Совпадение этих двух классов вычислимых функций, в основе построения которых лежали совершенно разные подходы к формализации понятия вычислимости функции, говорит о том, что эти подходы оказались весьма состоятельными, и служит косвенным подтверждением того, что как тезис Тьюринга, так и тезис Чёрча не только не безосновательны, но и имеют все права на признание.

Рекурсивные функции

Онлайн-сервисы

Нахождение НОД и НОК Разложение числа на простые множители Сравнения по модулю Операции над множествами Операции над векторами Разложение вектора по базису. Доказательство, что векторы образуют базис Чертёж треугольника по координатам вершин Решение треугольника Решение Пирамиды Построение Пирамиды по координатам вершин Чертёж многоугольника по координатам вершин Решение систем методом Крамера и Матричным Онлайн построение графика кривой 2-го порядка Определение вида кривой или поверхности 2-го порядка по инвариантам МНК и регрессионный анализ Онлайн + графики

Алгоритмы JavaScript

Алгоритмы поиска Алгоритмы сортировки Уникальные элементы массива Объединение, пересечение и разность массивов НОД и НОК Операции над матрицами

Введение в анализ

Функции: понятие, определение, графики Непрерывность функции Исследование функции и построение графика

Теория множеств

Множества: понятие, определение, примеры Точечные множества Замкнутые и открытые множества Мера множества Группы, кольца, поля в математике Поле комплексных чисел Кольцо многочленов Основная теорема алгебры и ее следствия

Математическая логика

Алгебра высказываний

Аксиоматика и логические рассуждения Методы доказательств теорем Алгебра высказываний и операции над ними Формулы алгебры высказываний Тавтологии алгебры высказываний Логическая равносильность формул Нормальные формы для формул высказываний Логическое следование формул Приложение алгебры высказываний для теорем Дедуктивные и индуктивные умозаключения Решение логических задач Принцип полной дизъюнкции

Булевы функции

Множества, отношения и функции в логике Булевы функции от одного и двух аргументов Булевы функции от n аргументов Системы булевых функций Применение булевых функций к релейно-контактным схемам Релейно-контактные схемы в ЭВМ Практическое применение булевых функций

Теория формального

Формализованное исчисление высказываний Полнота и другие свойства формализованного исчисления высказываний Независимость системы аксиом формализованного исчисления высказываний

Логика предикатов

Логика предикатов Логические операции над предикатами Кванторные операции над предикатами Формулы логики предикатов Тавтологии логики предикатов Преобразования формул и следование их предикатов Проблемы разрешения для общезначимости и выполнимости формул Применение логики предикатов в математике Строение математических теорем Аристотелева силлогистика и методы рассуждений Принцип полной дизъюнкции в предикатной форме Метод полной математической индукции Необходимые и достаточные условия Логика предикатов и алгебра множеств Формализованное исчисление предикатов

Неформальные и формаль-
ные аксиоматические теории

Неформальные аксиоматические теории Свойства аксиоматических теорий Формальные аксиоматические теории Формализация теории аристотелевых силлогизмов Свойства формализованного исчисления предикатов Формальные теории первого порядка Формализация математической теории

Теория алгоритмов

Интуитивное представление об алгоритмах Рекурсивные функции Нормальные алгоритмы Маркова Разрешимость и перечислимость множеств Неразрешимые алгоритмические проблемы Теорема Гёделя о неполноте формальной арифметики

Математическая логика и компьютеры

Математическая логика и языки программирования Применение компьютеров для доказательства теорем математической логики Математическая логика и логическое программирование Математическая логика и информатика Математическая логика и искусственный интеллект

Дискретная математика

Множества и отношения

Теория множеств: понятия и определения Операции над множествами Кортеж и декартово произведение множеств Соответствия и бинарные отношения на множествах Операции над соответствиями на множествах Семейства множеств Специальные свойства бинарных отношений Отношения эквивалентности на множестве Упорядоченные множества Теорема о неподвижной точке Мощность множества Парадокс Рассела Метод характеристических функций

Группы и кольца

Алгебраические структуры и операции Группоиды, полугруппы, группы Кольца, тела, поля Области целостности в теории колец Модули и линейные пространства Подгруппы и подкольца Теорема Лагранжа о порядке конечной группы Гомоморфизмы групп и нормальные делители Гомоморфизмы и изоморфизмы колец Алгебра кватернионов

Полукольца и булевы алгебры

Полукольца: определение, аксиомы, примеры Замкнутые полукольца Полукольца и системы линейных уравнений Булевы алгебры и полукольца Решетки и полурешетки

Алгебраические системы

Алгебраические системы: модели и алгебры Подсистемы алгебраических систем Конгруэнции и фактор-системы Гомоморфизмы алгебраических систем Прямые произведения алгебраических систем Конечные булевы алгебры Многосортные алгебры

Теория графов

Теория графов: основные понятия и определения Способы представления графов Неориентированные и ориентированные деревья Остовное дерево и алгоритм Краскала Методы систематического обхода вершин графа Алгоритмы поиска в глубину и ширину в графах Задача о путях во взвешенных ориентированных графах Изоморфизм, гомоморфизм и автоморфизм графов Топологическая сортировка вершин графа Элементы цикломатики в теории графов

Булева алгебра и функции

Булевы функции и булев куб Таблицы булевых функций и булев оператор Равенство булевых функций. Фиктивные переменные Формулы и суперпозиции булевых функций Дизъюнктивные и конъюнктивные нормальные формы Построение минимальных ДНФ Теорема Поста и классы Критерий Поста Схемы из функциональных элементов

Конечные автоматы и регулярные языки

Конечные автоматы и регулярные языки Алфавит, слово, язык в программировании Порождающие грамматики (грамматики Хомского) Классификация грамматик и языков Регулярные языки и регулярные выражения Конечные автоматы Допустимость языка конечным автоматом Теорема Клини Детерминизация конечных автоматов Минимизация конечных автоматов Лемма о разрастании для регулярных языков Обоснование алгоритма детерминизации автоматов Конечные автоматы с выходом Морфизмы и конечные подстановки Машины Тьюринга

Контекстно-свободные языки

Контекстно-свободные языки и грамматики Приведенная форма КС-грамматики Лемма о разрастании для КС-языков Магазинные автоматы (автомат с магазинной памятью) Алгоритм построения МП-автомата по КС-грамматике Алгоритм построения КС-грамматики по МП-автомату Алгебраические свойства КС-языков Основное свойство суперпозиции КС-языков Пересечение контекстно-свободных языков Методы синтаксического анализа КС-языков Восходящий синтаксический анализ и LR(k)-грамматики Семантика формальных языков Принцип индукции по неподвижной точке Графовое представление МП-автоматов

Интегральное исчисление

Неопределённый и определённый

Неопределенный и определенный интегралы Свойства интегралов Интегрирование по частям Интегрирование методом замены переменной Интегрирование различных рациональных функций Интегрирование различных иррациональных функций Интегрирование различных тригонометрических функций Определенный интеграл и его основные свойства Необходимое и достаточное условие интегрируемости Теоремы существования первообразной Свойства определенных интегралов Несобственные интегралы Интегральное определение логарифмической функции

Приложения интегралов

Вычисление площадей плоских фигур Площади фигур в различных координатах Вычисление объемов тел с помощью интегралов Объём тела вращения Вычисление длин дуг кривых Формулы длины дуги регулярной кривой Кривизна плоской кривой Площадь поверхности вращения тела

Интегралы в физике

Статические моменты и координаты центра тяжести Теоремы Гульдина–Паппа Вычисление моментов инерции Другие приложения интегралов в физике

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

Интеграл Ньютона-Лейбница Интеграл Римана Интеграл Лебега

Вариационное исчисление

Примеры вариационных задач Дифференциальное уравнение Эйлера Функционалы, зависящие от нескольких функций Задача о минимуме кратного интеграла

Финансовый анализ

Анализ эффективности

Критерии и показатели эффективности предприятия Методы анализа эффективности деятельности Факторный анализ прибыли от операционной деятельности Анализ безубыточности предприятия Операционный рычаг и эффект финансового рычага Анализ и оценка состава, структуры и динамики доходов и расходов Анализ рентабельности и резервов устойчивого роста капитала Анализ распределения прибыли предприятия Анализ и оценка чувствительности показателей эффективности

Анализ устойчивости

Финансовая устойчивость и долгосрочная платежеспособность Характеристика типов финансовой устойчивости

Рыночная активность

Финансовый анализ рыночной активности Методика анализа рыночной активности Анализ и оценка дивидендного дохода на одну акцию

Инвестиционная деятельность

Инвестиции: экономическая сущность и классификация Государственное регулирование инвестиционной деятельности Источники финансовых ресурсов на капитальные вложения Инвестиции в основные фонды Оценка состояния основных фондов Амортизация основных фондов Капитальное строительство в инвестиционном процессе Планирование инвестиций в форме капитальных вложений Экономическая эффективность инвестиций Финансирование капитальных вложений Кредитование капитальных вложений Кредитоспособность Финансирование и кредитование затрат Финансирование и кредитование инвестиционной деятельности потребительской кооперации Финансирование и кредитование капитальных вложений потребительской кооперации Инвестиционное строительное проектирование

Анализ инвестиций

Инвестиции и инвестиционная деятельность предприятия Задачи финансового анализа инвестиций предприятия Учет фактора времени в инвестиционной деятельности Аннуитет и финансовая рента в инвестициях Учет фактора инфляции при инвестировании Оценка фактора риска инвестиционного проекта Методы оценки эффективности инвестиций Показатели эффективности инвестиционного проекта

Стоимость компании

Концепция построения международных стандартов финансовой отчетности (МСФО) Экономическое содержание международных стандартов финансовой отчётности Цели и принципы оценки стоимости акций и активов компании Оценка акций и активов предприятия по справедливой стоимости Методы оценки справедливой стоимости акций предприятия Затратный подход к оценки стоимости компаний и акций Сравнительный подход к оценки стоимости предприятий и акций Доходный подход к оценке стоимости компании и акций Выбор ставки дисконтирования при инвестировании в акции Метод капитализации прибыли Сравнение подходов к оценке стоимости компаний и пакетов акций

Форвардные контракты

Форвардный контракт и цена Форвардная цена акции на бирже Цена форвардного контракта инвестора Форвардная цена акции с учетом величины дивиденда Форвардная цена акции с учетом ставки дивиденда Форвардная цена валюты на рынке форекс Форвардный валютный курс и инфляция на рынке Форвардная цена товара и спотовый рынок Форвардная цена при различии ставок по кредитам и депозитам Синтетический форвардный контракт на акции и валюту

Теория вероятностей

Основные понятия теории вероятностей Зависимые и независимые случайные события Повторные независимые испытания Формула Бернулли Одномерные случайные величины Многомерные случайные величины Функции случайных величин Законы распределения целочисленных случайных величин Законы распределения непрерывных случайных величин Предельные теоремы теории вероятностей Закон больших чисел и предельные теоремы Вероятностные закономерности

Мат. статистика

Элементы математической статистики Выборочный метод Оценки параметров генеральной совокупности Статистические гипотезы Критерии согласия Теоретические и эмпирические частоты

Теория очередей (СМО)

Определение системы массового обслуживания Уравнения Колмогорова Предельные вероятности состояний Определение СМО с отказами Определение СМО с ожиданием (очередью)

Аналитическая геометрия

Векторная алгебра

Метрические понятия и аксиомы геометрии Равенство и подобие геометрических фигур Бинарные отношения Вектор, его направление и длина Линейные операции над векторами Линейная зависимость и независимость векторов Отношение коллинеарных векторов Проекции векторов на прямую и на плоскость Угол между векторами Ортогональные проекции векторов Координата вектора на прямой и базис Координаты вектора на плоскости и базис Координаты вектора в пространстве и базис Операции над векторами в координатной форме Ортогональный и ортонормированный базисы Cкалярное произведение векторов и его свойства Выражение скалярного произведения через координаты векторов Векторное произведение векторов и его свойства Смешанное произведение векторов и его свойства Ориентированные площади и объемы Двойное векторное произведение и его свойства Применение векторов в задачах на аффинные свойства фигур Применение произведений векторов при решении геометрических задач Применение векторной алгебры в механике

Системы координат

Прямоугольные координаты Преобразования прямоугольных координат Полярная система координат Цилиндрическая система координат Сферические координаты Аффинные координаты Аффинные преобразования координат Аффинные преобразования плоскости Примеры аффинных преобразований плоскости Аффинные преобразования пространства Многомерное координатное пространство Линейные и аффинные подпространства Скалярное произведение n-мерных векторов Преобразования систем координат

Геометрия на плоскости

Алгебраические линии на плоскости Общие уравнения геометрических мест точек Алгебраические уравнения линий на плоскости Уравнения прямой, проходящей через точку перпендикулярно вектору Уравнения прямой, проходящей через точку коллинеарно вектору Уравнения прямой, проходящей через две точки Уравнения прямой с угловым коэффициентом Взаимное расположение прямых Примеры задач с прямыми на плоскости Системы неравенств с двумя неизвестными Системы линейных уравнений с двумя неизвестными

Линии 2-го порядка

Канонические уравнения линий второго порядка Порядок приведения уравнения линии к каноническому виду Эллипс Гипербола Парабола Квадратичные неравенства с двумя неизвестными Применение линий 1-го и 2-го порядков в задачах на экстремум функций

Инварианты линий

Классификация линий 2-го порядка по инвариантам Приведение уравнения линии к каноническому виду по инвариантам

Геометрия в пространстве

Способы задания ГМТ в пространстве Алгебраические уравнения поверхностей Уравнения плоскости, проходящей через точку перпендикулярно вектору Уравнения плоскости, компланарной двум неколлинеарным векторам Уравнения плоскости, проходящей через три точки Взаимное расположение плоскостей Типовые задачи с плоскостями Уравнения прямых в пространстве Взаимное расположение прямых в пространстве Типовые задачи с прямыми в пространстве

Поверхности 2-го порядка

Канонические уравнения поверхностей Порядок приведения уравнения поверхности к каноническому виду Поверхности второго порядка Эллипсоиды Гиперболоиды Конусы Параболоиды Применение поверхностей 1-го и 2-го порядков в задачах на экстремум функций

Инварианты поверхностей

Классификация поверхностей 2-го порядка по инвариантам Квадратичные неравенства с тремя неизвестными Приведение уравнения поверхности к канониче-скому виду по инвариантам

Линейная алгебра

Матрицы и операции

Линейные операции над матрицами Умножение матриц Возведение матриц в степень Многочлены от матриц Транспонирование и сопряжение матриц Блочные матрицы Произведение и сумма матриц Кронекера Метод Гаусса приведения матрицы к ступенчатому виду Элементарные преобразования матриц

Определители

Определители матриц и их основные свойства Формула полного разложения определителя Формула Лапласа полного разложения определителя Определитель произведения матриц Методы вычисления определителей

Ранг матрицы

Линейная зависимость и линейная независимость строк (столбцов) матрицы Ранг матрицы и базисный минор матрицы Методы вычисления ранга матрицы Ранг системы столбцов (строк)

Обратная матрица

Обратные матрицы и их свойства Ортогональные и унитарные матрицы Способы нахождения обратной матрицы Матричные уравнения Односторонние обратные матрицы Скелетное разложение матрицы Полуобратная матрица Псевдообратная матрица

Системы уравнений

Системы линейных алгебраических уравнений Метод Гаусса решения систем линейных уравнений Структура общего решения системы уравнений Решение систем с помощью полуобратных матриц Псевдорешения системы линейных уравнений

Функциональные матрицы

Функциональные матрицы скалярного аргумента Производные матриц по векторному аргументу Линейные и квадратичные формы и их преобразования Приведение форм к каноническому виду Закон инерции вещественных квадратичных форм Знакоопределенность форм вещественных квадратичных Формы и исследование функций на экстремум

Многочленные матрицы

Многочленные матрицы (лямбда-матрицы) Операции над лямбда-матрицами Простые преобразования многочленных матриц Инвариантные множители многочленной матрицы

Функции от матриц

Собственные векторы и значения матрицы Подобие числовых матриц Характеристический многочлен матрицы Минимальный многочлен матрицы Теорема Гамильтона-Кэли Жорданова форма матрицы Приведение матрицы к жордановой форме Многочлены от матриц Применение многочленов от матриц Функции от матриц

Линейные пространства

Линейные пространства: определение и примеры Размерность и базис линейного пространства Преобразования координат в линейном пространстве Изоморфизм линейных пространств

Подпространства

Подпространства линейного пространства Пересечение и сумма подпространств Способы описания подпространств Нахождение дополнения и суммы подпространств Нахождение пересечения подпространств

Линейные отображения

Линейные многообразия Линейные отображения Матрица линейного отображения Ядро и образ линейного отображения

Линейные операторы

Линейные операторы (преобразования) Инвариантные подпространства Собственные векторы и значения оператора Свойства собственных векторов операторов Канонический вид линейного оператора Методика приведения линейного преобразования к каноническому виду

Евклидовы пространства

Комплексный анализ

Комплексные числа

Комплексные числа в алгебраической форме Комплексные числа в тригонометрической и показательной формах Множества на комплексной плоскости Последовательности и ряды комплексных чисел

Комплексные функции

Функции комплексного переменного. Предел, непрерывность и производная Элементарные функции комплексного переменного Дифференцирование функций комплексного переменного Аналитические функции и их свойства Конформные отображения
и их свойства Интегрирование функций комплексного переменного

Функциональные ряды в комплексной области

Функциональные ряды и последовательности Степенные ряды и их свойства Разложение функций в степенные ряды Нули аналитических функций Ряд Лорана и разложение функций по целым степеням

Особые точки, Вычеты

Изолированные особые точки функций и полюсы Вычеты и их применение Вычисление интегралов с помощью вычетов Вычеты и расположение нулей многочлена

Операционное исчисление

Преобразование Лапласа и его свойства Решение ДУ операционным методом Анализ выходных процессов линейных стационарных систем Z-преобразование и его свойства

Дифференциальные уравнения

ДУ первого порядка

Основные понятия и определения ДУ Метод изоклин для ДУ 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]

▼ Доказательство

Руководствуясь определением 32.9 композиции машин Тьюринга, нетрудно понять, что если машина [math]F[/math] правильно вычисляет функцию [math]f(y)[/math], а машина [math]G[/math] правильно вычисляет функцию [math]g(x)[/math], то композиция этих машин [math]F\cdot G[/math] правильно вычисляет суперпозицию этих функций [math]f(g(x))\colon[/math]

[math]\begin{array}{ll}&\qquad q_101^x\,;\\ G\colon&\qquad q01^{g(x)}\,;\\ F\colon&\qquad q01^{f(g(x))}\,. \end{array}[/math]

Рассмотрим более сложную суперпозицию вычислимых функций: [math]\varphi(x,y)= f(g_1(x,y), g_2(x,y))[/math]. Пусть машины [math]F,\,G_1,\,G_2[/math] правильно вычисляют функции [math]f,\,g_1,\,g_2[/math] соответственно. Сконструируем машину Тьюринга, правильно вычисляющую сложную функцию [math]\varphi(x,y)[/math], пользуясь введенными в предыдущей лекции машинами сдвига, транспозиции, копирования и нулевой функции:

G_1\colon&\qquad 01^x01^yq01^{g_1(x,y)};\\[2pt] C\colon&\qquad 01^{g_1(x,y)}q01^x01^y\,;\\[2pt] G_2\colon&\qquad 01^{g_1(x,y)}q01^{g_2(x,y)};\\[2pt] B\colon&\qquad q01^{g_1(x,y)}01^{g_2(x,y)};\\[2pt] F\colon&\qquad q01^{f(g_1(x,y), g_2(x,y))};\\[2pt] q0\to q_00\colon&\qquad q_001^{f(g_1,g_2)}. \end{array}">[math]\begin{array}{ll} &\qquad q_101^x01^y\,;\\[2pt] K_2\colon&\qquad 01^x01^yq01^x01^y\,;\\[2pt]

Сконструируйте самостоятельно композицию машин, правильно вычисляющих функцию

[math]\varphi(x,y)= f \bigl(g_1(x,y),\, g_2(x,y),\, g_3(x,y)\bigr).[/math]

Подстановки указанного вида достаточно специфичны (все функции [math]g[/math] имеют одно и то же число аргументов) и не исчерпывают всевозможных подстановок, которые можно производить над функциями. Но благодаря функциям-проекторам [math]I_m^n[/math] этот недостаток легко устраняется: любая суперпозиция функций в функции может быть выражена через суперпозиции указанного вида и функции-проекторы. В самом деле, например, суперпозиция [math]f(g_1(x_1,x_2), g_2(x_1))[/math] может быть в требуемом виде представлена так: [math]f\bigl(g_1(x_1,x_2),\, I_1^2(g_2(x_1), g_3(x_1))\bigr)[/math] — любая функция от [math]x_1[/math]. В свою очередь, используя подстановку и функции-проекторы, можно переставлять аргументы в функции:

[math]\begin{gathered}f(x_2,x_1,x_3,\ldots,x_n)= f \bigl(I_2^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\\ f(x_1,x_1,x_3,\ldots,x_n)= f \bigl(I_1^2(x_1,x_2),\, I_1^2(x_1,x_2),\, x_3,\,\ldots,\,x_n\bigr);\end{gathered}[/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.7. Покажем, как, исходя из простейших функций, с помощью оператора примитивной рекурсии получить следующую функцию, называемую усеченной разностью:

[math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y= \begin{cases}x-y,&\text{if}\quad x \geqslant y,\\ 0,&\text{if}\quad x<y. \end{cases}[/math]

Во-первых, отметим, что функция [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1[/math], получающаяся из функции [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y[/math] фиксированием второго аргумента, удовлетворяет следующим соотношениям:

[math]\begin{aligned}& 0 \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=0=O(x);\\ & (x+1) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1=x= I_1^2(x,y),\end{aligned}[/math]

т.е. получена из простейших функций [math]O(x)[/math] и [math]I_1^2(x,y)[/math] с помощью оператора примитивной рекурсии. Во-вторых, нетрудно понять, исходя из определения усеченной разности, что эта функция удовлетворяет также равенствам:

[math]\begin{aligned}& x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 0=x= I_1^2(x,y);\\ & x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; (y+1)= (x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y) \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1= h(x,y,x -.1 y)\end{aligned}[/math]

для любых [math]x[/math] и [math]y[/math]. Тождества показывают, что двухместная функция [math]x \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; y[/math] получена с помощью оператора примитивной рекурсии из простейшей функции [math]I_1^2(x,y)[/math] и функции [math]h(x,y,z)= z \;\begin{matrix}.\\[-6pt]-\\[-7pt]{}\end{matrix}\; 1[/math].

Пример 33.8. Покажем, что функция [math]s(x,y)=x+y[/math] может быть получена из простейших с помощью оператора примитивной рекурсии. Для функции верны следующие тождества:

[math]\begin{aligned}& x+0=x;\\ & x+(y+1)= (x+y)+1, \end{aligned}[/math]

которые можно записать в виде

[math]\begin{aligned}s(x,0)=x;\\ s(x,y+1)= s(x,y)+1\end{aligned}[/math] или [math]\begin{aligned}s(x,0)= I_1^1(x);\\ s(x.y+1)= S(s(x,y)),\end{aligned}[/math],

а это и есть схема примитивной рекурсии, основывающаяся на простейших функциях [math]I_1^1[/math] и [math]S[/math].

Пример 33.9. Аналогично операции сложения, очевидные соотношения для операции умножения

[math]p(x,0)= x\cdot0=0= O(x),\quad p(x,x+1)= x\cdot y+x= p(x,y)+x= x+p(x,y)= s(x,p(x,y))[/math]

говорят о том, что функция [math]p(x,y)=x\cdot y[/math] получена из простейшей функции [math]O(x,y)[/math] и функции [math]s(x,y)=x+y[/math] с помощью оператора примитивной рекурсии.

Теорема 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], сама правильно вычислима на машине Тьюринга.

▼ Доказательство

Для краткости записей будем считать, что функция [math]\varphi[/math] связана с функциями [math]f[/math] и [math]g[/math] следующим образом: [math]\varphi(x,0)= f(x),~ \varphi(x,i+1)= g(x,\varphi(x,i))[/math]. Обозначим [math]F[/math] и [math]G[/math] — машины Тьюринга, правильно вычисляющие функции [math]f[/math] и [math]g[/math] соответственно. Пусть [math]x,\,y[/math] — произвольные натуральные числа. Требуется сконструировать машину Тьюринга, вычисляющую значение [math]\varphi(x,y)[/math]. Как мы уже отмечали, для вычисления [math]\varphi(x,y)[/math] предстоит вычислить [math]y+1[/math] значений [math]\varphi(x,0), \varphi(x,1),\ldots,\varphi(x,y-1),\varphi(x,y)[/math].

Начальная конфигурация такова: [math]q_101^x01^y0[/math]. Применим к ней следующую последовательность машин Тьюринга: [math]B^{+}V \Gamma VB^{+}F[/math]. В результате получим последовательность конфигураций:

[math]\begin{aligned}q_101^x01^y0\quad \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^xq01^y0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^yq01^x0 \\ \mathop{\Rightarrow}\limits^{\Gamma}&\quad 01^yq01^x01^x0\\ \mathop{\Rightarrow}\limits^{V}&\quad 01^xq01^y01^x0\\ \mathop{\Rightarrow}\limits^{B^{+}}&\quad 01^x01^yq01^x0\\ \mathop{\Rightarrow}\limits^{F}&\quad 01^x01^yq_{\alpha}01^{\varphi(x,0)}0. \end{aligned}[/math]

На последнем шаге, применив машину, вычисляющую функцию [math]f(x)[/math], к конфигурации [math]q01^x[/math], мы получим значение [math]f(x)[/math], которое, согласно схеме примитивной рекурсии для [math]\varphi[/math], есть [math]\varphi(x,0)[/math]. (Промежуточным состояниям [math]q[/math] мы намеренно не приписывали никаких индексов. Индекс [math]\alpha[/math] получило лишь последнее в этой последовательности состояние.)

Теперь мы можем приступить к вычислению [math]\varphi(x,1)[/math], используя второе соотношение схемы примитивной рекурсии: [math]\varphi(x,1)= g(x,\varphi(x,0))[/math]. Для этого применим сначала к последней конфигурации команды: [math]q_{\alpha}0\to q_{\alpha+1}0L,~ q_{\alpha+1}\to q_{\alpha+2}0[/math]. В результате получим конфигурацию: [math]01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0[/math]. Теперь нужно подготовить ленту машины к применению машины [math]G[/math], вычисляющей значение [math]g(x,\varphi(x,0))[/math], т.е. необходимо получить на ленте конфигурацию [math]q01^x01^{\varphi(x,0)}[/math]. Для этого применим к конфигурации [math]01^x01^{y-1} q_{\alpha+2}001^{\varphi(x,0)}0[/math] последовательность машин [math]AB^{-}VB^{+}V\Gamma VB^{-} VB^{+}B^{+} VB^{-}[/math]. Получим последовательность конфигураций:

[math]\begin{aligned}&01^x01^{y-1}q_{\alpha+2}001^{\varphi(x,0)}0 \quad \mathop{\Rightarrow}\limits^{A}\quad 01^x01^{y-1}q01^{\varphi(x,0)}00 \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^xq01^{y-1}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V} \\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{\Gamma}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{\Gamma}\quad 01^{y-1}01^{\varphi(x,0)}q01^{x}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{y-1}01^{x}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{y-1}q01^{x}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{V}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}q01^{y-1}01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}q01^{\varphi(x,0)}01^{x} \quad \mathop{\Rightarrow}\limits^{B^{+}}\\[2pt] &\quad \mathop{\Rightarrow}\limits^{B^{+}}\quad 01^{x}01^{y-1}01^{\varphi(x,0)}q01^{x} \quad \mathop{\Rightarrow}\limits^{V}\quad 01^{x}01^{y-1}01^{x}q01^{\varphi(x,0)} \quad \mathop{\Rightarrow}\limits^{B^{-}}\quad 01^{x}01^{y-1}q01^{x}01^{\varphi(x,0)}. \end{aligned}[/math]

Теперь мы можем применить машину [math]G[/math] и вычислить значение

[math]\varphi(x,1)= g\bigl(x,\varphi(x,0)\bigr)\,\colon 01^x01^{y-1} q_{\beta}01^{\varphi(x,0)}.[/math]

Применим к этой конфигурации команду: [math]q_{\beta}0\to q_{\alpha}0[/math], зацикливающую программу. Получим конфигурацию: [math]01^x01^{y-1}q_{\alpha}01^{\varphi(x,1)}[/math].

Начинается следующий цикл, осуществляемый командами идущими после первого появления состояния [math]q_{\alpha}[/math]. Этот цикл пре' образует конфигурацию вида [math]01^x01^{y-i}q_{\alpha}01^{\varphi(x,1)}[/math] в конфигурации [math]01^x01^{y-(i+1)}q_{\beta}01^{\varphi(x,i+1)}[/math] при условии, что [math]y>i[/math]. Команда [math]q_{\beta}0\to q_{\alpha}0[/math] зацикливает программу, и в результате работы цикла параметр [math]y-i[/math] будет понижаться до тех пор, пока не получится конфигурация [math]01^x0 q_{\alpha}01^{\varphi(x,y)}[/math], которая в силу команды [math]q_{\alpha}0\to q_{\alpha+1}0L[/math] перейдете конфигурацию [math]01^xq_{\alpha+1}001^{\varphi(x,y)}[/math].

Дополнительные команды [math]q_{\alpha+1}0\to q_{\beta+1}0,\, A,\,V,\,O,\,V,\,B^{-},\,A[/math] создают на ленте требуемую конфигурацию [math]q_001^{\varphi(x,y)}[/math], доказывающую, что функция [math]\varphi(x,y)[/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. Искомая функция конструируется с помощью последовательности вычислимых функций, в которой каждая функция растет существенно быстрее предыдущей.

▼ Доказательство

Начнем с построения такой последовательности. Мы знаем, что произведение растет быстрее суммы, а степень — быстрее произведения. Начнем построение последовательности именно с этих функций, введя для них единообразные обозначения:

[math]P_0(a,y)= a+y;\qquad P_1(a,y)=a\cdot y;\qquad P_2(a,y)=a^y.[/math]

Эти функции связаны между собой следующими рекурсивными соотношениями:

[math]\begin{aligned}P_1(a,y+1)&= a+ay= P_0(a, P_1(a,y)),\quad P_1(a,1)=a;\\ P_2(a,y+1)&= a\cdot a^y= P_1(a, P_2(a,y)),\quad P_2(a,1)=a. \end{aligned}[/math]

Продолжим эту последовательность, положив по определению для [math]n=2,3,\ldots\colon[/math]

[math]\left.{\begin{aligned}&P_{n+1}(a,0)=1,\\ &P_{n+1}(a,1)=a,\\ &P_{n+1}(a,y+1)= P_n(a,P_{n+1}(a,y)).\end{aligned}}\right\}[/math]

(1)

(Первое из равенств (1) предназначено для того, чтобы функции [math]P_n(a,y)[/math] были всюду определены.) Эта схема имеет вид примитивной рекурсии, и, следовательно, все функции [math]P_n(a,y)[/math] примитивно рекурсивны. Растут они крайне быстро. Например, [math]P_3(a,1)=a,~ P_3(a,2)= P_2(a,a)=a^a,~\ldots[/math]. Значение [math]P_3(a,k+1)[/math] получается в результате возведения числа [math]a[/math] в степень [math]a[/math] k-раз.

Зафиксируем теперь значение [math]a=2[/math]. Получим последовательность функций от одного аргумента: [math]P_0(2,y),\, P_1(2,y),\,\ldots[/math]. Введен, две новые функции: [math]B(x,y)= P_x(2,y)[/math] (она перечисляет последнюю последовательность) и [math]A(x)= B(x,x)[/math]. Первая из них называется функцией Аккермана, а вторая — диагональной функцией Аккермана.

Для функции [math]B(x,y)[/math] на основании введенных выше обозначений и соотношений (1) вытекают следующие равенства:

[math]\left.{\begin{aligned}& B(0,y)=2+y,\\ & B(x+1,0)= \operatorname{sg}(x),\\ & B(x+1,y+1)=B(x,B(x+1,y)), \end{aligned}}\right\}[/math]

(2)

которые позволяют вычислять значение функции [math]B(x,y)[/math], а следовательно, и значения функции [math]A(x)[/math]. При этом в процессе вычисления значения функции [math]B(x,y)[/math] в некоторой точке используются вычисленные ранее ее значения в неких предыдущих точках. Этим схема (2) похожа на схему примитивной рекурсии. Но примитивная рекурсия ведется по одному аргументу, а в схеме (2) рекурсия ведется сразу по двум аргументам (такая рекурсия называется двойной, двухкратной, или рекурсией второй ступени). При этом существенно усложняется характер упорядочения точек, а следовательно, и понятие предшествующей точки. Это упорядочение не предопределено заранее, как в схеме примитивной рекурсии, где число [math]n[/math] всегда предшествует числу [math]n+1[/math], а выясняется в ходе вычислений и для каждой схемы (2), вообще говоря, различно. Например, [math]B(3,3)= B(2,B(3,2))[/math], а так как

[math]B(3,2)= P_3(2,2)= P_2(2,P_3(2,1))= P_2(2,2)=2^2=4,[/math]

то вычислению [math]B[/math] в точке [math](3,3)[/math] по схеме (2) должно предшествовать вычисление [math]B[/math] в точке (2, 4): [math]B(3,3)= B(2,4)= P_2(2,4)=24=16[/math]. Проверьте самостоятельно, что вычислению [math]B[/math] в точке [math](3 4)[/math] должно предшествовать вычисление в точке [math](2,16)[/math].

Итак, функция [math]B(x,y)[/math], а вместе с ней и функция [math]A(x)[/math] вычислимы (по схеме (2)), а значит, в силу гипотезы Тьюринга, вычислимы посредством подходящей машины Тьюринга. Возникает вопрос, можно ли их вычисление свести к вычислению по схеме примитивной рекурсии, т. е. будут ли эти функции примитивно рекурсивными. Именно такова ситуация с функцией Аккермана [math]A(x)[/math]. Идея доказательства того, что функция [math]A(x)[/math] не является примитивно рекурсивной, состоит в доказательстве того, что функция [math]A(x)[/math] растет быстрее, чем любая примитивно рекурсивная функция, и поэтому не может быть примитивно рекурсивной. Более точно, для любой примитивно рекурсивной функции [math]f(x)[/math] от одного аргумента найдется такое [math]n[/math], что для любого [math]x\geqslant n[/math] будет [math]A(x)>f(x)[/math]. (Это доказал Аккерман в 1928 г.)

Идея доказательства этого утверждения состоит в следующем. Сначала доказываются два свойства функции [math]B(x,y)[/math], которые используются в дальнейшем:

[math]\begin{aligned}& B(x,y+1)> B(x,y)\quad (x,y=1,2,\ldots);\\ & B(x+1,y)\geqslant B(x,y+1)\quad (x \geqslant 1,~ y \geqslant 2). \end{aligned}[/math]

Затем вводится понятие B-мажорируемой функции. Функция [math]f(x_1,\ldots,x_n)[/math] называется B-мажорируемой, если

[math](\exists m\in \mathbb{N})(\forall x_1,\ldots,x_n) \bigl[\max(x_1,\ldots,x_n)>1\to f(x_1,\ldots,x_n)< B(m,\max(x_1,\ldots,x_n))\bigr].[/math]

Доказывается, что все примитивно рекурсивные функции B-мажорируемы. (Сначала устанавливается B-мажорируемость простейших функций [math]O,\,S(x),\,I_m^n(x)[/math]. Затем доказывается, что оператор суперпозиции, примененный к B-мажорируемым функциям, дает B-мажорируемую функцию. Аналогичным свойством обладает и оператор примитивной рекурсии.)

Наконец, рассмотрим произвольную примитивно рекурсивную функцию [math]f(x)[/math]. В силу предыдущего утверждения, для некоторого [math]m[/math] и любого [math]x\geqslant 2[/math] имеем [math]f(x)<B(m,x)[/math]. Но тогда [math]A(m+x)= B(m+x,m+x)> B(m,m+x)> f(m+x)[/math]. (Предпоследнее неравенство получено исходя из двух свойств функции [math]B(x,y)[/math], сформулированных вначале.) Это и означает, что [math]A(x)>f(x)[/math], начиная по меньшей мере с [math]x=m+2[/math].

Итак, функция Аккермана [math]A(x)[/math] не может быть вычислена по схеме примитивной рекурсии, но может быть вычислена по более сложной схеме (2). Следовательно, примитивно рекурсивные функции не исчерпывают класса всех вычислимых функций, а свойство функции быть примитивно рекурсивной не равносильно ее свойству быть вычислимой (в том числе по Тьюрингу). Это говорит о том, что если мы не оставляем затеи породить из простейших функций все вычислимые функции, то мы должны ввести какие-то дополнительные средства (методы) порождения. Таким средством явится оператор минимизации.

Оператор минимизации

Это — оператор наименьшего числа в определении 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.17. Рассмотрим следующую функцию, получающуюся с помощью оператора минимизации:

[math]d(x,y)= \mu z[y+z=x]= \mu z \bigl[s(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].[/math]

Вычислим, например, [math]d(7,2)[/math]. Для этого нужно положить [math]y=2[/math] и, придавая переменной [math]z[/math] последовательно значения [math]0,1,2,\ldots[/math], каждый раз вычислять сумму [math]y+z[/math]. Как только она станет равной 7, то соответствующее значение [math]z[/math] принять за значение [math]d(7,2)[/math]. Вычисляем:

[math]\begin{aligned}&z = 0,~~2+0 = 2 \ne 7 ;\\ &z= 1,~~ 2+ 1 = 3 \ne 7 ;\\ &z=2,~~ 2+2 = 4 \ne 7 ;\\ &z = 3,~~ 2 + 3 = 5\ne 7;\\ &z= 4,~~ 2 + 4 = 6 \ne 7 ;\\ &z = 5,~~ 2 + 5 = 7.\end{aligned}[/math]

Таким образом, [math]d(7,2)=5[/math].

Попытаемся вычислить по этому правилу [math]d(3,4)\colon[/math]

[math]\begin{aligned}&z = 0,~~ 4 + 0 = 4 > 3 ;\\&z= 1,~~ 4+ 1 = 5 > 3;\\&z = 2,~~ 4 + 2 = 6 > 3 ;\\&\ldots \ldots\ldots\ldots\ldots \end{aligned}[/math]

Видим, что данный процесс будет продолжаться бесконечно. Следовательно, [math]d(3,4)[/math] не определено.

Пример 33.18. Аналогично, с помощью оператора минимизации можно получить частичную функцию, выражающую частное от деления двух натуральных чисел:

[math]x\!\!\not{\phantom{|}}\,y= q(x,y)= \mu z[y\cdot z=x]= \mu z \bigl[p(I_2^3(x,y,z), I_3^3(x,y,z))= I_1^3(x,y,z)\bigr].[/math]

Заметим, что обе функции из двух последних примеров не всюду определены, т. е. являются частичными.

С помощью µ-оператора можно построить некоторые всюду определенные аналоги рассмотренных функций:

[math]\begin{aligned}&[x-y]= \mu z[y+z \geqslant x]= \mu z[y+z+1>x];\\ &[x\!\!\not{\phantom{|}}\,y]= \mu z[y(z+1)>x].\end{aligned}[/math]

Первая из этих функций равна 0, если [math]x<y[/math], и равна [math]x-y[/math], если [math]x\geqslant y[/math]. Вторая представляет собой целую часть функций [math]x\!\!\not{\phantom{|}}\,y[/math].

Заметим, что механизм проявления неопределенности функции в точке при вычислении ее значения с помощью µ-оператора такой же, как и при вычислении ее на машине Тьюринга: в случае неопределенности процесс вычисления не останавливается, а продолжается неограниченно долго.

Общерекурсивные и частично рекурсивные функции

Итак, функция называется частично рекурсивной (определение 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], также правильно вычислима на машине Тьюринга.

▼ Доказательство

Обозначим [math]F[/math] — машину Тьюринга, правильно вычисляющую функцию [math]f(x,y)[/math]. Используя ее, сконструиру-ем такую машину Тьюринга, которая для заданного значения х вычисляет последовательно значения [math]f(x,0), f(x,1), f(x,2),\ldots[/math] до тех пор, пока в первый раз получится [math]f(x,i)=0[/math]. После этого машина Должна выдать на ленту число [math]i[/math], представляющее собой значение Функции [math]\varphi(x)=i[/math]. Если же для всех [math]i[/math] будет иметь место [math]f(x,i)>0[/math], то машина должна работать вечно, и это будет означать, что функция [math]\varphi[/math] не определена в точке [math]x[/math]. Начальная конфигурация на конструируемой машине такова: [math]q_101^x0[/math]. Будем мыслить ее следующим образом: [math]q_101^x01^0[/math] и начнем с применения к ней машины "копирование" [math]\mathsf{K}_2[/math]. Получим конфигурацию: [math]01^x01^0q01^x01^0[/math]. Теперь вычислим значение [math]f(x,0)[/math], применив машину [math]F\colon\, 01^x01^0q_{\alpha}01^{f(x,0)}[/math].

Далее подбираем команды, которые при условии [math]f(x,i)>0[/math] преобразовывают конфигурацию [math]01^x01^iq01^{f(x,i)}[/math] в конфигурацию [math]01^x01^{i+1}q01^{f(x,i+1)}\colon[/math]

[math]\begin{array}{rl}q_{\alpha}0 \to q_{\alpha+1}0\Pi\colon &\qquad 01^x01^0q_{\alpha+1}1^{f(x,0)};\\ q_{\alpha+1}1 \to q_{\alpha+2}0\colon &\qquad 01^x01^0q_{\alpha+2}01^{f(x,0)-1};\\ q_{\alpha+2}0 \to q_{\alpha+3}0L\colon &\qquad 01^x01^0q_{\alpha+3}001^{f(x,0)-1};\\ q_{\alpha+3}0 \to q_{\alpha+4}1\colon &\qquad 01^x01^0q_{\alpha+4}101^{f(x,0)-1};\\ q_{\alpha+4}1 \to q_{\alpha+5}1\Pi\colon &\qquad 01^x01^1q_{\alpha+5}01^{f(x,0)-1};\\ O\colon &\qquad 01^x01^1q0;\\ B^{-}B^{-}\colon &\qquad q01^x01^1;\\ K_2\colon &\qquad 01^x01^1q01^x01^1;\\ F\colon &\qquad 01^x01^1q_{\beta}01^{f(x,1)};\\ q_{\beta}0\to q_{\alpha}0\colon &\qquad 01^x01^1q_{\alpha}01^{f(x,1)}.\end{array}[/math]

Последняя команда зацикливает программу, и машина от конфигурации [math]01^x01^1q_{\alpha}01^{f(x,1)}[/math] переходит к конфигурации [math]01^x01^2q_{\alpha}01^{f(x,2)}[/math], затем к конфигурации [math]01^x01^3q_{\alpha}01^{f(x,3)}[/math] и т.д. Допустим, что по истечении некоторого времени машина достигла конфигурации [math]01^x01^iq_{\alpha}01^{f(x,i)}[/math], при которой [math]f(x,i)=0[/math]. Это означает, что [math]f(x,i)=0[/math] и машина должна выдать этот результат. Число [math]i[/math] накоплено в "счетчике" [math]01^i[/math]. Поэтому поступаем следующим образом. Уже имеющаяся команда [math]q_{\alpha}0\to q_{\alpha+1}0\Pi[/math] приведет машину к конфигурации [math]01^x01^i0q_{\alpha+1}0[/math]. Следующие команды выдают на ленту необходимую конфигурацию [math]q_001^i[/math], то есть [math]q_001^{\varphi(x)}\colon[/math]

[math]\begin{array}{rl}q_{\alpha+1}0\to q_{\gamma}0\colon &\qquad 01^x01^iq_{\alpha}0;\\ B^{-}B^{-}\colon &\qquad 01^xq01^i;\\ BOB^{-}\colon &\qquad q_{\delta}01^i;\\ q_{\delta}0\to q_00\colon &\qquad q_001^{\varphi(x)}.\end{array}[/math]

Теорема доказана.

Следствие 33.20. Всякая частично рекурсивная функция вычислима по Тьюрингу.

Доказательство. Итак, поскольку оператор минимизации сохраняет свойство вычислимости по Тьюрингу (этим же свойством, как было установлено выше, обладают и операторы суперпозиции и примитивной рекурсии), простейшие функции [math]O,\,S,\,I_m^n[/math] вычислимы по Тьюрингу, а всякая частично рекурсивная функция получается из простейших с помощью применения конечного числа раз трех указанных операторов, то всякая частично рекурсивная функция вычислима по Тьюрингу.

Частичная рекурсивность функций, вычислимых по Тьюрингу

Наконец мы расширили класс вычислимых по Тьюрингу функций до таких размеров, что он исчерпывает класс всех вычислимых по Тьюрингу функций. Это нам и предстоит доказать. Другими словами, мы намерены доказать, что вычислимы по Тьюрингу лишь частично рекурсивные функции, т.е. если функция вычислима по Тьюрингу, то она частично рекурсивна. Еще точнее, по функциональной схеме (программе) машины Тьюринга, вычисляющей функцию [math]f(x_1,\ldots, x_n)[/math], можно построить рекурсивное описание этой функции. Эта теорема впервые была доказана Тьюрингом.

Теорема 33.21. Если функция вычислима по Тьюрингу, то она частично рекурсивна.

▼ Доказательство

Прежде чем приступить к доказательству теоремы, обратим внимание на следующее обстоятельство. Машина Тьюринга, преобразовывающая слова в алфавите [math]A=\{a_0,a_1,\ldots, a_{m-1}\}[/math], никак не различает природу этого алфавита. В частности, она никак не отличает числа от "нечисел": работая с числами, машина не считает их в смысле известных арифметических правил, а преобразовывает слова, представляющие собой записи чисел на каком-то языке (в какой-то системе счисления). Правила преобразований задаем мы с помощью соответствующей программы, и мы же даем полученному машиной словесному результату числовую интерпретацию. Именно в этом смысле мы говорили о вычислимости машиной Тьюринга тех или иных числовых функций. Чтобы доказать сформулированную теорему, необходимо идею арифметической (числовой) интерпретации работы машины Тьюринга довести до определенного совершенства и показать, что любое преобразование, осуществляемое машиной Тьюринга, если его интерпретировать как вычисление, является частично рекурсивным.

Разделим доказательство на этапы (их будет пять).

Первый этап. Арифметизация машин Тьюринга начинается с того, что мы вводим в машину своего рода арифметическую систему координат. Эта система координат предназначена для конфигураций машины. Как известно, в каждый момент времени конфигурация на ленте машины Тьюринга имеет вид [math]\alpha q_ia_j \beta[/math], где [math]\alpha[/math] — слово в алфавите [math]A=\{a_0,a_1,\ldots, a_{m-1}\}[/math], записанное на ленте левее обозреваемой в данный момент ячейки; [math]q_i[/math] — состояние, в котором находится в данный момент машина; [math]a_j[/math] — содержимое обозреваемой в данный момент ячейки; [math]\beta[/math] — слово в алфавите [math]A[/math], записанное на ленте правее обозреваемой ячейки. Указанной конфигурации однозначно сопоставляется упорядоченная четверка [math](\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})[/math] чисел, определяемых следующим образом: [math]\widetilde{q}_i=i;~ \widetilde{a}_j=j;~ \widetilde{\alpha}[/math] — число, изображаемое цифрами, полученными кодированием символов слова [math]\alpha[/math] по следующему правилу: эти символы интерпретируются как m-ичные цифры, т.е. цифры m-ичной системы счисления, т.е. [math]a_i[/math] кодируется цифрой [math]i[/math]; [math]\widetilde{\beta}[/math] аналогично получается из [math]\beta[/math], но при этом читается справа налево, т.е. крайняя слева ячейка [math]\beta[/math] содержит самый младший разряд, а крайняя справа — самый старший (это сделано для того, чтобы нули справа от [math]\beta[/math] не влияли на значение [math]\widetilde{\beta}[/math]).

Завершим кодирование элементов машины Тьюринга. Символу [math]a_0[/math] пустой ячейки сопоставим число 0, сдвигу вправо [math]\Pi[/math] сопоставим 1, сдвигу влево [math]L[/math] — 2, отсутствию сдвига [math]C[/math] сопоставим 0, буквой [math]z[/math] закодируем заключительное состояние (состояние остановки) [math]q_0[/math]. В итоге алфавит [math]A[/math] закодируется числовым множеством [math]\widetilde{A}[/math], а алфавит [math]Q[/math] — числовым множеством [math]\widetilde{Q}[/math].

Тогда, например, если мы имеем машину Тьюринга с внешним алфавитом [math]A=\{a_0, a_1\}[/math] и на ее ленте имеется конфигурация [math]a_1a_0a_1a_1a_0q_3a_1a_1a_0a_1a_1[/math], то при нашей кодировке (или координатизации) ей соответствует следующая упорядоченная четверка натуральных чисел: [math](22, 3, 1, 13)[/math]. Поясним, как она получилась. В нашей конфигурации [math]\alpha=a_1a_0a_1a_1a_0,[/math] [math]q_i=q_3,~ a_j=a_1,[/math] [math]\beta= a_1a_0a_1a_1[/math]. Поэтому [math]\widetilde{\alpha}=10110[/math] — двоичное число, которое следующим образом переводится в десятичное:

[math][10110]_2=1\cdot 2^4+0\cdot 2^3+ 1\cdot 2^2+1\cdot 2^1+ 0\cdot 2^0=22[/math]

Далее, [math]\widetilde{q}_3=3,~ \widetilde{a}_1=1[/math] и, наконец, [math]\widetilde{\beta}= [1101]_2=13[/math].

Второй этап. При таком кодировании система команд машины Тьюринга с алфавитом [math]A[/math] и множеством состояний [math]Q[/math] превращается в тройку числовых функций:

[math]\varphi_a\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{A}[/math] (функция печатаемого символа);
[math]\varphi_q\colon~ \widetilde{Q}\times \widetilde{A}\to \widetilde{Q}[/math] (функция следующего состояния);
[math]\varphi_d\colon~ \widetilde{Q}\times \widetilde{A}\to \{0,1,2\}[/math] (функция сдвига).

Например, если среди команд машины Тьюринга имеется команда [math]q_ia_j\to q'_ia'_jX[/math], то

[math]\varphi_a(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{a}'_j,\qquad \varphi_q(\widetilde{q}_i, \widetilde{a}_j)= \widetilde{q}'_i,\qquad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)= \xi,[/math]

где [math]\xi=0,\,1,\,2[/math], если [math]X=C,\,\Pi,\,L[/math] соответственно.

Отметим, что все эти функции [math]\varphi_a,\,\varphi_q,\,\varphi_d[/math] заданы на конечном множестве [math]\widetilde{Q}\times \widetilde{A}[/math] и потому примитивно рекурсивны.

Третий этап. Выполнив одну команду, машина Тьюринга преобразует имеющуюся на ленте конфигурацию [math]K=\alpha q_ia_j \beta[/math] в новую конфигурацию [math]K'=\alpha' q'_ia'_j \beta'[/math]. При арифметизации это означает, что упорядоченной четверке чисел [math](\widetilde{\alpha},\widetilde{q}_i,\widetilde{a}_j, \widetilde{\beta})[/math], соответствующей конфигурации [math]K[/math], однозначно сопоставляется упорядоченная четверка чисел [math](\widetilde{\alpha}',\widetilde{q}'_i,\widetilde{a}'_j, \widetilde{\beta}')[/math], соответствующая конфигурации [math]K'[/math].

Например, при команде [math]q_3a_1\to q_4a_0[/math] ранее приведенная конфигурация перейдет в конфигурацию [math]K'= a_1a_0a_1a_1a_0a_0 q_4a_1a_0a_1a_1[/math], которой соответствует четверка чисел [math](44,4,1,6)[/math].

Так будет происходить почти со всеми конфигурациями, связанными с алфавитами [math]A,\,Q[/math]. В итоге на множестве таких конфигураций будет задана (вообще говоря, не всюду определенная, т.е. частичная) нечисловая функция [math]\psi_{\Theta}(K)=K'[/math], обусловленная данной машиной Тьюринга [math]\Theta[/math]. Назовем ее функцией следующего шага.

При введенной арифметизации этой функции соответствует четверка числовых функций следующего шага. Иначе говоря, [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] — это числовые функции, каждая из которых зависит от четырех числовых переменных [math]\widetilde{\alpha}, \widetilde{q}, \widetilde{a}, \widetilde{\beta}[/math]. Попытаемся понять, как эти функции связаны с функциями системы команд [math]\varphi_a, \varphi_q, \varphi_a[/math]. Во-первых, ясно, что [math]\widetilde{q}'_i= \varphi_q[/math] и функция [math]\widetilde{q}'[/math] фактически не зависит от [math]\widetilde{\alpha},\, \widetilde{\beta}[/math], а зависит лишь от [math]\widetilde{q},\, \widetilde{a}[/math], то есть [math]\widetilde{q}'(\widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= \varphi_q(\widetilde{q}_i, \widetilde{a}_j)[/math].

Рассмотрим теперь функцию [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})[/math]. Если при рассматриваемом такте работы машины ее головка осталась на месте, т.е. обозреваемая ячейка не изменилась, т.е. [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0[/math], то ясно, что [math]\widetilde{\alpha}'= \widetilde{\alpha}[/math]. Если головка сдвинулась вправо, т.е. [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1[/math], то это означает, что степень каждого разряда числа [math]\widetilde{\alpha}[/math] повысилась на единицу: нулевой разряд стал первым, первый — вторым и т.д., т.е. число [math]\widetilde{\alpha}[/math] увеличилось в [math]m[/math] раз (напомним, что [math]m[/math] — число элементов в алфавите [math]A[/math], т.е. основание системы счисления, в которой рассматривается наша арифметизация): [math]m\widetilde{\alpha}[/math]. Кроме того, в образовавшийся младший (нулевой) разряд помещается та m-ичная цифра, которая соответствует при кодировании только что вписанному на ленту элементу из [math]A[/math]. Эта цифра равна [math]\varphi_a(\widetilde{q}_i, \widetilde{a}_j)[/math]. В итоге получим, что при сдвиге вправо: [math]\widetilde{\alpha}'( \widetilde{\alpha}', \widetilde{q}'_i, \widetilde{a}'_j, \widetilde{\beta}')= m \widetilde{\alpha}+ \varphi_a(\widetilde{q}_i, \widetilde{a}_j)[/math]. Наконец, при сдвиге на данном шаге головки влево, т.е. при [math]\varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2[/math], степень каждого разряда числа [math]\widetilde{\alpha}[/math] понизилась на единицу: первый разряд стал нулевым, второй — первым и т.д., т.е. число [math]\widetilde{\alpha}[/math] уменьшилось в [math]m[/math] раз: [math]\widetilde{\alpha}\!\!\not{\phantom{|}}\,m[/math]. Но поскольку самый младший (нулевой) разряд оказался фактически как бы "отрубленным", то в итоге получилось не частное [math]\widetilde{\alpha}\!\!\not{\phantom{|}}\,m[/math] (оно могло бы оказаться дробным), а его целая часть: [math][\widetilde{\alpha}\!\!\not{\phantom{|}}\,m][/math].

Итак, для функции [math]\widetilde{\alpha}'[/math] мы получаем следующее описание с помощью оператора условного перехода:

[math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_i, \widetilde{a}_j, \widetilde{\beta})= \begin{cases}\widetilde{\alpha},& \text{elsi}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=0\quad \text{(net sdviga)},\\[2pt] m\widetilde{\alpha}+\varphi_a(\widetilde{q}_i, \widetilde{a}_j),& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=1\quad \text{(sdvig vpravo)},\\[2pt] \widetilde{\alpha}\!\!\not{\phantom{|}}\,m,& \text{esli}\quad \varphi_d(\widetilde{q}_i, \widetilde{a}_j)=2\quad \text{(sdvig vlevo)}.\end{cases}[/math]

Совершенно аналогичная, но в определенном смысле двойственная картина наблюдается и для функции [math]\widetilde{\beta}\colon[/math] при сдвиге вправо (влево) она ведет себя так же, как функция [math]\widetilde{\alpha}[/math] при сдвиге влево (вправо). Так что для нее получаем следующее описание с помощью оператора условного перехода:

[math]\widetilde{\beta}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases}\widetilde{\beta},& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ \widetilde{\beta}\!\!\not{\phantom{|}}\,m,& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ m\widetilde{\beta}+ \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}[/math]

Наконец, рассмотрим функцию [math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})[/math]. Если сдвига не происходит, то ясно, что [math]\widetilde{\alpha}'= \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j})[/math]. Если происходит сдвиг вправо, то машина приходит к обозрению самого левого разряда (напомним, что это есть младший разряд) — числа [math]\widetilde{\beta}\colon[/math] именно он был отброшен при взятии для [math]\widetilde{\beta}'[/math] целой части частного [math]\widetilde{\beta} \!\!\not{\phantom{|}}\, m[/math]. Он как раз и представляет собой остаток от деления числа [math]\widetilde{\beta}[/math] на [math]m[/math], т.е. в этом случае [math]\widetilde{\alpha}'= r(m,\widetilde{\beta})[/math]. Если же происходит сдвиг влево, то двойственно получаем: [math]\widetilde{\alpha}'= r(m, \widetilde{\alpha})[/math]. Итак, функция [math]\widetilde{\alpha}'[/math] получает следующее описание:

[math]\widetilde{\alpha}'(\widetilde{\alpha}, \widetilde{q}_{i}, \widetilde{a}_{j}, \widetilde{\beta})= \begin{cases} \varphi_{a}(\widetilde{q}_{i}, \widetilde{a}_{j}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=0\quad \text{(net sdviga)},\\ r(m,\widetilde{\beta}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=1\quad \text{(sdvig vpravo)},\\ r(m, \widetilde{\alpha}),& \text{esli}\quad \varphi_{d}(\widetilde{q}_{i}, \widetilde{a}_{j})=2\quad \text{(sdvig vlevo)}. \end{cases}[/math]

Теперь сделаем выводы. В полученных выражениях для функций [math]\widetilde{q}', \widetilde{\alpha}', \widetilde{\beta}, \widetilde{a}'[/math], а задействованы только примитивно рекурсивные функции, и указанные функции получены из этих примитивно рекурсивных функций с помощью оператора условного перехода, который, как мы знаем, сохраняет свойство примитивной рекурсивности, т.е. из примитивно рекурсивных функций создает снова примитивно рекурсивную функцию. Следовательно, все функции [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] примитивно рекурсивны.

Итак, мы доказали, что на каждом шаге любая машина Тьюринга осуществляет примитивно рекурсивное вычисление.

Четвертый этап. Рассмотрим теперь с точки зрения введенной арифметизации работу машины Тьюринга в целом.

Пусть задана начальная конфигурация [math]K(0)= (\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)[/math]. Тогда конфигурация [math]K(t)[/math], возникающая на такте [math]t[/math] работы машины, зависит от величины [math]t[/math] и компонент [math]\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math] начальной конфигурации, т.е. она является векторной функцией [math]K(t)= \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr)[/math], компоненты которой, в свою очередь, являются функциями, зависящими от переменных [math]t, \widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math]. Эти функции определяются следующим образом:

[math]\begin{aligned}&K_{\alpha}(0,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)= \widetilde{\alpha}_{0};\\[2pt] &K_{\alpha}(t+1,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)=\\ &\qquad= \widetilde{\alpha} \bigl(K_{\alpha}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{q}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{a}(t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0), K_{\beta} (t,\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0)\bigr);\\[2pt] &K_{q}(0)= \widetilde{q}_{0};\\[2pt] &K_{q}(t+1)= \widetilde{q}'\bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{a}(0)= \widetilde{a}_{0};\\[2pt] &K_{a}(t+1)= \widetilde{a}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr);\\[2pt] &K_{\beta}(0)= \widetilde{\beta}_{0};\\[2pt] &K_{\beta}(t+1)= \widetilde{\beta}' \bigl(K_{\alpha}(t), K_{q}(t), K_{a}(t), K_{\beta}(t)\bigr). \end{aligned}[/math]

(В записях для функций [math]K_{q},K_{a},K_{\beta}[/math] аргументы [math]\widetilde{\alpha}_0, \widetilde{q}_0, \widetilde{a}_0, \widetilde{\beta}_0[/math] для краткости опущены.)

Эти соотношения представляют собой схемы примитивной рекурсии, определяющие функции [math]K_{\alpha},K_{q},K_{a},K_{\beta}[/math] с помощью функций [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math]. При этом рекурсия ведется по переменной t. Примитивная рекурсивность функций [math]\widetilde{\alpha}', \widetilde{q}', \widetilde{a}', \widetilde{\beta}'[/math] установлена на предыдущем шаге доказательства. Тогда отсюда очевидно следует, что и функции. [math]K_{\alpha}, K_{q}, K_{a}, K_{\beta}[/math] также примитивно рекурсивны.

Пятый этап. Наконец, на заключительном шаге доказательства покажем, что результат работы машины Тьюринга (т.е. вычисляемая машиной функция) носит рекурсивный характер. (Обратите внимание: не примитивно рекурсивный, а рекурсивный, т. е. здесь придется использовать оператор минимизации [math]\mu[/math].)

Здесь мы докажем утверждение, обратное тому, которое было доказано в предыдущем пункте: всякая функция, правильно вычислимая на машине Тьюринга, частично рекурсивна. Пусть [math]\varphi[/math] — функция, правильно вычисляемая машиной Тьюринга. Такая машина, начав с конфигурации [math]q_1a_0 \beta_0[/math], останавливается в конфигурации вида [math]q_za_z \beta_z[/math], т.е. для такой машины [math]K_{a}(0)=0,~ K_{q}(0)=1[/math], исходное слово на ленте кодируется числом [math]m \widetilde{\beta}_0+\widetilde{\alpha}_0[/math], заключительное слово — числом [math]m \widetilde{\beta}_z+\widetilde{\alpha}_z[/math], т.е. вычисляется значение функции [math]\varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z[/math]. Заключительное слово — это слово, написанное на ленте в тот момент [math]t_z[/math], когда машина впервые перешла в заключительное состояние [math]q_z[/math], т.е. в момент [math]t_z= \mu t[K_{q}(t)=z][/math]. Поэтому [math]\widetilde{\beta}_z= K_{\beta}(t_z),~ \widetilde{\alpha}_z= K_{a}(t_z)[/math] и

[math]\varphi(m \widetilde{\beta}_0+\widetilde{\alpha}_0)= m \widetilde{\beta}_z+ \widetilde{\alpha}_z= mK_{\beta}(t_z,0,1,\widetilde{\alpha}_0, \widetilde{\beta}_0)+ K_{a}(t_z,0,1, \widetilde{\alpha}_0, \widetilde{\beta}_0).[/math]

Учитывая, что [math]\widetilde{\beta}_0= [x\!\!\not{\phantom{|}}\,m],~ \widetilde{\alpha}_0= r(m,x)[/math], выражение для результирующего значения [math]\varphi(x)[/math] можно со всеми подробностями записать так:

[math]\begin{aligned}\varphi(x)&= mK_{\beta} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m]\bigr)+\\ &\quad+ K_{a} \bigl(\mu t[K_{q}(t,0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m])=z], 0,1, r(m,x), [x\!\!\not{\phantom{|}}\,m]\bigr), \end{aligned}[/math]

где [math]m,\,z[/math] — константы, зависящие от конкретной машины. Отсюда непосредственно видно, что функция [math]\varphi(x)[/math], представляющая собой результат работы машины Тьюринга, построена из примитивно рекурсивных функций с помощью оператора минимизации [math]\mu[/math] и, следовательно, является частично рекурсивной.

Этим и завершается доказательство того, что всякая вычислимая по Тьюрингу функция частично рекурсивна.

Соединив вместе следствие 33.20 и теорему 33.21, приходим к следующей теореме.

Теорема 33.22. Функция вычислима по Тьюрингу тогда и только тогда, когда она частично рекурсивна.

Итог рассмотрений настоящей лекции состоит в том, что мы дали некую альтернативную характеристику вычислимым по Тьюрингу функциям: это те и только те функции, которые частично рекурсивны. Другими словами, класс функций, вычислимых по Тьюрингу, совпадает с классом частично рекурсивных функций. Совпадение этих двух классов вычислимых функций, в основе построения которых лежали совершенно разные подходы к формализации понятия вычислимости функции, говорит о том, что эти подходы оказались весьма состоятельными, и служит косвенным подтверждением того, что как тезис Тьюринга, так и тезис Чёрча не только не безосновательны, но и имеют все права на признание.

Портал » Список форумов

Часовой пояс: UTC + 4 часа [ Летнее время ]

Математический форум Math Help Planet

Рекурсивные функции

Происхождение рекурсивных функций

Основные понятия теории рекурсивных функций и тезис Чёрча

Примитивно рекурсивные функции

Примитивная рекурсивность предикатов

Вычислимость по Тьюрингу примитивно рекурсивных функций

Функции Аккермана

Оператор минимизации

Общерекурсивные и частично рекурсивные функции

Вычислимость по Тьюрингу частично рекурсивных функций

Частичная рекурсивность функций, вычислимых по Тьюрингу