Theory of Computation

Heinrich Rolletschek

September 8, 2004

The research topics are on the one hand those of classical recursive function theory. Various structural properties of recursively enumerable sets on the one hand, of arbitrary subsets of omega on the other hand and their relationships are investigated. With regard to recursively enumerable sets we deal with

• variants of creativity,
• variants of simplicity,
• reducibility relations.

Here is one problem involving Turing reducibility: if A₀, A₁, ... is a sequence of uniformly recursivly enumerable sets of descending Turing degrees, that is, A₀>_TA₁>_TA₂···, does there necessarily exist a nonrecursive recursively enumerable set A which satisfies A<_TA_i for each i?

Another research topic is the complexity analysis of one special class of algorihms, namely variants of the Euclidean algorithm in quadratic number fields.

---