7.2 Частично-рекурсивные функции

Мы познакомились с неформальными определениями алгоритма и вычислимой функции. Но для математического изучения этих понятий вычислимость следует формализовать. В 30-е годы XX века и позже было предложено несколько точных определений понятия алгоритма и вычислимой функции. Опишем подход Гёделя и Клини1, предложенный ими в 1936 г.