*The
inclusion problem for generalized frequency classes*

** **

**by
Timothy Hugh McNicholl**

Ph.D. dissertation, The George Washington University, 1995, 126 pages.

**Abstract**

A
set of natural numbers is *computable* if there is an algorithm
that,
given a natural number as input, determines whether that number is in
the set. The
existence of sets of natural numbers that are not computable was first
demonstrated by Post in 1922. Since then, several notions of how an
algorithm
can estimate a non-computable set have been proposed. We define a
new notion
that includes most known notions of how an algorithm can estimate a
non-computable set.

A
particular subcase of this notion is *S*-computability defined as
follows.
Let *n* be a natural number, and let *S* be a
collection of sets of
binary *n*-tuples. A set *A* of natural numbers is *S*-computable
if there is an algorithm that, given *n* distinct natural numbers
as input,
computes an element of *S* that includes (*c _{A}*(