Skip to main content
Unit of study_

COMP2022: Models of Computation

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 COMP2022
Academic unit Computer Science
Credit points 6
INFO1103 OR INFO1903 OR INFO1113
Assumed knowledge:
(MATH1004 OR MATH1904 OR MATH1064 OR MATH1964 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. Design a deterministic (resp. nondeterministic) finite state machine to accept a specified language.
  • LO3. Generate a regular expression to represent a specified language.
  • LO4. Explain why the halting problem has no algorithmic solution.
  • LO5. Design a context-free grammar to represent a specified language.
  • LO6. Convert among equivalently powerful notations for a language, including among DFAs, NFAs, and regular expressions.
  • LO7. Explain the Church-Turing thesis and its significance.
  • LO8. Determine a languageā€™s place in the Chomsky hierarchy (e.g., regular, context-free, Turing recognisable)
  • LO9. Define the classes P and NP.
  • LO10. Provide examples of uncomputable functions.
  • LO11. Prove that a problem is uncomputable by reducing a classic known uncomputable problem to it.
  • LO12. Convert logical statements from informal language to propositional and predicate logic expressions.
  • LO13. Apply formal methods of symbolic propositional and predicate logic, such as calculating validity of formulae and computing normal forms.
  • LO14. Use the rules of inference to construct proofs in propositional and predicate logic.
  • LO15. Describe how symbolic logic can be used to model real-life situations or applications, e.g., arising in computing contexts such as software analysis (e.g., program correctness), database queries, or algorithms.
  • LO16. Describe the strengths and limitations of propositional and predicate logic.