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

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

Курсовая работа

по дисциплине: Математическая логика и теория алгоритмов

на тему: Рекурсивные функции

Содержание

Введение

1. Цели и задачи курсовой работы

2. Алгоритмическая неразрешимость

3. Суперпозиция функций

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

3.1 Примитивно рекурсивная функция

3.2 Общерекурсивные функции

3.3 Расширенный базис клини. Частичная рекурсивность разности

3.4 Геделева нумерация и эффективная перечислимость частично-рекурсивных функций

Заключение

Список использованной литературы

Введение

Важным элементом математики является доказательство существования или отсутствия алгоритма для решения поставленной задачи.

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

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

Существует несколько подходов к определению понятия алгоритма. Одним из них связано с уточнением понятия эффективно вычислимой функции. Его вывели математики А. Черч, К. Гендель, С. Клини. В результате был выведен класс частично-рекурсивных функций, имеющих строгое математическое определение.

В данной курсовой работе рассматриваются: определение алгоритмической неразрешимости задачи; понятия суперпозиции функций, рекурсивных функций; схема примитивной рекурсии; операция минимизации.

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

Задачами курсовой работы являются:

.        пояснение определения алгоритмической проблемы, алгоритмической неразрешимости;

.        раскрытие понятия суперпозиции функций;

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

2. Алгоритмическая неразрешимость

алгоритм задача рекурсия суперпозиция

Алгоритмическая неразрешимость - важнейшее свойство некоторых классов корректно поставленных задач, допускающих применение алгоритмов. Оно состоит в том, что задачи каждого из этих классов в принципе не имеют какого-либо общего, универсального алгоритма решения, объединяющего этот класс. Несмотря на полную однотипность условий и требований, здесь, как ни парадоксально, принципиально невозможна однотипность метода решения. А. н. не означает неразрешимости тех или иных единичных проблем данного класса - часть из них может иметь свои решения. Но в целом данный класс задач не имеет ни общего универсального алгоритма решения, ни ветвящегося алгоритма полного разбиения класса на подклассы, к каждому из которых был бы применим свой специфический алгоритм.

Алгоритмически неразрешимыми являются, напр., проблема распознавания: закончит ли свою работу (остановится ли) или же «зависнет» в бесконечном цикле произвольно выбранная программа действий алгоритмического типа (не только компьютерная, но и реализуемая человеком по алгоритмическому типу); проблема эквивалентности программ (нет универсального алгоритма, позволяющего установить эту эквивалентность); проблема тождества двух математических выражений; проблема распознавания того, можно ли из имеющихся автоматов собрать заданный автомат; а также множество других проблем, относящихся к топологии, к теории групп и к другим областям.

3. Суперпозиция функций

Суперпозицией функций f1, …, fm называется функция f, полученная с помощью подстановок этих функций друг в друга и переименования переменных.

Пусть имеются два отображения <#"878563.files/image001.gif">.

Построим рекурсивное уравнение:

Результат операции минимизации не определен даже для точки х=0.

2) Функция, определенная в одной точке, .

Построим рекурсивное уравнение:

Результат операции минимизации определен только для точки х=0, при остальных значениях x вычисление (подбор нужного значения z) никогда не будет закончено.

Заключение

В данной курсовой работе рассматриваются: определение алгоритмической неразрешимости задачи; понятия суперпозиции функций, рекурсивных функций; схема примитивной рекурсии; операция минимизации.

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

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

Были рассмотрены основные понятия заданной темы:

алгоритмическая проблема

алгоритмическая неразрешимость

суперпозиция функций

примитивная рекурсия

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

В представленной работе был проведен анализ понятий: алгоритм решения задачи, алгоритмическая неразрешимость, суперпозиция функций, рекурсивная функция.

Все задачи, поставленные в задании к данной курсовой работе, выполнены в полном объеме.

Вывод:

Доказательство существования или отсутствия алгоритма для решения поставленной задачи является важным элементом математической логики, так как оно позволяет однозначно ответить на вопрос, существует ли алгоритмическое решение.

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

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

Список использованной литературы

1.      Клини С. Математическая логика. - М.: Мир, 1980.

2.      Карри Хаскелл Б. Основания математической логики. - М.: Мир, 1969

.        Карпов В.Г., Мощенский В.А. Математическая логика и дискретная математика. - Минск: «Вышэйш. школа», 1977

.        Верещагин Н.К., Успенский В.А., Плиско В.Е. Вводный курс математической логики: учебное пособие - ФИЗМАТЛИТ, 2007

.        Ершов Ю.Л., Палютин Е.А. Математическая логика - ФИЗМАТЛИТ, 2011