pipette
ENEnglish

Weakly uniform computable categoricity and function composition

Joey Lakerdas-Gayle

Preprint

En palabras de los autores

We introduce the definition of a weakly -uniformly -computably categorical structure, relativizing a definition of Kudinov (1996), and show that this relativized notion is closely related to the 2-dimensional complexity of the pairs of partial functions with the property that the composition simulates convergent -oracle computations. We develop a general theory for computing via composition and use it to prove results about the surprisingly complex weakly uniform categoricity spectrum of the structure where . Namely, that is w..u..c.c. for some and , but is not w..u..c.c. for any and . We also construct a computably categorical structure that is not w..u.c.c., but is w..u.c.c. for a set that is -incomparable with .

Resultado principalEl resumen no menciona limitaciones.

Apareció: martes, 20 de octubre. arXiv. Preprint, todavía sin revisión por pares.

Comentario de los autores: 47 pages