Difference between revisions of "Direct counting"
From Encyclopedia of Mathematics
(cf Immune set) |
m (→References: + ZBL link) |
||
| (One intermediate revision by one other user not shown) | |||
| Line 1: | Line 1: | ||
{{TEX|done}} | {{TEX|done}} | ||
| − | The counting of the elements of a set of natural numbers in order of increasing magnitude. More precisely, a direct counting of a set $A$ of natural numbers is a strictly-increasing function from the natural numbers onto $A$. In the theory of algorithms the important characteristics of a direct counting of a set are recursiveness and rate of growth. E.g., the general recursiveness (primitive recursiveness) of the direct counting of an infinite set is equivalent to the solvability (primitive recursive solvability) of this set. Sets of natural numbers whose direct countings are not majorized by any general recursive function are called | + | The counting of the elements of a set of natural numbers in order of increasing magnitude. More precisely, a direct counting of a set $A$ of natural numbers is a strictly-increasing function from the natural numbers onto $A$. In the theory of algorithms the important characteristics of a direct counting of a set are recursiveness and rate of growth. E.g., the general recursiveness (primitive recursiveness) of the direct counting of an infinite set is equivalent to the solvability (primitive recursive solvability) of this set. Sets of natural numbers whose direct countings are not majorized by any general recursive function are called [[hyperimmune set]]s ; they play an important role in the theory of [[truth-table reducibility]]. |
====References==== | ====References==== | ||
| − | <table><TR><TD valign="top">[1]</TD> <TD valign="top"> V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian)</TD></TR><TR><TD valign="top">[2]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR></table> | + | <table> |
| + | <TR><TD valign="top">[1]</TD> <TD valign="top"> V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian) {{ZBL|0143.25202}}</TD></TR> | ||
| + | <TR><TD valign="top">[2]</TD> <TD valign="top"> H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165</TD></TR> | ||
| + | </table> | ||
Latest revision as of 11:07, 17 March 2023
The counting of the elements of a set of natural numbers in order of increasing magnitude. More precisely, a direct counting of a set $A$ of natural numbers is a strictly-increasing function from the natural numbers onto $A$. In the theory of algorithms the important characteristics of a direct counting of a set are recursiveness and rate of growth. E.g., the general recursiveness (primitive recursiveness) of the direct counting of an infinite set is equivalent to the solvability (primitive recursive solvability) of this set. Sets of natural numbers whose direct countings are not majorized by any general recursive function are called hyperimmune sets ; they play an important role in the theory of truth-table reducibility.
References
| [1] | V.A. Uspenskii, "Leçons sur les fonctions calculables" , Hermann (1966) (Translated from Russian) Zbl 0143.25202 |
| [2] | H. Rogers jr., "Theory of recursive functions and effective computability" , McGraw-Hill (1967) pp. 164–165 |
How to Cite This Entry:
Direct counting. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Direct_counting&oldid=34504
Direct counting. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Direct_counting&oldid=34504
This article was adapted from an original article by S.N. Artemov (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article