Computability (recursion) theory: TOPICS

Computability theory aka Recursion theory computable functions solvability of computable functions

• Aliases

  • Computability theory aka Recursion theory

  • general recursive function aka μ-recursive function

  • computable partial function aka recursive partial function

  • the decision problem aka Entscheidungsproblem

• Opposing pairs

  • solvable vs unsolvable function

  • computable vs noncomputable function

  • total vs partial function

  • recursive vs nonrecursive function

  • primitive recursive vs general recursive function