For every partial combinatory algebra (pca), we define a hierarchy of extensionality relations using ordinals. We investigate the closure ordinals of pcas, i.e. the smallest ordinals where these relations become equal. We show that the closure ordina
l of Kleenes first model is $omega_1^textit{CK}$ and that the closure ordinal of Kleenes second model is $omega_1$. We calculate the exact complexities of the extensionality relations in Kleenes first model, showing that they exhaust the hyperarithmetical hierarchy. We also discuss embeddings of pcas.
Normalized information distance (NID) uses the theoretical notion of Kolmogorov complexity, which for practical purposes is approximated by the length of the compressed version of the file involved, using a real-world compression program. This practi
cal application is called normalized compression distance and it is trivially computable. It is a parameter-free similarity measure based on compression, and is used in pattern recognition, data mining, phylogeny, clustering, and classification. The complexity properties of its theoretical precursor, the NID, have been open. We show that the NID is neither upper semicomputable nor lower semicomputable.
