Kleene's T predicate

Content sourced from Wikipedia, licensed under CC BY-SA 3.0.

Kleene’s T predicate: a simple guide

In computability theory, Kleene’s T predicate is a precise way to talk about whether a computer program halts on a given input. It uses a fixed way of naming all computable functions (a Gödel numbering) so we can refer to a program just by numbers.

What T and U mean
- T(e, i, x) is true if x encodes a complete run of the program with index e on input i, and this run ends with the program halting.
- If T(e, i, x) is true, the related U(x) gives the output the program would produce on input i.
- T is designed to describe one-input functions first (T1). There are also T2, T3, and so on for functions with more inputs (Tk).

Why Tk are important
- Each Tk is primitive recursive, meaning there is a fixed, simple algorithm that can decide whether Tk(e, i, x) is true for any given e, i, x.
- Because Tk is primitive recursive, any arithmetic theory that can handle all primitive recursive functions can also represent T and U. This includes basic systems like Robinson arithmetic and stronger systems like Peano arithmetic.

Kleene’s normal form theorem
- There is a fixed primitive recursive function U such that any computable function f of k inputs can be described in a standard form using U and a number e that encodes the computation.
- In practical terms, every computable function can be written in a normal form where a least-number operator (μ) is used in a single, well-structured place. This shows a uniform way to express all computable functions.

Why this matters: complete sets and the arithmetical hierarchy
- The T predicates can be used to generate complete sets in the arithmetical hierarchy. In particular, the set that matches the halting problem has the complexity class Σ1⁰ complete, and similar results hold for higher levels.
- More generally, if you have a Σn⁰-complete set, you can obtain a Πn+1⁰-complete set from it. This is part of a broader picture known as Post’s theorem.

In short
- T and its siblings Tk provide a precise, uniform way to talk about when programs halt and what they output.
- They are primitive recursive and can be used to express all computable functions in a standard form.
- They also reveal how different levels of computability relate to each other in the arithmetical hierarchy.