O'Reilly logo

Recursion Theory by Liang Yu, Chi Tat Chong

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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 ...

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required