Research Group Theory of Computability over Algebraic Structures

Contact Information

PD Dr. Christine Gaßner

Institut für Mathematik und Informatik

Walther-Rathenau-Straße 47

17489 Greifswald

Phone  +49 3834 420 4610

Telefax + 49 3834 86-4640




The Theory of Computability over Algebraic Structures is essentially a branch of mathematical logic which is related to theoretical computer science. It deals with different models of computation, where operations of algebraic structures are permitted, and includes generalizations of the classic recursion theory.   



Colloquium (07 November 2016, 4.00 pm)

Rupert Hölzl (München): Absolutely undecidable sets (Slides)



Colloquium Logicum 2016 (September 2016)

Christine Gaßner: BSS RAM's with ν-Oracle and the Axiom of Choice


Colloquium on Hiddensee (09 August 2016, 1.00 pm)

André Nies (Auckland): Zufälligkeit und Quantenberechnung


Working meeting (08 - 12  August 2016)

The meeting "Computability and the BSS-Model" took place in Kloster on the island Hiddensee. 


Research Areas

  • Computability over Algebraic Structures
  • Classification of algebraic problems according to their degree of undecidability
  • Bounds of Complexity and P-NP-problems
  • The BSS-RAM model and Moschovakis operators (definitions)

See also (in german):

  • T. Zerjatke: Möglichkeiten und Grenzen des DNA-Computings im Hinblick auf PSPACE (Diplomarbeit)

Topics for Bachelor, Master and PhD thesis

If you are interested in writing a thesis in any of the following topics, please contact: gassnerc(at)uni-greifswald(dot)de.

Main Topics:

  • The power of models of computation between finite automata and BSS-RAM's over algebraic structures. This topic was proposed at a working meeting 2014. The aim is to collect application examples and to compare different types of automata as well as to prove the power of individual types of automata and the insolubility of problems by certain automata. 
  • Classification of currently avaliable  models of computation
  • The significance of the axioms of choice 
    • in Theory of Computability
    • in Graph Theory