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

1 An introduction to higher recursion theory

1.1 Projective predicates

1.1.1 Recursive and arithmetical predicates

A recursive predicate R on ω is a total recursive function Φ : ω → 2 such that R(n) ⇔ Φ(n) = 1. With a standard coding of ω<ω in ω, one may define recursive predicates on ω<ω. Similarly one may code ωn in ω to obtain recursive n-ary predicates on ω, as well as recursive predicates on (ω<ω)m × ωn. The class of arithmetical predicates on ωω × ω is now defined as follows:

Definition 1.1.1. A predicate R(x, n) on ωω × ω is partial recursive if there is a partial recursive function Φ(σ, n) on ω<ω × ω such that

(i)(∀σ)(∀τ)(∀n)[Φ(σ, n) ↓ ∧ σ τ → (Φ(τ, n) ↓ ∧ Φ(σ, n) = Φ(τ, n))].

(ii)For any xωω and nω, R(x, n) if and only if (∃

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