Ирина Эланс

Автор который поможет с любыми образовательными и учебными заданиями

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

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

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

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

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

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

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

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

Тян Д.С.

Специальность: 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, была столь же вычислительно мощной, как и сегодняшние наиболее высокопроиз-водительные суперкомпьютеры. Не существует такой задачи, которую мог бы решить современный компьютер, но не могла бы решить Аналитическая Машина, если ей предоставить для этого необходимое время. Эта идея суммируется в тезисе Черча-Тьюринга.

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

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

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

Разрешимость

Аксиоматическая система является разрешимой, если существует машина Тьюринга, способная определить какие утверждения аксиоматической системы являются истинными, а какие ложными. Если для машины Тьюринга может быть создана программа, которая возьмет все утверждения аксиоматической системы и определит значения их истинности, тогда система разрешима. По существу это означает нахождение конечного останавливающегося алгоритма для определения истинности или ложности высказывания. Любой алгоритм, который это способен сделать, называется вычислимым. Тезис Черча-Тьюринга утверждает, что существует уровень вычислимости, который мы не можем превзойти. Все компьютеры используют этот уровень вычислимости. Поэтому все компьютеры вычислительно эквивалентны. Реальный вопрос в том, не могут ли квантовые нейронные сети (или в общем случае квантовые компьютеры) использовать уровень вычислимости выходящий за предел, определенный тезисом Черча-Тьюринга.

Квантовое поведение

“Кубит” - это квантовый бит, который можно рассматривать так же как и цифровой бит в компьютере, за исключением одного важного различия. Хотя в цифровом компьютере бит может принимать лишь значения 0 или 1, кубит может иметь значения 0,1 или же оба одновременно. Я объясню, что это означает, но сначала я расскажу, как кубит может быть создан.

Мы можем сконструировать кубит, используя атом некоторого элемента - возьмем для примера водород. Атом водорода состоит из ядра (которое нас не интересует) и орбитального электрона. Этот электрон может существовать на различных энергетических уровнях, или орбиталях вокруг ядра. Эти различные орбитали могут использоваться для представления бинарных значений 0 и 1, которые известны нам по цифровым компьютерам. Мы могли бы предположить, например, что атом водорода в основном состоянии (т.е. в состоянии, в котором электрон находится ближе всего к ядру) представляет собой значение 0. Подобным же образом, мы можем сказать, что атом, электрон которого находится на первом возбужденном уровне представляет значение 1. Для перевода электрона с одного уровня возбуждения на другой мы можем воздействовать на него поляризованным излучением лазера - по существу мы вводим в нашу систему фотоны. Как только они инжектируются, электрон начинает переходить с одного уровня энергии на другой. Так что, для того чтобы перевернуть бит из 0 в 1 мы просто облучаем атом достаточным количеством света так, чтобы электрон перешел на более высокий энергетический уровень. Для того чтобы перевести 1 в 0, мы делаем то же самое, так как перегрузка электрона приведет к переходу его назад в основное состояние. Логически это эквивалентно действию вентиля NOT, т.е. одной из тех операций, которые требуются нам в компьютере для вычислений. Используя аналогичные идеи, мы можем сконструировать вентили AND и COPY, которые вместе с вентилем NOT составляют три основные компоненты вычислительного устройства.

До сих пор мы не видели качественного различия между использованием обычных битов и кубитов, но нечто странное происходит, если мы облучаем атом светом, которого достаточно лишь для того, чтобы электрон проделал половину пути между уровнями возбуждения. Поскольку электроны не могут в действительности существовать в пространстве между этими уровнями, они существуют НА ОБОИХ уровнях одновременно. Это известно как “суперпозиция”. Эта суперпозиция позволяет нам теоретически вычислить одновременно несколько возможностей , так как группа кубитов может представлять одновременно несколько чисел. Если мы возьмем один “кубайт”, то есть 8 кубитов, то мы сможем одновременно представить 256 чисел. С числом кубитов количество представимых чисел растет по закону , где n- число кубитов.

Для вычислений с использованием свойства суперпозиции мы можем создать набор кубитов, перевести их в состояния суперпозиции и затем осуществить над ними действие. Когда алгоритм будет завершен, суперпозиция может быть сколлапсирована, и будет получен определенный результат - т.е. все кубиты перейдут в состояния 0 или 1. В основном, вы можете считать, что алгоритм как бы параллельно действует на все возможные комбинации определенных состояний кубитов (т.е. 0 или 1) - трюк, известный как квантовый параллелизм.

Итак, действительный вопрос здесь в том можно ли получить с помощью описанного квантового вычисления нечто еще не достигнутое с помощью обычных классических компьютеров? Ответ, конечно, положительный. Квантовое вычисление обеспечивает громадное преимущество по скорости. Рассмотрим задачу, которая требует исключительно большого времени вычислений на классическом компьютере, такую как факторизация 250-значного числа. По имеющейся оценке 1400 параллельно работающих современных компьютеров решат ее примерно за 800 000 лет. Даже если будут разработаны более производительные компьютеры, и мы найдем пути лучшего интегрирования широкомасштабного параллелизма, проблема все еще останется экспоненциально сложной. Однако, для квантового компьютера сложность проблемы будет полиномиальной по времени , а не экспоненциальной. Например, 1000-значное число можно будет факторизовать лишь за несколько миллионов шагов. Основная вера связана здесь с тем, что, используя параллельную природу квантовых явлений (т.е. суперпозицию), мы сможем вычислять все возможности параллельно.

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

