Почему вычислимые функции также называются рекурсивными функциями?

23

В теории вычислимости вычислимые функции также называют рекурсивными функциями. По крайней мере, на первый взгляд, они не имеют ничего общего с тем, что вы называете «рекурсивным» в повседневном программировании (т. Е. Функциями, которые сами себя вызывают).

Каково реальное значение рекурсивности в контексте вычислимости? Почему эти функции называются «рекурсивными»?

Другими словами: какова связь между двумя значениями «рекурсивность»?

computability terminology history Голо Роден
источник

2

μ-рекурсивная функция

Томас Климпел

3

Они обманывают, потому что они включают оператор μ . Это оператор минимизации, но, конечно, минимизация имеет мало общего с рекурсией. Так что, похоже, кто-то (Клин) думал, что «рекурсивный» будет звучать хорошо, поэтому он придумал оправдание для использования этого имени. Намного позже Роберт Соаре объяснил, что «вычислимый» будет звучать намного лучше, и что «рекурсивный» был просто маркетинговым трюком первых дней, и все согласились.

Томас Климпел

3

Что насчет примитивных рекурсивных функций? Скопированные из википедии, они определены как и . Это функция, которая вызывает себя.

h (0, x_{1}, \dots, x_{k}) = f (x_{1}, \dots, x_{k})

$h(0,x_{1},\ldots ,x_{k})=f(x_{1},\ldots ,x_{k})$

h (S (y), x_{1}, \dots, x_{k}) = g (y, h (y, x_{1}, \dots, x_{k}), x_{1}, \dots, x_{k})

$h(S(y),x_{1},\ldots ,x_{k})=g(y,h(y,x_{1},\ldots ,x_{k}),x_{1},\ldots ,x_{k})$

Хендрик Ян

3

@GoloRoden Обратите внимание, что описание тега «вычислимость» (вы использовали его для этого вопроса) гласит: «Теория вычислимости или теория рекурсии». Гедель называл функции рекурсивными , но термин превратился в вычислимый . Вероятно, чтобы избежать путаницы, как у вас. Люди, которые интенсивно изучают теорию вычислимости, чаще используют термин теория рекурсии, чтобы «уважать» ее корни.

Оберон

1

потому что они определены рекурсивно, то есть « более сложные функции определены в терминах ранее определенных, более простых функций »

Никос М.

13

Определите некоторые основные функции:

нулевая функция

$z e r o : N \to N : x \mapsto 0$ $zero: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto 0$
функция преемника

$s u c c : N \to N : x \mapsto x + 1$ $succ: \mathbb{N} \rightarrow \mathbb{N} : x \mapsto x + 1$
функция проекции

p_{i}^{n} : N^{n} \to N : (x_{1}, x_{2}, \dots, x_{n}) \mapsto x_{i}

$p_i^n: \mathbb{N}^n \rightarrow \mathbb{N} : (x_1, x_2, \dots, x_n) \mapsto x_i$

С этого момента я буду использовать для обозначения $\bar{x_n}$ $(x_1, x_2, \dots, x_n)$

Определите состав:

Данные функции

каждый с подписью $g_1, g_2, \dots, g_m$ $\mathbb{N}^k \rightarrow \mathbb{N}$
$f : \mathbb{N}^m \rightarrow \mathbb{N}$

Построить следующую функцию:

\begin{aligned} h : N^{k} \to N : \bar{x_{k}} \mapsto h (\bar{x_{k}}) = f ( & g_{1} (\bar{x_{k}}), g_{2} (\bar{x_{k}}), \dots, g_{m} (\bar{x_{k}})) \end{aligned}

$\begin{align} h: \mathbb{N}^k \rightarrow \mathbb{N}: \bar{x_k} \mapsto h(\bar{x_k}) = f ( & g_1(\bar{x_k}), g_2(\bar{x_k}), \dots, g_m(\bar{x_k}) ) \end{align}$

Определим примитивную рекурсию:

Данные функции

$f: \mathbb{N}^k \rightarrow \mathbb{N}$
$g: \mathbb{N}^{k+2} \rightarrow \mathbb{N}$

Построить следующую (кусочную) функцию:

