Namespaces
Variants
Actions

Difference between revisions of "Enumeration problem"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex encoded by computer)
 
Line 1: Line 1:
An [[Algorithmic problem|algorithmic problem]] in which one has to construct an algorithm that enumerates <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358201.png" /> for a given set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358202.png" />, i.e. an algorithm <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358203.png" /> that is applicable to any natural number, that converts it to an element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358204.png" /> and such that any element of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358205.png" /> is obtained by applying <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358206.png" /> to some natural number; in other words, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358207.png" />. The enumeration problem for a set <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358208.png" /> is solvable (i.e. such an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e0358209.png" /> exists) if and only if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/e/e035/e035820/e03582010.png" /> is a non-empty [[Enumerable set|enumerable set]].
+
<!--
 +
e0358201.png
 +
$#A+1 = 10 n = 0
 +
$#C+1 = 10 : ~/encyclopedia/old_files/data/E035/E.0305820 Enumeration problem
 +
Automatically converted into TeX, above some diagnostics.
 +
Please remove this comment and the {{TEX|auto}} line below,
 +
if TeX found to be correct.
 +
-->
 +
 
 +
{{TEX|auto}}
 +
{{TEX|done}}
 +
 
 +
An [[Algorithmic problem|algorithmic problem]] in which one has to construct an algorithm that enumerates $  A $
 +
for a given set $  A $,  
 +
i.e. an algorithm $  \mathfrak A $
 +
that is applicable to any natural number, that converts it to an element of $  A $
 +
and such that any element of $  A $
 +
is obtained by applying $  \mathfrak A $
 +
to some natural number; in other words, $  A = \{ {\mathfrak A ( i) } : {i \in \mathbf N } \} $.  
 +
The enumeration problem for a set $  A $
 +
is solvable (i.e. such an $  \mathfrak A $
 +
exists) if and only if $  A $
 +
is a non-empty [[Enumerable set|enumerable set]].

Latest revision as of 19:37, 5 June 2020


An algorithmic problem in which one has to construct an algorithm that enumerates $ A $ for a given set $ A $, i.e. an algorithm $ \mathfrak A $ that is applicable to any natural number, that converts it to an element of $ A $ and such that any element of $ A $ is obtained by applying $ \mathfrak A $ to some natural number; in other words, $ A = \{ {\mathfrak A ( i) } : {i \in \mathbf N } \} $. The enumeration problem for a set $ A $ is solvable (i.e. such an $ \mathfrak A $ exists) if and only if $ A $ is a non-empty enumerable set.

How to Cite This Entry:
Enumeration problem. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Enumeration_problem&oldid=46832
This article was adapted from an original article by V.E. Plisko (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article