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 Computer Science 6
 Prerequisites: ? INFO1103 OR INFO1903 OR INFO1113 None COMP2922 (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.

## Unit outlines

Unit outlines will be available 2 weeks before the first day of teaching for the relevant session.