Computability theory 2026/27, Lecture 4: Partial recursive functions

Primitive recursive functions. Partial recursive functions. Theorem: partial recursive functions coincide with computable partial functions. Proof that every partial recursive function is computable. Encoding pairs and sequences as natural numbers. Proof that every computable partial function is partial recursive.