ГОУ ВПО «Московский государственный  открытый университет»

      Чебоксарский  политехнический институт (филиал)

 

      Кафедра Прикладной математики

 
 
 
 
 
 

      КУРСОВАЯ  РАБОТА

 

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

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

 
 
 
 
 
 
 
 
 

Выполнил студент:

Тян Д.С.

 

Специальность:  230105

ф/о: дневная

 

учебный шифр:_610162___

________________

Руководитель: Павлова Н.А.

 
 
 
 
 
 

Чебоксары 2011

 

Содержание:

      Глава 1. Теоритическая часть.

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

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

(от  позднелатинского recursio — возвращение)

        название, закрепившееся за одним из наиболее распространённых вариантов уточнения общего понятия арифметического алгоритма, т.е. такого Алгоритма, допустимые исходные данные которого представляют собой системы натуральных чисел, а возможные результаты применения являются натуральными числами. Рекурсивные функции были введены в 30-х гг. 20 в. С. К. Клини, в свою очередь основывавшимся на исследованиях К. Гёделя, Ж. Эрбрана и др. математиков.

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

        

Арифметические  функции, для вычисления значений которых  имеются какие-либо алгоритмы, принято  называть вычислимыми. Вычислимые функции  играют в математике важную роль. Вместе с тем, если понятию алгоритма  здесь не будет придан точный смысл, то и само понятие вычислимой функции окажется несколько расплывчатым. Рекурсивные функции уже в силу самого характера своего определения оказываются вычислимыми. В известном смысле верно и обратное: имеются серьёзные основания считать, что математическое по своему характеру понятие рекурсивности является точным эквивалентом несколько расплывчатого понятия вычислимости. Предложение считать понятие вычислимости совпадающим по объёму с понятием рекурсивности известно в теории рекурсивных функций под названием тезиса Чёрча по имени американского математика А. Чёрча, впервые (в 30-х гг. 20 в.) сформулировавшего и обосновавшего это предложение. Принятие тезиса Чёрча позволяет придать понятию вычислимой арифметической функции точный математический смысл и подвергнуть это понятие изучению при помощи точных методов.

              

Рекурсивные функции являются частичными функциями, т. е. функциями, не обязательно всюду определёнными. Чтобы подчеркнуть это обстоятельство, часто в качестве синонима используют термин «частично рекурсивные функции». Рекурсивные функции, определённые при любых значениях аргументов, называют общерекурсивными функциями.

              

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

      Операции  над функциями.

Оператор  суперпозиции (подстановки) сопоставляет функции f от n переменных и функциям g1, . . ., gn от m переменных функцию h от m переменных такую, что для любых натуральных чисел x1, .., xm

         h(x1, .., xm) ≅ f (g1(x1, .., xm), ..., gm(x1, .., xm))

        (здесь и ниже условное равенство ≅ означает, что оба выражения, связываемые им, осмыслены одновременно и в случае осмысленности имеют одно и то же значение).

 

Оператор  примитивной рекурсии сопоставляет функциям f от n переменных и g от n + 2 переменных функцию h от n + 1 переменных такую, что для любых натуральных чисел x1, .. .., xn, y

         h(x1, .., xn ,0) ≅ f(x1, .., xn),

         h(x1, .., xn, y + 1) ≅ g(x1, .., xn, y, h(x1, .., xn, y )).

 

Оператор минимизации сопоставляет функции f от n переменных функцию h от n переменных такую, что для любых натуральных чисел x1, .., xn

        h(x1, .., xn) ≅ f(x1, .., xn-1, y)

        где у таково, что f(x1, .., xn-1, y-1) определены и отличны от xn, а f(x1, .., xn, y) определена и равна xn, если же у с указанными свойствами не существует, то значение h(x1, .., xn) считается не определённым.

 

