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

There will be an exam on January 28.

Some topics:

1. Basic models: (multidimensional) Turing machines; recursive functions [Thue systems (type 0 grammars)]
2. Rewriting models of nondeterminacy, including lambda calculus, combinatory logic, and typed systems
   
3. Abstract state machines, including effectiveness, parallelism, and interaction
4. Cellular automata, Petri nets, and membrane systems, as models of concurrency
5. Analog computation
   
6. [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)
   1. Notes on Effective Representations
9. Typed Models (Ref. #10, Ref. #11)
   1. Old Notes
10. Normalization
1. On Multisets
   
11. Petri Nets (Ref. #6)
1. Interactive examples
2. Verification (Stefan Schwoon)
   
12. Cellular Models (Ref. #13; Ref . #12)
    1. Orit's presentation
    2. PSU course
    3. Dynamic automata
13. Analog Models

Selected readings:

1. Models of Computation: An Introduction to Computability Theory, Maribel Fernández, Springer, 2009
2. Programming Languages and Lambda Calculi, Matthias Felleisen 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, Bull. Symbolic Logic, 2008
   
10. "Lambda Calculus with Types", Henk Barendregt, in Perspectives in Logic, Cambridge University Press, 2013
    
11. Proofs and Types, Jean-Yves Girard
12. "Causal Graph Dynamics", Pablo Arrighi and Gilles Dowek, Inf. Comput., 2013
13. Cellular Automata, Jarkko Kari
14. A New Kind of Science, Stephen Wolfram