Advanced Models of Computation

This course concentrates on general-purpose models of computation, incorporating non-classical aspects like concurrency and interaction.

Prerequisite: Models of Computation

Some topics:

  1. Basic models: multidimensional Turing machines; recursive functions; Thue systems (type 0 grammars)
  2. Rewriting models of nondeterminacy, including lambda calculus and combinatory logic
  3. Abstract state machines, including parallelism and interaction
  4. Cellular automata, Petri nets, and other models of concurrency
  5. Quantum computing and other invertible models

Lectures:

  1. Introduction
    1. Outline
    2. History
    3. Vision
  2. Recursive and primitive recursive functions (Chap. 4 in R1); Comparing models
  3. ?
  4. ?
  5. ?
  6. Guest lecture
  7. ?
  8. ?
  9. ?
  10. ?
  11. ?
  12. ?
  13. Conclusion

Selected readings:

  1. Models of Computation: An Introduction to Computability Theory, Maribel Fernández, Springer, 2009
  2. The Expressive Power of Abstract-State Machines, Wolfgang Reisig, Computing and Informatics 22, 2003, 209-219
  3. "Rewrite Systems", Nachum Dershowitz and Jean-Pierre Jouannaud, Handbook of Theoretical Computer Science, vol. B: Formal Methods and Semantics, chap. 6, pp. 243-320, North-Holland, 1990
  4. Cellular Automata: Models for a Discrete World, Joel Schiff, Wiley, 2007 (Chap. 3 online)
  5. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies, Wolfgang Reisig, Springer, 2013