Рекурсивні функції: відмінності між версіями

 

При введенні класа ефективно обчислюваних функцій природнім чином виникає питання уточнення конструктивних об'єктів, на яких визначено ці функції. Клас всіх таких об'єктів обширний та трудно обозримий. В той же час, із допомогою методу [[арифметизація математики|арифметизації]], запропонованого [[австрія|австрійським]] математиком [[Гедель|Геделем К.]], всі такі об'єкти легко зводяться до [[натуральні числа|натуральних чисел]]. Тому рекурсивні функції було введено як функції, визначені на множині натуральних чисел, і приймаючі значення з тієї ж множини натуральних чисел. Перенесення понять і методів вироблених в теорії рекурсивних функцій на функції, визначені на складніших конструктивних областях (множини слів деякого алфавіту, формул деякої теорії, [[граф (математика)|графів]], тощо) не представляє принципових ускладнень.