20240226_140856
Research

Challenging computability

Cooperating faculty member Dusko Pavlovic published a book in 2023 in Springer’s Theory and Applications of Computability series:

Programs as diagrams: From Categorical Computability to Computable Categories

In 2024, Bjørn Kjos-Hanssen‘s book

Automatic Complexity: A computable measure of irregularity

was published by De Gruyter.

The books challenge computability theory in different yet similar ways:

  • Programs as diagrams argues that Turing machines can be replaced by category-theoretical diagrams for a more natural understanding of computability.
  • Automatic complexity advocates replacing Turing machines by finite automata in the definition of Kolmogorov complexity, thus obtaining a computable notion that is “visual” in an analogous way to Pavlovic’s diagrams.