En matemáticas , específicamente en computabilidad y teoría de conjuntos , se dice que un ordinal es computable o recursivo si existe un buen ordenamiento computable de un subconjunto computable de números naturales que tienen el tipo de orden .
Es fácil comprobar que es computable. El sucesor de un ordinal computable es computable y el conjunto de todos los ordinales computables se cierra hacia abajo.
El supremo de todos los ordinales computables se llama ordinal de Church-Kleene , el primer ordinal no recursivo, y se denota por . El ordinal de Church-Kleene es un ordinal límite . Un ordinal es computable si y sólo si es menor que . Dado que sólo hay un número contable de relaciones computables, también hay sólo un número contable de ordinales computables. Por tanto, es contable.
Los ordinales computables son exactamente los ordinales que tienen notación ordinal en Kleene .
