Complexity of deep computations via topology of function spaces
Preprints · Eduardo Dueñez, José Iovino, Tonatiuh Matos-Wiederhold, Luciano Salvetti, and Franklin D. Tall
A deep computation is a pointwise limit of computations along an ultrafilter, and it need not be the limit of any sequence of computations. When the features are countably many, a set of computations is NIP exactly when, on every bounded region that the computations preserve, its deep computations, extended to the limit states, are of the first Baire class. In that case every deep computation is, on each such region, the limit of a sequence of computations, and each level of the resulting hierarchy is realized by a classical algorithm.