Рекурсивные множества против рекурсивных функций - PullRequest
Новая
       29

Рекурсивные множества против рекурсивных функций

2 голосов
/ 05 декабря 2009

В чем разница между рекурсивным набором и рекурсивной функцией?

Ответы [ 3 ]

8 голосов
/ 06 декабря 2009

Рекурсивные функции и рекурсивные множества - это термины, используемые в теории вычислимости. Википедия определяет их следующим образом:

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

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

6 голосов
/ 06 декабря 2009

Значение этих терминов варьируется в зависимости от вашего контекста. Если бы мы обсуждали их исключительно с точки зрения написания программ, то рекурсивные множества не имеют большого смысла; однако, может быть, я просто столкнулся с этим. Тем не менее, рекурсивные функции являются функциями, которые вызывают себя при выполнении. Вычисление n th числа Фибоначчи является классическим примером, который обычно представлен: 

/// <summary>A C# implementation of a function to return the nth Fibonacci number.</summary>
private static int Fibonacci(int n) {
 if (n <= 2) {
  return 1;
 } else {
  return Fibonacci(n - 1) + Fibonacci(n - 2);
 }
}

Тем не менее, другой контекст для этих терминов в контексте информатики и, в частности, теории вычислений, - это обсуждение формальных языков . В этом контексте рекурсивный набор определяется как набор, для которого существует разрешимая проблема принадлежности. Например, мы знаем, что множество всех натуральных чисел & # x2115; является рекурсивным набором, потому что мы можем определить рекурсивную функцию следующим образом:

Пусть f определяется как функция, где f (x) = 1 , если x & # x2208; & # x2115; и f (x) = 0 , если x & # x2209; & # X2115;

Концепция рекурсивного набора важна для концепции вычислимости, поскольку она приводит к рекурсивно перечислимому набору , который является языком, который может быть распознан машиной Тьюринга (т.е. Тюрингу узнаваемым * +1039 *). Это языки, для которых машина Тьюринга может или не может определить, является ли данная строка членом языка, или, другими словами, машина может либо принять , отклонить , или loop. Это в отличие от языка Тьюринга с разрешением , для которого машина будет вводить либо accept , либо reject состояние для данной входной строки.

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

Итак, чтобы вернуться к исходному вопросу, в контексте теории вычислений, рекурсивное множество - это то, что может быть сгенерировано (то есть перечислено) или проверено на членство рекурсивной функцией на машине Тьюринга.

Дополнительная литература:

5 голосов
/ 06 декабря 2009

Возможно, вопрос должен был звучать так: «Почему слово« рекурсивный »используется для описания как множеств, так и функций?»

Как отметил в своем комментарии Грег Хьюгилл, слово «зеленый» может быть применено к яблокам и автомобилям, но это не подразумевает отношения между яблоками и автомобилями.

Я думаю, что цитата из Википедии использует термин «рекурсивный» в качестве синонима «вычислимого», с которым мы, программисты, осторожно согласились бы, но только в определенных контекстах.

...