Восходит к Давиду Гильберту На рубеже 20 века сформулировал мировую проблему

Примитивная рекурсия

• Оператор примитивной рекурсии Rn позволяет определить (n+1) - местную функцию f по двум заданным функциям, одна из которых является n- местной функцией g, а другая (n+2) - местной функцией h.
• Функция f(x1, x2, ..., xn, y) получается оператором примитивной рекурсии из функции g(x1, x2, ..., xn) и функции h(x1, x2, ..., xn, y, z), по схеме:
• f(x1, x2, ..., xn, 0) = g(x1, x2, ..., xn);
• f(x1, x2, ..., xn, y+1) = h(x1, x2, ..., xn, y, f(x1, x2, ..., xn, y)).
• Независимо от числа переменных в f рекурсия ведется только по одной переменной у. Остальные n переменных x1, x2, ..., xn на момент применения схемы зафиксированы и играют роль параметров.

• Тезис Чёрча — Тьюринга и алгоритмически неразрешимые проблемы

• Алан Тьюринг высказал предположение (известное как Тезис Чёрча — Тьюринга), что любой алгоритм в интуитивном смысле этого слова может быть представлен эквивалентной машиной Тьюринга. Уточнение представления о вычислимости на основе понятия машины Тьюринга (и других эквивалентных ей понятий) открыло возможности для строгого доказательства алгоритмической неразрешимости различных массовых проблем (то есть проблем о нахождении единого метода решения некоторого класса задач, условия которых могут варьироваться в известных пределах). Простейшим примером алгоритмически неразрешимой массовой проблемы является так называемая проблема применимости алгоритма (называемая также проблемой остановки). Она состоит в следующем: требуется найти общий метод, который позволял бы для произвольной машины Тьюринга (заданной посредством своей программы) и произвольного начального состояния ленты этой машины определить, завершится ли работа машины за конечное число шагов, или же будет продолжаться неограниченно долго.