Cтраница 2
Этот выбор определения может показаться неожиданным, потому что слово рекурсивно имеет общий корень с глаголом recur ( возвращаться, повторяться 1), а математическая индукция является нашим методом рассмотрения повторяющихся процессов. Смысл этого выбора-не в том, что черта ( п) может отсутствовать при какой-либо конкретной рекурсии, а в том, что она переносится из самого определения на применения этого определения. Чтобы показать финитными средствами, что данная схема наделена чертой ( i), за исключением тривиальных случаев, приходится так или иначе пользоваться математической индукцией. Но определение совокупности обще-рекурсивных функций предшествует попытке охарактеризовать заранее, в какой форме проявится содержательный принцип индукции. Из теоремы Геделя, § 42, мы знаем, что попытка дать такую характеристику посредством формальной арифметической системы оказывается неполной. [16]