Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part IV, Tome 20 (1971), pp. 200-207
Citer cet article
A. O. Slisenko. A property of recursively enumerable sets containing “hardly deducible” formulas. Zapiski Nauchnykh Seminarov POMI, Studies in constructive mathematics and mathematical logic. Part IV, Tome 20 (1971), pp. 200-207. http://geodesic.mathdoc.fr/item/ZNSL_1971_20_a18/
@article{ZNSL_1971_20_a18,
author = {A. O. Slisenko},
title = {A~property of recursively enumerable sets containing {\textquotedblleft}hardly deducible{\textquotedblright} formulas},
journal = {Zapiski Nauchnykh Seminarov POMI},
pages = {200--207},
year = {1971},
volume = {20},
language = {ru},
url = {http://geodesic.mathdoc.fr/item/ZNSL_1971_20_a18/}
}
TY - JOUR
AU - A. O. Slisenko
TI - A property of recursively enumerable sets containing “hardly deducible” formulas
JO - Zapiski Nauchnykh Seminarov POMI
PY - 1971
SP - 200
EP - 207
VL - 20
UR - http://geodesic.mathdoc.fr/item/ZNSL_1971_20_a18/
LA - ru
ID - ZNSL_1971_20_a18
ER -
%0 Journal Article
%A A. O. Slisenko
%T A property of recursively enumerable sets containing “hardly deducible” formulas
%J Zapiski Nauchnykh Seminarov POMI
%D 1971
%P 200-207
%V 20
%U http://geodesic.mathdoc.fr/item/ZNSL_1971_20_a18/
%G ru
%F ZNSL_1971_20_a18
There are considered recursively enumerable sets of formulas of the predicate calculus with the following property: for any sufficiently large $n$ there exists a formula in such a set, whose complexity of establishing of deducibility is maximal among all deducible formulas having the length $\leq n$. The article contains a low bound for some characteristic of density of such sets.
