Skip to main content

During 2021 we will continue to support students who need to study remotely due to the ongoing impacts of COVID-19 and travel restrictions. Make sure you check the location code when selecting a unit outline or choosing your units of study in Sydney Student. Find out more about what these codes mean. Both remote and on-campus locations have the same learning activities and assessments, however teaching staff may vary. More information about face-to-face teaching and assessment arrangements for each unit will be provided on Canvas.

Unit of study_

COMP2922: Models of Computation (Adv)

This unit provides an introduction to the foundations of computing. The main aims are to introduce and compare different models of computation based on state-machines, grammars and algebra, and logic.

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 the relevant session.