час : N^{К + 1} \to N : (\bar{{Икс}_{К}}, Y + 1) \mapsto {\begin{cases} е (\bar{{Икс}_{К}}), & Y + 1 знак равно 0 \\ г (\bar{{Икс}_{К}}, Y, час (\bar{{Икс}_{К}}, Y)), & Y + 1 > 0 \end{cases}

$h : \mathbb{N}^{k+1} \rightarrow \mathbb{N} : \\ (\bar{x_k}, y + 1) \mapsto \begin{cases} f(\bar{x_k}), & y + 1 = 0 \\ g (\bar{x_k}, y, h(\bar{x_k}, y)), & y + 1 > 0 \end{cases}$

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

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

(Не) к счастью, кто-то по имени Аккерман пришел и определил следующую функцию:

$Ack : \mathbb{N}^2 \rightarrow \mathbb{N}$
$Ack(0, y) = y+1$
$Ack(x+1, 0) = Ack(x, 1)$
$Ack(x+1, y+1) = Ack(x, Ack(x+1,y))$

Эта функция вычислима, но нет способа построить ее, используя только конструкции выше! (т.е. не является примитивно-рекурсивным) Это означает, что Гедель и его отряд не смогли охватить все вычислимые функции в их построении! $Ack$

Геделю пришлось расширить свой класс функций, чтобы можно было построить . Он сделал это, определив следующее: $Ack$

Неограниченная минимизация

$g : \mathbb{N}^k \rightarrow \mathbb{N}$
ЕСЛИ ТОГДА ELSE не определен. $\left[f(\bar{x_k}, y) = 0 \text{ AND } \\f(\bar{x_k}, z) \text{ is defined } \forall z < y \text{ AND } \\f(\bar{x_k}, z)\neq 0\right]$

$g(\bar{x_k}) = y$

$g(\bar{x_k})$

$g((x_1, x_2, \dots, x_k))$ $f$

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

$Ack$

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

Оберон
источник

4

Я знаю, понимают, что данные определения на самом деле не отвечают на вопрос, но мой ответ описывает эволюцию теории рекурсии / вычислимости. Может стоит прочитать.

Оберон

Мне это нравится, спасибо за ваши усилия :-)

Голо Роден

h ((x_{1}, x_{2}, . . ., x_{k}), 0) = f ((x_{1}, x_{2}, . . ., x_{k}))

$h((x_1, x_2, ..., x_k), 0) = f((x_1, x_2, ..., x_k))$

h ((x_{1}, x_{2}, . . ., x_{k}, 0))

$h((x_1, x_2, ..., x_k, 0))$ , Кроме того, нет условия затем до следующего пункта маркированного списка else.

Эрик Тауэрс

2

μ

$\mu$

1

В вашем ответе немало неверных утверждений. Вы не должны составлять историю для ответа.

Каве

17

Основоположниками теории вычислимости были математики. Они основали то, что сейчас называется теорией вычислимости еще до появления компьютеров. Как математики определяли функции, которые можно было вычислить? По рекурсивным определениям!

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

$\mu$

Название поля используется в теории рекурсии. Однако в последние десятилетия был успешный толчок к изменению названия на что-то более привлекательное от теории рекурсии до чего-то более компьютерного (по сравнению с математикой). В результате область теперь называется теорией вычислимости. Однако если вы посмотрите на книги, статьи, конференции и т. Д. В первые десятилетия, они называются теорией рекурсии, а не теорией вычислимости. Даже название собственной книги Соаре 1987 года (которая была главной фигурой, побудившей сменить название на теорию вычислимости) - «Рекурсивно перечислимые множества и степени».

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

Кава
источник

7

Роберт Соаре написал эссе по этому вопросу. По его словам, термин (общие) рекурсивные функции был придуман Геделем, который определил их с помощью некоторой взаимной рекурсии. Имя застряло, хотя позже были найдены другие эквивалентные определения.

Для получения дополнительной информации я рекомендую сочинение Соаре.

Юваль Фильмус
источник

0

вместо длинного комментария решил добавить ответ:

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

Этот вид итеративной или инкрементной процедуры создает четко определенные функции (в математическом смысле)

В этом смысл рекурсивности на математическом языке. Ниже показано, как это относится к рекурсии на языке программирования.

Сравните эту процедуру с методами и методами, такими как (математическая) индукция, которая также является примером рекурсивности в математике.

Программирование имеет как математическую, так и инженерную направленность.

Это (конструктивная обычно работают на жидком) процедура также refered , как « самозагрузки » в операционных системах жаргоне.

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

Остальное не очень четко определено, и приводит к таким вещам, как переполнение стека :))))

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

начальная загрузка для загрузки низкоуровневых подпрограмм (например, I / O)
сделать необходимые обновления (используя низкоуровневые процедуры)
перезагрузка (фактически, повторный вызов сама), но на этот раз загрузка более сложных подпрограмм (или даже всей системы)

Прекрасный ответ Оберона демонстрирует процедуру такого рода более подробно.

Никос М.
источник

Почему вычислимые функции также называются рекурсивными функциями?

Ответы: