3 Admissibility and constructibility

This chapter introduces the basic notions of effective computability from the set- theoretic perspective. While somewhat abstract at first sight, they are natural when viewed from the standpoint of definability.

An admissible structure is essentially an inner model of computation. The constructible universe L is defined via a transfinite iteration of the Gödel operators. By considering an appropriate initial segment of L which forms an admissible structure, we will see how a image-set assumes the role of an r.e. set in higher recursion theory.

3.1 Kripke–Platek set theory

The Kripke–Platek (KP) theory of sets was ...

Get Recursion Theory now with the O’Reilly learning platform.

O’Reilly members experience live online training, plus books, videos, and digital content from nearly 200 publishers.