zum Inhalt springen

Automata Theory: Dynamic Labyrinths

Dynamic Labyrinths are used in the STEM Learning Lab at the University of Cologne as well as in teacher training (e.g. the lecture on computability).

Important theorem from automata theory / theoretical computer science: Dynamic Labyrinths are computationally universal. This means that for every computable function (in principle, given the necessary resources such as time and building materials) a Dynamic Labyrinth can be built to compute this function. Elmar Cohors-Fresenborg, who at the time worked at Dieter Rödding's Chair of "Mathematical Logic and Basic Research" at the University of Münster, has translated this powerful concept from automata theory into "real" building blocks for schools.

 

The mathematical-informatics game world "Dynamic Labyrinths" offers a playful introduction to basic concepts of automation and programming from pre-school age to adulthood.

The following building block types can be used to construct Dynamic Labyrinths:

  • Path building blocks: straight line, intersection, curve (right, left), junction (right, left)
  • Controller elements: flip-flop, switch, counter

Constructions from these building blocks can be used to algorithmically solve sorting problems, periodic counting, addition (see illustration), subtraction, multiplication, or division.

Dynamic Labyrinths are the enactive variant of an automaton-theoretical concept. They belong to the universal calculation concepts such as the Turing machine or register machine.

Ottmann's theorem states that all Mealy automata can be reconstructed with the two building block types switch and junction. In theoretical computer science, dynamic labyrinths are also known as Rödding networks.

With the construction of Dynamic Labyrinths, external representations can be created for solving computational problems, which simplify the problem-solving person's reflection on errors, for example, by supporting their communication with others and making ideas non-verbally expressible. This promotes algorithmic thinking as well as functional-logical thinking in general.