# 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*_{0},

*A*_{1},

*...* is a sequence of uniformly
recursivly enumerable sets of descending Turing degrees, that is,

*A*_{0}>_{T}A_{1}>_{T}A_{2}···, does there
necessarily exist a nonrecursive recursively enumerable set

*A* which satisfies

*A<*_{T}A_{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.