Рекурсивні функції: відмінності між версіями
| [неперевірена версія] | [неперевірена версія] |
Вилучено вміст Додано вміст
м робот вилучив: pt:Recursividade (strongly connected to uk:Рекурсія), is:Endurkvæmt fall (strongly connected to uk:Рекурсія) |
IvanBot (обговорення | внесок) м replaced: В зв'язку з → У зв'язку з |
||
Рядок 1:
'''Рекурсивні функції''' — клас функцій, введений як уточнення класу обчислюваних функцій. В математиці загальноприйнятою є теза про те, що клас функцій, для обчислення яких існують [[алгоритм]]и, при найширшому розумінні алгоритму, збігається з класом рекурсивних функцій.
При введенні класу ефективно обчислюваних функцій природнім чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів широкий. В той же час, з допомогою методу [[арифметизація математики|арифметизації]], запропонованого [[австрія|австрійським]] математиком [[Гедель|Куртом Геделем]], всі такі об'єкти легко зводяться до [[натуральні числа|натуральних чисел]]. Тому рекурсивні функції було введено як функції, що визначені на множині натуральних чисел і набувають значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, [[граф (математика)|графів]], тощо) не створює принципових ускладнень.
Рядок 15:
=== Операція суперпозиції ===
Кажуть, що функція <math>g(x_1, \dots, x_m)</math> виникає із функцій <math>f(x_1, \dots, x_n)</math>, <math>f_1(x_1, \dots, x_m)</math>,
:<math>\ g(x_1, \dots, x_m) = f \Big( f_1(x_1, \dots, x_m), \dots, f_n(x_1, \dots, x_m)\Big)</math>
Рядок 27:
{{main|Операція мінімізації}}
Позначимо через <math>\mu y(f(x_1, \dots, x_{n-1}, y) = x_n)</math> найменше значення <math>\alpha</math>, для якого <math>f(x_1, \dots, x_{n-1}, \alpha) = x_n</math>. Будемо вважати, що <math>\mu y(f(x_1, \dots, x_{n-1}, y) = x_n)</math> не визначено, якщо:
# значення <math>f(x_1, \dots, x_{n-1}, \alpha)</math> визначено для всіх <math>y < \alpha</math>, але відмінні від <math>x_n</math>, а значення <math>f(x_1, \dots, x_{n-1}, \alpha)</math> не визначено (
# значення <math>f(x_1, \dots, x_{n-1}, \alpha)</math> визначені для всіх
Таким чином, значення <math>\mu y(f(x_1, \dots, x_{n-1}, y) = x_n)</math> є функцією <math>g(x_1, \dots, x_n)</math> від змінних <math>x_1, \dots, x_n</math>. Кажуть, що ця функція отримана від функції <math>f(x_1, \dots, x_{n-1}, y)</math> із допомогою ''мінімізації''.
Рядок 48:
Доведено, також, що будь-яка частково рекурсивна функція може бути представлена у вигляді:
: <math>g(x_1, \dots, x_s) = \phi (\mu z(f(x_1, \dots, x_s, z) = 0))</math>,
Де <math>\phi</math> і <math>f</math> — примітивно рекурсивні функції, тобто, для отримання будь-якої частково рекурсивної функції оператор
Робились спроби класифікації рекурсивних функцій. Класифікацію примітивно рекурсивних функцій здійснив польський математик А. Гжегорчик, а класифікацію, основану на понятті [[звідність|звідності]] (в [[теорія алгоритмів|теорії алгоритмів]]), виконав американський математик [[Пост Еміль|Е. Пост]].
Рядок 61:
\end{cases}
</math></center>
де
Доведено, що всі одномісні примітивно рекурсивні функції, і лише вони можуть бути отримані із функцій <math>s(x)</math>, <math>g(x)</math> скінченною кількістю операцій додавання, суперпозиції та ітерації.
| |||