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. The Recursive Function Model
    1. Primitive recursion and recursion (Chap. 4 in Ref. #1 or any other source)
    2. Comparing models (Ref. #8)
    3. Representations
  3. The Lambda Calculus Model
    1. Lambda and Beta (Ref. #2)
    2. Recursion Theorem
  4. Rewriting Models
    1. Church-Rosser Theorems (Ref. #3)
    2. HW #1 (due end Nov.)
  5. Abstract State Machines (Ref. #4)
    1. Postulates of Algorithms (Ref. #7)
  6. Parallel Models (Guest lecture: Jenny Falkovich)
  7. Oracular Models
    1. HW #2 (due end Dec.)
  8. Effective Models (Ref. #9)
  9. Typed Models (Ref. #10, Ref. #11)
  10. Cellular Models
  11. Petri Nets (Ref. #6)
  12. Exotic Models
  13. Conclusion

Selected readings:

  1. Models of Computation: An Introduction to Computability Theory, Maribel Fernández, Springer, 2009
  2. Programming Languages and Lambda Calculi, Matthias Fellesisen and Matthew Flatt, 2006
  3. "Rewrite Systems", Nachum Dershowitz and Jean-Pierre Jouannaud, Handbook of Theoretical Computer Science, vol. B: Formal Methods and Semantics, chap. 6, North-Holland, 1990
  4. The Expressive Power of Abstract-State Machines, Wolfgang Reisig, Computing and Informatics, 2003
  5. Cellular Automata: Models for a Discrete World, Joel Schiff, Wiley, 2007 (Chap. 3 online)
  6. Understanding Petri Nets: Modeling Techniques, Analysis Methods, Case Studies, Wolfgang Reisig, Springer, 2013
  7. Sequential Abstract State Machines Capture Sequential Algorithms, Yuri Gurevich, ACM TOCL, 2000
  8. Comparing Computational Power, Nachum Dershowitz & Udi Boker, Logic J. of IGPL, 2006
  9. A Natural Axiomatization of Computability and Proof of Church's Thesis, Nachum Dershowitz & Yuri Gurevich, Bulletin of Symbolic Logic, 2008
  10. Barendregt's Chapter
  11. Girard's Notes