Skip to main content Accessibility help
×
  1. Home
  2. Search

Refine search

Refine search

Access:
Content type:
Publication date:
Apply   From and To filters
Subject: Show more
Journals Show more
Publishers: Show more
Societies Show more
Series: Show more
Collections: Show more

Actions for selected content:

Select all | Deselect all
  • View selected items
  • Export citations
  • Download PDF (zip)
  • Save to Kindle
  • Save to Dropbox
  • Save to Google Drive

Save Search

You can save your searches here and later view and run them again in "My saved searches".

Please provide a title, maximum of 40 characters.
Cancel
×

2 results

  • CHARACTERISING SJT REDUCIBILITY

  • Part of
  • NOAM GREENBERG, ANDRÉ NIES, DANIEL TURETSKY
  • Journal:
    The Journal of Symbolic Logic , First View
    Published online by Cambridge University Press:
    24 June 2026, pp. 1-23
    • Article
      • You have access
    • PDF
    • HTML
    • Export citation

  • SJT reducibility between sets $A,B \subseteq \mathbb N$ is defined by $A \le _{SJT} B$ if for each computable function h that is unbounded and nondecreasing, there is an h-bounded uniformly B-c.e. trace $(T_n)_{n \in \mathbb N} $ such that for each n, the value $J^A(n)$ of the jump is in $T_n$, if defined. This reducibility is slightly weaker than Turing reducibility. We study SJT reducibility, and as a main result give several characterisations of it on the K-trivial sets. This is the first case of extending the three lowness paradigms, weak as an oracle, computed by many, and inert, to the setting of weak reducibilities.

  • CHARACTERIZING LOWNESS FOR DEMUTH RANDOMNESS

  • LAURENT BIENVENU, ROD DOWNEY, NOAM GREENBERG, ANDRÉ NIES, DAN TURETSKY
  • Journal:
    The Journal of Symbolic Logic / Volume 79 / Issue 2 / June 2014
    Published online by Cambridge University Press:
    25 June 2014, pp. 526-560
    Print publication:
    June 2014
    • Article
      • You have access
    • PDF
    • Export citation

  • We show the existence of noncomputable oracles which are low for Demuth randomness, answering a question in [15] (also Problem 5.5.19 in [34]). We fully characterize lowness for Demuth randomness using an appropriate notion of traceability. Central to this characterization is a partial relativization of Demuth randomness, which may be more natural than the fully relativized version. We also show that an oracle is low for weak Demuth randomness if and only if it is computable.