Weakly uniform computable categoricity and function composition
We introduce the definition of a weakly $X$-uniformly $Y$-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 $(f,g)$ with the property that the composition $g\circ f$ simulates convergent $\emptyset'$-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 $(ω,S)$ where $S(n)=n+1$. Namely, that $(ω,S)$ is…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.24422
curl -X POST /api/v1/records/arxiv/2610.24422/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.24422/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'