Математическая энциклопедия - нумерически выразимый предикат

арифметический предикат обладающий по отношению к данной формальной системе S арифметики следующим свойством: существует такая формула в языке арифметики формальной, что для любых натуральных чисел

1) если истинно, то

2)еслиложно, то где означает выводимость в системе S, а результат подстановки в формулу вместо переменных термов, изображающих числа . В этом случае говорят, что формула нумерически выражает предикат . Для формальной системы Sарифметики имеет место утверждение: в Sнумерически выразимы все рекурсивные предикаты и только они.

n-местная арифметич. функция f наз. нумерически пррдставимой в формальной системе Sарифметики, если существует такая арифметич. формула что для любых натуральных чисел

В обычных формальных системах арифметики нумерически представимы все общекурсивные функции и только они.

Лит.:[1] Клини С. К., Введение в метаматематику, пер. с англ., М., 1957. В. Е. Плиско

Математическая энциклопедия. — М.: Советская энциклопедия

И. М. Виноградов

1977—1985