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(x₁),…, c_A(x_n)), where c_A is the characteristic function of A.  The main result of this dissertation is a description of the set of all (S, S΄) such that every S-computable set is S΄-computable.  The description is sufficient to show that there is an algorithm that, given a pair (S, S΄) as input, determines whether the pair is an element of this set.