Effectively simple sets
1964; American Mathematical Society; Volume: 15; Issue: 6 Linguagem: Inglês
10.1090/s0002-9939-1964-0180485-7
ISSN1088-6826
Autores Tópico(s)semigroups and automata theory
ResumoWe use the word to mean positive integer, and to mean set of positive integers. A set a is called simple (after Post [1 ]) iff a is r.e. (recursively enumerable), infinite, and its complement &x, though infinite, contains no infinite recursively enumerable subset. We shall call a set a effectively simple if a and its complement are infinite, a is r.e., and there exists a recursive function a(x) such that for any number i for which wi is disjoint from a, the number a(i) is greater than the number of elements of oi.2 Informally speaking, this means that any coi disjoint from a is not onlyfinite (which simply says that a is simple), but that we can effectively find a bound for the number of elements of wc. The original simple set S constructed by Post [1] is effectively simple, indeed it is immediate from Post's argument that the function a(x) = 2x+1 has the desired property. As is well known, the set S is not hypersimple. Our present purpose is to prove the existence of an effectively simple set which is also hypersimple. A number i is said to be a deficiency point of a function f(x) if there exists a number j > i such that f(j) <f(i). The set of all deficiency points of f is called the deficiency set of f. Dekker [4 ] has shown that if f is a 1-1 recursive function which enumerates a recursively enumerable but not recursive set, then the deficiency set of f is simple, in fact hypersimple. We show
Referência(s)