" 0 C F G H K L N P S T W Z А Б В Г Д Е Ж З И Й К Л М Н О П Р С Т У Ф Х Ц Ч Ш Э Ю Я

НУМЕРИЧЕСКИ ВЫРАЗИМЫЙ ПРЕДИКАТ

Значение НУМЕРИЧЕСКИ ВЫРАЗИМЫЙ ПРЕДИКАТ в математической энциклопедии:

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

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

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

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

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

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