Computation Theory Past Paper

• Reference
  • ★ Credit: @Dimitrios Los

Register machines

• y2021p6q5
  • Universal Register Machine, $e \in N = ⌜P = prog(e)⌝$
  • partial / total RM-computable function
• y2007p3q7
• y2005p3q7
  • Halting Problem
• y2003p3q7

Turing Machine

• y2004p3q7
• Turing’s Thesis

Partial recursive functions

• y2022p6q5
• y2006p4q9

Lambda Calculus

Foundations of Functional Programming Past Paper

• y2021p6q6
  • equivalence classes [M], relation $=_{\beta}$
• y2022p6q6
  • Church-Rosser Theorem
• y2009p6q6

General