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.

We are currently working to resolve an issue where some unit outline links are unavailable. If the link to your unit outline does not appear below, please use the link in your Canvas site. If no link is available on your Canvas site, please contact your unit coordinator.

Unit of study_

COMP2022: Models of Computation

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 COMP2022
Academic unit Computer Science
Credit points 6
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 basic discrete mathematics, theorems and formal proofs
  • LO2. demonstrate an understanding of propositional logic
  • LO3. demonstrate an understanding of propositional logic as a model of facts and of reasoning
  • LO4. demonstrate an ability to use languages/tools for propositional logic
  • LO5. demonstrate an understanding of predicate logic
  • LO6. demonstrate an understanding of predicate logic as a model of facts and of reasoning
  • LO7. demonstrate an understanding of a formal language as a set of strings, and of operations on formal languages, in particular union, concatenation, and Kleene closure
  • LO8. demonstrate an ability to use regular languages and their representations by DFAs, NFAs, regular expressions, and regular grammars
  • LO9. demonstrate an ability to use context-free grammars as a model of formal languages
  • LO10. demonstrate an awareness of the Chomsky hierarchy, and the notions of decidability and intractability
  • LO11. 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.