Department Seminar

Wednesday, 5 November 2025, Aula E

16:30

Christine Gaßner (University of Greifswald)

From High School Algebra to University Algebra

The BSS-RAM model can be used for characterizing uniform algorithms within a mathematical framework. BSS RAMs over first-order structures are the result of a generalization of various types of abstract machines such as BSS machines and Turing machines. On the one hand, universal machines are not necessary for executing arbitrary programs since any machine has its own program. On the other hand, universal BSS RAMs and, in particular, universal non-deterministic BSS RAMs are helpful in defining complete problems for some classes in different hierarchies of decision problems. Here, we will discuss sufficient conditions for their existence. We will consider first-order structures that contain only a finite number of operations and relations, including or excluding the identity relation, and with or without constants.