Skip to main content

We are aiming for an incremental return to campus in accordance with guidelines provided by NSW Health and the Australian Government. Until this time, learning activities and assessments will be planned and scheduled for online delivery where possible, and unit-specific details about face-to-face teaching will be provided on Canvas as the opportunities for face-to-face learning become clear.

Unit of study_

COMP2922: Models of Computation (Adv)

This unit provides an introduction to the foundations of computational models, and their connection to programming languages/tools. The unit covers various abstract models for computation including Lambda Calculus, and Logic calculi (e.g. concept of formal proofs in propositional, predicate, and temporal logic). For each abstract model, we introduce programming languages/tools that are built on the introduced abstract computational models. We will discuss functional languages including Scheme/Haskell, and Prolog/Datalog.

Code COMP2922
Academic unit Computer Science
Credit points 6
Distinction level result in INFO1103 OR INFO1903 OR INFO1113
Assumed knowledge:
(MATH1004 OR MATH1904 OR MATH1064 OR MATH2069 OR MATH2969) AND (INFO1105 OR INFO1905 OR COMP2123 OR COMP2823)

At the completion of this unit, you should be able to:

  • LO1. demonstrate a knowledge of discrete mathematics, mathematical theorems and proofs
  • LO2. hold an understanding of propositional logic, including syntax, semantics, proof systems, and some basic meta-theorems
  • LO3. demonstrate an ability to use languages/tools for propositional logic
  • LO4. hold an understanding of predicate logic, including syntax, semantics, proof systems, and some basic meta-theorems
  • LO5. hold an understanding of the concept of propositional and first order logic as a model of facts and of reasoning
  • LO6. hold an understanding of the concept of a formal language as a set of strings, and of operations on formal languages, in particular union, concatenation, and Kleene closure
  • LO7. demonstrate an ability to use regular languages and their representations by DFAs, NFAs, regular expressions, and regular grammars
  • LO8. demonstrate an ability to use context-free grammars as a model of formal languages
  • LO9. demonstrate an awareness of the Chomsky hierarchy, and the notions of decidability and intractability
  • LO10. demonstrate an awareness of universal models of computation, e.g., Turing machines, the lambda calculus and its application to functional programming

Unit outlines

Unit outlines will be available 2 weeks before the first day of teaching for 1000-level and 5000-level units, or one week before the first day of teaching for all other units.

There are no unit outlines available online for previous years.