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

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

Источник

3 ответа

Решение

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

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

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

Источник

Значение этих терминов варьируется в зависимости от вашего контекста. Если бы мы обсуждали их исключительно с точки зрения написания программ, то рекурсивные множества не имеют особого смысла; однако, может быть, я просто столкнулся с этим. Тем не менее, рекурсивные функции - это функции, которые вызывают себя при выполнении. Вычисление 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);
 }
}

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

Пусть f определена как функция, где f(x) = 1, если x ∈ ℕ, и f(x) = 0, если x ∉ ℕ

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

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

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

Дальнейшее чтение:

Источник

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

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

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

Источник
Другие вопросы по тегам