Важную  роль в теории рекурсивных функций играют т. н. примитивно рекурсивные функции — рекурсивные функции, получающиеся из исходных функций в результате конечного числа применений одних лишь операторов суперпозиции и примитивной рекурсии. Они образуют собственную часть класса общерекурсивных функций. В силу известной теоремы Клини о нормальной форме рекурсивной функции могут быть указаны такие конкретные примитивно рекурсивные функции U от одной переменной и Tn от n + 2 переменных, что для любой рекурсивной функции φ от n переменных и для любых натуральных чисел x1, . . ., xn имеет место равенство φ(x1, ..., xn) ≅ U(y), где у есть наименьшее из чисел z таких, что Tn(φ, x1, ..., xn,z) = 0 (здесь φ представляет собой т. н. геделев номер функции φ — число, которое эффективно строится по системе равенств, задающей функцию φ). Из этой теоремы, в частности, вытекает, что для рекурсивной функции от п переменных может быть построена универсальная рекурсивная функция от n+1 переменных, т. е. такая рекурсивная функция Фn, что для любой рекурсивной функции φ от n переменных и для любых натуральных чисел x1, . . ., xn имеет место условное равенство

         φ( x1, . . ., xn) ≅ Фn(x1, . . ., xn).

      Примеры.

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

Функция Сложения двух натуральных чисел ( ) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям   и  , вторая из которых получается подстановкой основной функции   в основную функцию S:

;

;

.

Умножение двух натуральных чисел ( ) может быть рассмотрено в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения оператора примитивной рекурсии к функциям O и G, вторая из которых получается подстановкой основных функций   и   в функцию сложения:

;

;

.

Симметрическая  разность (абсолютная величина разности) двух натуральных чисел ( ) может быть рассмотрена в качестве примитивно рекурсивной функции двух переменных, получаемой в результате применения следующих подстановок и примитивных рекурсий:

;

;

;

;

;

      Тезис А. Чёрча.

Тезис Чёрча-Тьюринга— фундаментальное эвристическое утверждение, существенное для многих областей науки, в том числе, для математической логики, теории доказательств, информатики, кибернетики, дающее интуитивное понятие о вычислимости. Это утверждение было высказано Алонзо Чёрчем и Аланом Тьюрингом в середине 1930-х годов.

В терминах теории рекурсии, это утверждение  формулируется как совпадение классов  вычислимых и частично рекурсивных  функций. В этой формулировке часто упоминается как просто тезис Чёрча.

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

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

Позднее были сформулированы другие практические варианты утверждения:

• Физический тезис Чёрча — Тьюринга: любая функция, которая может быть вычислена физическим устройством, может быть вычислена машиной Тьюринга;
• Сильный тезис Чёрча — Тьюринга: любой конечный физический процесс, не использующий аппарат, связанный с непрерывностью и бесконечностью, может быть вычислен физическим устройством.

      Рассмотрим  подробно тезис Чёрча - Тьюринга.

      Для этого поставим вопросы, на которые следует  обдумать:

 

• Что такое  классические вычисления?
• Что такое тезис Черча-Тьюринга?
• Что такое разрешимость?
• Что такое квантовые вычисления?
• Мог ли бы тезис Черча-Тьюринга применяться к квантовым нейронным сетям?

      Классические  вычисления

Каждый  из когда-либо построенных компьютеров  является фон Неймановским. Такие  компьютеры реализуют алгоритмы, следуя простым дискретным инструкциям (кодам  машинного языка), которые являются полностью детерминистическими и последовательными. Их действие осуществляется элементами, имеющими конечное число информационных состояний, известных как биты, и логическими вентилями, которые воздействуют на эти биты. Все это называется классической моделью вычислений. По существу Аналитическая Машина Бэббиджа, 200 или 300 летней давности1, была столь же вычислительно мощной, как и сегодняшние наиболее высокопроиз-водительные суперкомпьютеры. Не существует такой задачи, которую мог бы решить современный  компьютер, но не могла бы решить Аналитическая Машина, если ей предоставить для этого необходимое время.  Эта идея суммируется в тезисе Черча-Тьюринга.

      Тезис Черча-Тьюринга

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