Справедлив ли тезис Черча-Тьюринга для всех квантовых компьютеров не совсем ясно. Квантовые вычисления, о которых мы говорили до сих пор, осуществляются очень сходным образом с действием обычных компьютеров (т.е. с использованием битов, логических вентилей, памяти и т.п.), но не существует прямых доводов полагать, что это означает невозможность разработки других типов квантовых вычислений, которые являются существенно более мощными. Одной из таких моделей может быть квантовая нейронная сеть. Хотя возможно построить квантовую нейронную сеть, используя кубиты и т.п., как это описано выше, это было бы эквивалентно конструированию обычной нейронной сети на классической машине, и обеспечило бы преимущества перед обычной нейронной сетью только по скорости, но не по вычислимости. Если мы хотим сконструировать квантовую нейронную сеть, не ограниченную тезисом Черча-Тьюринга, мы должны подумать о радикально ином подходе к кубитам и логическим вентилям. Это конечно очень трудно, и до сих пор серьезных попыток в данном направлении не предпринималось. Хотя некоторые предложения, которые могут служить началом поиска нового типа квантовых вычислений, действительно существуют.

Обход ограничений тезиса Черча-Тьюринга

Ранее я отметил, что существует ряд странных теорий относительно того, как можно было бы использовать квантовый компьютер для реализации алгоритмов существенно более сложных, чем те, которые разрешимы машиной Тьюринга. Держим в уме, что они носят в высшей степени спекулятивный характер (что, как я предполагаю в любом случае относится ко всей области квантовых вычислений). Проведение вычислений, не имеющих конечного состояния (т.е. неразрешимого алгоритма) не могло бы быть возможным как на классическом, так и на имеющихся моделях квантового компьютера. Например, доказательство гипотезы Гольдбаха путем одновременной проверки всех случаев. Гипотеза Гольдбаха формулируется следующим образом “Каждое четное число может быть представлено в виде суммы двух простых чисел”. Можно было бы написать алгоритм (который не имеет остановки) для решения этой проблемы, который просто берет каждое четное число и перебирает натуральные числа до нахождения двух его простых нечетных слагаемых. Если бы мы могли использовать этот алгоритм бесконечное время, то смогли бы найти нечетные слагаемые всех четных чисел. Конечно, это невозможно на машине Тьюринга, поскольку в этом случае алгоритм не имеет остановки. И поскольку квантовый компьютер вычислительно эквивалентен машине Тьюринга, он также не способен найти ответ.

Одно из интересных решений этой проблемы предполагает использование норы червяка².Если мы создадим замкнутый ход червяка и используем его как часть нашего квантового компьютера, то мы могли бы иметь бесконечное время необходимое для вычисления ответа, просто проводя вычисление в замкнутой бесконечной петле. Другое предложение состоит в расширении чевячного хода в то что известно как ‘basement universe’ - существенно новый мир внутри нашего собственного - а затем создание другого мира внутри уже созданного и так до бесконечности. Если мы создадим эти миры используя эффект замедления времени (в согласии с общей теории относительности), тогда бы мы смогли выполнять каждое действие несколько быстрее, чем в мире-родителе. Все что мы должны бы были сделать далее, это скопировать наш квантовый компьютер из этих миров в их потомков и т.д. и это вернет результат бесконечно долгого вычисления за конечное время, фактически мгновенно.

Согласно недавно предложенной космологической теории вселенная может породить потомка, который возникает вначале в виде некоторой неоднородности (выпуклости) и преобразуется в некое подобие протуберанца, связанного с материнской вселенной узкой пуповиной, которая и называется норой червяка (wormhole). Из вселенной-родителя она выглядит как черная дыра. Эта пуповина, утончаясь, может порваться (что будет выглядеть как испарение черной дыры), и тогда вселенная-потомок отделится от материнской. Согласно теории советского физика Андрея Линде наш мир образовался именно таким образом, как маленький пузырек пространства-времени, который расширился в ходе того, что мы называем Большим Взрывом.

Глава 2. Практическая часть.

Заключение.

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

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

Также понятно, что примитивно рекурсивная функция определена везде и поэтому является общерекурсивной функцией (у примитивно рекурсивной функции нет повода «зависать», так как при её построении используются операторы, определяющие везде определённые функции).

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

Люди иногда задаются таким вопросом: « А что если ты докажешь этот тезис, что если опровергнешь? Голодающие станут сытыми, обездоленные получат лучшую жизнь, а войны прекратятся?»

Нет, просто я думаю, что человечество продвинется на шаг вперед в научной сфере. Сейчас, конечно, ты начнешь " обстрел ", а какая с этого польза и так далее. Отвечу сразу: тебе этого просто не понять. Не потому что ты глупый, а просто потому что я чувствую, что это нужно. Ведь, как говориться, чем меньше мы знаем, тем легче нам жить. Такие люди, которые думают “ а зачем все это, что с этого будет и т.п. ” были, есть и будут всегда. Именно поэтому сожгли Джордано Бруно на костре, просто потому что церковь не могла понять, какая будет польза с того что он делал. Может сейчас в данный момент от этого пользы "0". А может через лет 100-200 доказательство этого тезиса перевернет понимания кибернетики, как таковой.

Литература:

Мальцев А. И., Алгоритмы и рекурсивные функции, М., 1965 ;
Роджерс Х., Теория рекурсивных функций и эффективная вычислимость, пер. с англ., М., 1972 ;
http://dic.academic.ru ;
http://ru.wikipedia.org .