Models of Computation

Course at the University of Novi Sad, March 3—12, 2026

Lecturer

Clemens Grabmayer

Visit credits

Heartfelt thanks to our hosts:
- Jovanka Pantović (Chair for Mathematics, Department of fundamental disciplines, University of Novi Sad)
- Silvia Ghilezan (Head of Mathematics Department, Mathematical Institute SASA, Novi Sad)
- Ivan Prokić (University of Novi Sad)
Our visit is financed by the DESK (Developing Shared Knowledge), a European Union project, under the auspices of the Italian Ministery for Universities and Research.

Framework

This lecture took place in the framework of the General Seminar of the Center for Mathematics and Statistics of the Faculty of Technical Sciences of the University of Novi Sad.

Course page (link) at the Center for Mathematics and Statistics at the Faculty of Technical Sciences at the University of Novi Sad.

Room

Room NTP 317 in the new building of the Faculty of Fundamental Disciplines, University of Novi Sad.

Lecture times

17.00—19.00 daily (except Saturday and Sunday) Tuesday, March 3 — Thursday, March 12, 2026.
Please note: this slot will be shared with the course:
- Emilio Tuosto (with guest lecture by Dragiža Zunić): Formal methods for Communication Protocols (in robotics, e-finance, etc.) (link).

Overview at a glance

Overview Table of the Lecture Models of Computation at a Glance

Course Aims

The course aims at familiarizing attendees with basic concepts of computability theory and with several and diverse models of computation. Following the historical development, three classical models will be presented first:

Turing machines,
recursive functions,
Lambda Calculus.

Subsequently, more recent models in computer science and other fields like science and biology will be mentioned. The focus will be on understanding underlying intuitions rather than on exhaustively formal presentations. Specific attention will be directed to:

the comparison of the computational power of different models by finding, whenever possible, simulations between them, modulo reasonable encodings.

By recognizing that some quite disparate models are computationally equally powerful, we will survey some of the ample empirical evidence that computability is a fundamental concept, the Church-Turing Thesis: every informally computable function is Turing-computable (and equivalently, is definable in Lambda Calculus), modulo reasonable encodings.

Lectures

Introduction and Overview (Tuesday, 03/03/2026)
- Slides [handout version (pdf), with overlays (pdf)]
Post and Turing machines, Turings analysis of computability (Wednesday, 04/03/2026)
- Slides [with overlays (pdf)]
Busy Beavers, and Basic recursion theory (Thursday, 05/03/2026)
- Slides [handout version (pdf), with overlays (pdf)]
Basic recursion theory (continued), and Recursive functions (Friday, 06/03/2026)
- Slides [handout version (pdf), with overlays (pdf)]
Lambda Calculus (Monday, 09/03/2026)
- Slides [handout version (pdf), with overlays (pdf)]
- Handout From partial recursive functions to λ-definable functions (pdf)
Three More Models (Thursday, 12/03/2026)
- Slides [handout version (pdf), with overlays (pdf)]

Book

Maribel Fernández: Models of Computation (An Introduction to Computability Theory), Springer-Verlag London, 2009.

Links to Further Resources

Böhm's full precision calculator and Recursive Real Analysis (RRA):
- Popular science article by Chad Nauseam (link)
Post machines, and Post's computability `working hypothesis':
- Emil Leon Post: "Finite Combinatory Processes — Formulation 1" (pdf via wolframscience), The Journal of Symbolic Logic, Vol. 1, No. 3. (Sep., 1936), pp. 103-105.
Turing, and Turing machines:
- Alan M. Turing: "On Computable Numbers, with an Application to the Entscheidungsproblem" (pdf via wolframscience), Proceedings of the London Mathematical Society, 1936.
  - General interest (recent report): Wartime codebreaker Alan Turing’s scientific papers sell for £465,000 at auction (Guardian article, Tue 17 Jun 2025)
- Mike Davey's Turing Machine ``embodying the classic look and feel of a Turing machine'' (link youtube)
- The LEGO Turing Machine (link youtube)
Turing test (for general interest concerning the question: Can machines think?, but only indirectly related to this course):
- Turing's famous paper, a founding text of Artificial Intelligence:
  - A.M. Turing: "Computing Machinery and Intelligence", Mind: a Quarterly Review of Psychology and Philosophy, volume LIX, N.S., No. 236, October, 1950, [scan (pdf via a link in Slovakia)]
Busy Beavers:
- Scott Aaronson: "Why Philosophers Should Care About Computational Complexity", Talk at the University of Austin, Texas, May 2025 (link youtube).
  - Busy beaver section of his talk: (link youtube).
- Scott Aaronson: "The Busy Beaver Frontier", ACM SIGACT News, Volume 51, Issue 3 p. 32—54 29 September 2020 ( papers page at ACM, pdf via ACM).
Church's Thesis and effective calculability:
- A. Church: "An Unsolvable Problem of Elementary Number Theory" (read pdf at JSTOR)
From partial recursive functions to λ-definable functions:
- Handout (pdf).
Comparing computational power of models of computation
- Handout (pdf).
- Udi Boker, and Nachum Dershowitz: "Comparing Computational Power", Logic Journal of the IGPL (pdf report-version via arXiv ).
- Jörg Endrullis, Clemens Grabmayer, and Dimitri Hendriks: "Regularity-Preserving but not Reflecting Encodings", Proceedings of LICS 2015 (pdf, pdf report via arXiv).
Post's Correspondence Problem:
- Emil Leon Post: "A Variant of a Recursively Unsolvable Problem", Bulletin of the American Mathematical Society, 1946 (pdf via projectEuclid).
Interaction Nets:
- Yves Lafont: "Interaction Nets", Proceedings of POPL'90, 1990 (pdf via ACM).
- Lambdascope:
  - Vincent van Ostrom, Kees-Jan van de Looij, Marijn Zwitserlood: "Lambdascope" (pdf via van Oostrom's publication page),
  - Jan Rochel: "graph-rewriting-lambdascope", Lambdascope animation tool, available (link) on Haskell Hackage.
Fractran:
- John Horton Conway:
  - "FRACTRAN: A Simple Universal Programming Language for Arithmetic" (page for download first 2 pages of article).
  - "Fractran: A Ridiculous Logical Language" (link talk video at UCTV).
  - Obituary John Horton Conway, a `Magical Genius', Dies at 82 (link New York Times).

Clemens Grabmayer / www: https://clegra.github.io / mailto: c one dot a one dot grabmayer one at gmail one dot com / Last modified: Sun 15 Mar 2026 19:42 CET /