Formal Models and Computation

Instructors                      :       H. Adorna, and N.H.S. Hernandez
e-mail                             :,                                               
Schedule                         :       Thursdays, 18.00H-21.00H / ACLab
Consultation Hours          :       M-F, 16.00 to 18.00 / ACLab, by appointment please
Course Pre-requisites:
    Automata and
    course or COI

Course Requirements:
    Problem Sets (PSet)
    Oral Reports (ORep)

    40% PSet
    60% ORep

must obtained at least 60% in order to gain credit.


1. Maribel Fernández, Models of Computation
An Introduction
to Computability Theory, Springer-Verlag London Limited 2009

John E. Savage, Models of Computation
Exploring the Power of Computing

3. Avi Wigderson,
The "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human Knowledge
[A Public Lecture at IAS, Princeton University]

4. Juraj Hromkovic,
Communication Complexity and Parallel Computing, Springer Verlag, 1997

4. Gheorghe Phaun,
Introduction to Membrane Computing, Springer Verlag, 2000

[This part of the page will grow as we progress our lecture]


Schedule of Lectures:

 Day       Topic(s)

 12. Nov.
 Administrivia (Hi and Hello, GTKY (Getting-to-know-you))
N. Hernandez
 19. NovThe "P vs. NP" Problem: Efficient Computation, Internet Security, and the Limits of Human KnowledgeVideo Public Lecture of Avi Wigderson (IAS) 
  Part 1: Traditional Models
 26. Nov.
 Introduction: Role of Theory in Computer Science (chap 1 of [1] and [2])
 N. Hernandez
 03. Dec
 Automata and Turing Machines
 N. Hernandez
 10. Dec
 Lambda Calculus
 N. Hernandez 
 17. Dec
 Holiday Season Break
 07. Jan
 Recursive Functions
 N. Hernandez 
 14. Jan
 Logic-Based Models
 N. Hernandez 
  Problem Set1 Due : 14 January 2010 [e-mail submission]
 21. Jan
 Oral Report NH/HA
  Part 2: Modern and Unconventional Models
 28. Jan
 no classes
 H. Adorna
 04. Feb
 Communication Protocol Models
 H. Adorna
 11. Feb
 Communication Models in P Systems
 H. Adorna 
 18. Feb
  H. Adorna 
 25. Feb
  H. Adorna 
 04. Mar
  No Lecture : [ACLab to PCSC 2010]
   Problem Set2 Due : 04. March 2010 [e-mail submission]  
 11. Mar
  Oral Report HA/NH