Showing math.LOShow all
3 papers · 1 filter
math.LO2026
Punctually Standard and Nonstandard Models of Natural Numbers
Nikolay Bazhenov, Ivan Georgiev, Dariusz Kalociński +2
Abstract models of computation often treat the successor function on as a primitive operation, even though its low-level implementations correspond to non-trivial…
math.LO2025
Online and feasible presentability: from trees to modal algebras
Nikolay Bazhenov, Dariusz Kalociński, Michał Wrocławski
We investigate whether every computable member of a given class of structures admits a fully primitive recursive (also known as punctual) or fully P-TIME copy. A class with this pr…
math.LO2021
Intrinsic complexity of recursive functions on natural numbers with standard order
Nikolay Bazhenov, Dariusz Kalociński, Michał Wrocławski
Intrinsic complexity of a relation on a given computable structure is captured by the notion of its degree spectrum - the set of Turing degrees of images of the relation in all com…