Paperlane

no. 17 · Wednesday 18 November 2026

Relative computability and definability for nonregular oracles

Yong Liu, Cheng Peng and Mengzhou Sun

math.LO

Abstract

Classically, a set is computable from an oracle if both the set and its complement are computably enumerable (c.e.) relative to that oracle. We construct a countable nonstandard model of true arithmetic with sets A and X such that both A and its complement are c.e. relative to X, yet A is not pointwise Turing reducible to X. The Turing functionals used here are single-valued at every oracle. For regular oracles, we prove that the classical equivalence holds over ISigma_1. Two further phenomena, each known from earlier work, are realized with the same oracle X that witnesses our main separation. Strong and pointwise Turing reducibility differ for this X, and some Delta_1^X set is not X-c.e.

fields
Logic
pdf ↗ page arXiv:2611.22871 ↗