On Cantor space, a partial computable real function that is easy to compute but hard to invert even probabilistically is called a one-way real function; such functions exist by work of Barmpalias–Zhang and Gács answering a question of Levin, but all known examples are many-to-one. The source paper (Barmpalias, Wang, Zhang, 2024/2025) constructs an injective partial computable function that is one-way only in the weaker left-oneway sense of Gács, where hardness is measured over the domain, and explicitly leaves open whether an injective partial computable function can be one-way in Levin's range-side sense. The question remains open (see [1, 4]): does there exist an injective partial computable ff on the reals mapping a positive-measure set of inputs to Martin-Löf random outputs such that no partial computable procedure, even granted free random bits, inverts ff on a positive-measure set of its outputs?

Background

Work in Cantor space 2ω2^\omega of infinite binary sequences with the uniform (Lebesgue) measure μ\mu, writing x⊕rx\oplus r for the interleaving of two sequences. A real is Martin-Löf random (ML-random) if it avoids every effectively presented null GδG_\delta cover; ML\mathsf{ML} denotes the class of such reals. A partial computable function f:⊆2ω→2ωf:\subseteq 2^\omega\to 2^\omega is given by a Turing machine that maps finite strings to finite strings monotonically: on input xx it outputs longer and longer prefixes of f(x)f(x), and its domain (where the output length tends to infinity) is always a Π20\Pi^0_2 class; such ff is continuous on its domain. This is the standard framework of computable analysis.

Problem Statement

Does there exist an injective partial computable function f:⊆2ω→2ωf:\subseteq 2^\omega\to 2^\omega such that: (i) μ(f−1(ML))>0\mu(f^{-1}(\mathsf{ML}))>0, i.e. ff maps a positive-measure set of reals to Martin-Löf random reals (Levin's randomness condition, equation (5) of the source paper, which by the paper's implication (6) entails both positive domain measure and positive range measure, and hence the right-oneway range condition); and (ii) for every partial computable g:⊆2ω→2ωg:\subseteq 2^\omega\to 2^\omega,

μ({y⊕r: f(g(y⊕r))=y})=0,\mu\big(\{y\oplus r:\ f(g(y\oplus r))=y\}\big)=0,

that is, no partial computable procedure, even equipped with an independent random sequence rr as side information, inverts ff on a positive-measure set of its outputs? Equivalently, in the terminology of the source paper: an injective partial computable function that is oneway (Levin), hence by the paper's implication (6) also right-oneway. The same question with (i) weakened to μ(f(2ω))>0\mu(f(2^\omega))>0 also remains open in the literature and is noted here as context; it is not part of the question. Any such ff must be partial, since every total computable injection on 2ω2^\omega has a total computable inversion.

References

  1. George Barmpalias, Mingyang Wang, Xiaoyan Zhang. Complexity of inversion of functions on the reals. arXiv:2412.07592, DOI 10.48550/arxiv.2412.07592; published as Mathematical Structures in Computer Science 35 (2025), article e26, DOI 10.1017/S0960129525100224. https://arxiv.org/abs/2412.07592
  2. George Barmpalias, Xiaoyan Zhang. Computable one-way functions on the reals. arXiv:2406.15817, DOI 10.48550/arxiv.2406.15817; published in Information and Computation 306 (2025), article 105327, DOI 10.1016/j.ic.2025.105327. https://arxiv.org/abs/2406.15817
  3. George Barmpalias, Xiaoyan Zhang. Collision-resistant hash-shuffles on the reals. arXiv:2501.02604, DOI 10.48550/arxiv.2501.02604; published in Information and Computation 309 (2026), article 105426, DOI 10.1016/j.ic.2026.105426. https://arxiv.org/abs/2501.02604
  4. George Barmpalias, Su Gao, Jialiang He, Takayuki Kihara, Andre Nies, David Schrittesser, Theodore Slaman, Chieu-Minh Tran, Daniel Turetsky, Philip Welch, Liang Yu, Hang Zhang. Open Problems in Mathematical Logic. arXiv:2608.26628. https://arxiv.org/abs/2608.26628
  5. Leonid A. Levin. The Tale of One-Way Functions. arXiv:cs/0012023; published in Problems of Information Transmission 39 (2003), no. 1, 92–103, DOI 10.1023/A:1023634616182. https://arxiv.org/abs/cs/0012023
  6. Peter Gács. A (partially) computable map over infinite sequences can be 'one-way'. Circulated draft, May 8, 2024.