История изменений
Исправление Norgat, (текущая версия) :
Разве что только аксиоматически, придумав виртуальную машину, которая эту функцию может выполнять.
http://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)#.D0.A7...
И, если мне не изменяет память, то машина Тьюринга может вычислять программы только представимые ч.р.ф. и наоборот. А для ч.р.ф. там куча всего напридумана и доказана уже.
P.S. В догонку о формальной системе: http://ru.wikipedia.org/wiki/Теорема_Гёделя_о_неполноте
Исходная версия Norgat, :
Разве что только аксиоматически, придумав виртуальную машину, которая эту функцию может выполнять.
http://ru.wikipedia.org/wiki/Рекурсивная_функция_(теория_вычислимости)#.D0.A7...
И, если мне не изменяет память, то машина Тьюринга может вычислять программы только представимые ч.р.ф. и наоборот. А для ч.р.ф. там куча всего напридумана и доказана уже.