2.1 Partial computable functions on the reals

A Turing machine with an infinite oracle tape and an infinite one-way output tape can be regarded as an effective map $f$ on the reals: given $x\in \{0,1\}^{\omega }$ on its oracle tape, the machine runs indefinitely, and if the cells of the output tape contain the digits of $y$ , we write $y=f(x)$ . This is the standard concept of computability on the reals from computable analysis Pour-El and Richards (Reference Pour-El and Richards1989); Weihrauch (Reference Weihrauch1993).

Let $f:\subseteq \{0,1\}^\omega \to \{0,1\}^\omega$ denote a function from a nonempty subset of $\{0,1\}^\omega$ to $\{0,1\}^\omega$ . Let $\mathsf{dom}(\,f)$ be the domain and $f(\{0,1\}^\omega )$ be the range of $f$ .

We write $f(x)\downarrow$ if $x\in \mathsf{dom}(\,f)$ and $f(x)\uparrow$ otherwise. We say that $f$ is partially computable if there is an oracle Turing functional $\Phi$ such that

\begin{equation*} \big (\,f(x)\downarrow \iff \forall n,\ \Phi ^x(n)\downarrow \big )\ \land \ \big (\,f(x)\downarrow \implies \forall n, \Phi ^x(n)=f(x)(n)\big ). \end{equation*}

If $\Phi$ has access to an additional oracle $w$ , we say that $f$ is partial $w$ -computable and write $f\leq _T w$ . Every $w$ -computable function is continuous. Every continuous function with $G_\delta$ domain is $w$ -computable for some oracle $w$ .

A representation is a partial computable $\hat {f}:\subseteq \{0,1\}^{\lt \omega }\to \{0,1\}^{\lt \omega }$ with

\begin{equation*} \big ({\sigma \prec \tau \ \wedge \ \hat {f}(\tau )\downarrow }\big )\ \implies \ \big ({\hat {f}(\sigma )\downarrow \ \wedge \ \hat {f}(\sigma )\preceq \hat {f}(\tau )}\big ) \end{equation*}

and is a representation of $f:\subseteq \{0,1\}^\omega \to \{0,1\}^\omega$ if for all $x$ and

\begin{equation*} \forall n,\ \hat {f}(x\upharpoonright _n)\prec f(x) \hspace {0.3cm}\textrm {and}\hspace {0.3cm} f(x)\downarrow \iff \lim _n|\hat {f}(x\upharpoonright _n)|=\infty . \end{equation*}

A function $f$ is $w$ -computable if it has a $w$ -computable representation.

2.2 Complexity of domain and range

If $f$ is partially computable, its domain is effectively $G_{\delta }$ , namely a $\Pi ^0_2$ class. The converse also holds, so the domain of a partial computable $f$ might not be closed.

Proof. Let $\hat {f}$ be a partial computable representation of $f$ . Since

\begin{equation*}x\in \mathsf{dom}(\,f)\iff \forall n\ \exists m\ \exists s\ |\hat {f}_s(x\upharpoonright _m)\downarrow |\geq n\end{equation*}

we get (i). For (ii) let $(V_{i,j})$ be a computable family of clopen sets with

\begin{equation*} P=\bigcap _i\bigcup _j V_{i,j} \hspace {0.3cm}\textrm {and}\hspace {0.3cm} V_{0,0}=\{0,1\}^\omega , V_{i,j}\subseteq V_{i,j+1}. \end{equation*}

Define the partial computable function $\hat {g}(\sigma )=\hat {f}(\sigma )\upharpoonright _{t_{\sigma }}$ where

\begin{equation*} t_{\sigma }:=\max \{\hspace {0.03cm}{i} : {i\leq |\hat {f}(\sigma )|\ \wedge \ [\![\sigma ]\!]\subseteq V_{i,|\sigma |}}\hspace {0.03cm}\}. \end{equation*}

If $\sigma \prec \tau$ and $\hat {g}(\tau )\downarrow$ then $\hat {f}(\tau )\downarrow$ and $\hat {f}(\sigma )\downarrow \preceq \hat {f}(\tau )$ and

\begin{equation*} [\![\tau ]\!]\subset [\![\sigma ]\!]\ \implies \ t_{\tau }\geq t_{\sigma } \ \implies \ \hat {g}(\sigma )\downarrow \preceq \hat {g}(\tau ) \end{equation*}

so $\hat {g}$ is a representation of a partial computable $g$ . If $x\in \mathsf{dom}(\,f)\cap P$ then

\begin{equation*} \forall i\ \exists k,j,\ [\![ x\upharpoonright _k]\!]\subseteq V_{i,j}. \end{equation*}

If $n\geq k,j$ , $|\hat {f}(x\upharpoonright _n)|\geq i$ by $[\![ x\upharpoonright _n]\!]\subseteq V_{i,n}$ we get $|\hat {g}(x\upharpoonright _n)|\geq i$ . Such $n$ exists for all $i$ so $g(x)\downarrow$ . Since $\forall n,\ \hat {g}(x\upharpoonright _n)\preceq \hat {f}(x\upharpoonright _n)\prec f(x)$ we get $g(x)=f(x)$ .

If $x\notin \mathsf{dom}(\,f)$ then $g(x)\uparrow$ . If $x\notin P$ then

\begin{equation*} \exists i\ \forall j,\ x\notin V_{i,j}\ \implies \ \forall n,\ |\hat {g}(x\upharpoonright _n)|\leq i\ \implies \ g(x)\uparrow . \end{equation*}

So $g$ is the restriction of $f$ to $\mathsf{dom}(\,f)\cap P$ . Finally (iii) follows from (ii).

Continuous functions $f$ on subsets of $\{0,1\}^{\omega }$ map compact sets to compact sets. Since $\{0,1\}^{\omega }$ is a Hausdorff space, the same holds for closed sets. An effective version of this fact is true when $f$ is partially computable.

Recall that if $P\in \Pi ^0_1(w)$ , there is a $w$ -computable tree $\hat {P}$ with $P=[\hat {P}]$ .

Proof. For (i) let $\hat {P}$ be a $w$ -computable tree with $[\hat {P}]=P$ . We show

(1) \begin{equation} y\in f(P)\iff \forall n\ \exists \sigma \in \hat {P}\cap \{0,1\}^n,\ \hat {f}(\sigma )\prec y. \end{equation}

If $y\in f(P)$ then $\exists x\in P,\ f(x)=y$ so $\forall n\ \big ({x\upharpoonright _n\in \hat {P}\cap \{0,1\}^n\ \wedge \ \hat {f}(x\upharpoonright _n)\prec y}\big )$ .

For the converse, suppose that there is $\sigma _0,\sigma _1,\ldots$ with $\sigma _i\in \hat {P}\cap \{0,1\}^i$ and $\hat {f}(\sigma _i)\prec y$ . Since $\{0,1\}^\omega$ is compact, there is a subsequence of $\sigma _i$ (without loss of generality, the sequence $\sigma _i$ itself) that converges to some $x$ . Let $\tau _i$ be the longest common prefix of $\sigma _i$ , $x$ . Since $\sigma _i\to x$ , we get $|\tau _i|\to \infty$ so $\tau _i\to x$ . Also

• • since $\sigma _i\in \hat {P}$ we get $\tau _i\in \hat {P}$ so $x\in [\hat {P}]=P\subseteq \mathsf{dom}(\,f)$ and $f(x)\downarrow$ ,

• • since $\hat {f}(\tau _i)\preceq \hat {f}(\sigma _i)\prec y$ and $\tau _i\to x$ we get $f(x)=y$ .

This completes the proof of (1) so $f(P)\in \Pi ^0_1(w)$ . For (ii) we have

\begin{equation*} x\in f^{-1}(Q)\iff x\in \mathsf{dom}(\,f)\ \land \ \forall n\ \forall i\ \ [\![\hat {f}(x\upharpoonright _n)]\!]\cap Q_i\neq \emptyset \end{equation*}

where each $Q_i$ is clopen, $i\mapsto Q_i$ is $w$ -computable and $Q=\bigcap _i Q_i$ . Then

\begin{equation*} P=\{x:\forall n\ \forall i\ [\![\hat {f}(x\upharpoonright _n)]\!]\cap Q_i\neq \emptyset \} \end{equation*}

is $\Pi ^0_1(w)$ and $f^{-1}(Q)=\mathsf{dom}(\,f)\cap P$ .

Although the domain of any partial computable $f:\subseteq \{0,1\}^\omega \to \{0,1\}^\omega$ is arithmetically definable (indeed $\Pi ^0_2$ ) as a subset of $\{0,1\}^{\omega }$ , it is possible that it is nonempty and has no arithmetically definable member.

Proof. If $x\in \Delta ^1_1$ there is an ordinal $\alpha \lt \omega _1^{\textrm {CK}}$ with $x\lt _T \emptyset ^{(\alpha )}$ . Since $\{\emptyset ^{(\alpha )}\}\in \Pi ^0_2$ by [Chong and Yu (Reference Chong and Yu2015), Theorem 2.1.4], by Proposition 2.1 (iii) we get (i). Let

\begin{equation*} \pi (\alpha ):=0^{1+\alpha (0)} 1 0^{1+\alpha (1)}\ldots 0^{1+\alpha (n)}\ldots \end{equation*}

be a computable injective function from $\omega ^\omega$ into $\{0,1\}^{\omega }$ . By [Chong and Yu (Reference Chong and Yu2015), Proposition 2.5.2] there is a computable tree $T\subseteq \omega ^{\omega }$ such that $[T]$ is uncountable and $[T]\cap \Delta ^1_1=\emptyset$ . Every $x\in \pi ([T])$ computes a member of $[T]$ so $\pi ([T])\cap \Delta ^1_1=\emptyset$ .

Since $\pi ([T])\in \Pi ^0_2$ we get (ii) by Proposition 2.1 (iii).

So a partially computable $f:\subseteq \{0,1\}^\omega \to \{0,1\}^\omega$ may have a non-empty domain such that all arithmetically definable closed subsets (represented as the set of infinite paths through an arithmetically definable tree) of it are empty.

By Proposition 2.2 (i) the range of any total computable $f:\{0,1\}^{\omega }\to \{0,1\}^{\omega }$ is $\Pi ^0_1$ . However, the range of a partial computable $f$ is only $\Sigma ^1_1$ . Recall ([Chong and Yu (Reference Chong and Yu2015),Definition 1.1.6]) that a class $Q\subseteq \{0,1\}^{\omega }$ is $\Sigma ^1_1$ if for each $y$ :

\begin{equation*} y\in Q\iff \exists \alpha \in \omega ^\omega \ \forall s,\ P(\alpha , y, s) \end{equation*}

where $P\subseteq \omega ^\omega \times \{0,1\}^{\omega }\times \omega$ is a total computable predicate.

Proof. Clause (i) is straightforward. For (ii), we fix an effective injection from $\omega ^\omega$ to $\{0,1\}^\omega$ , for example, $\pi (\alpha ):=0^{1+\alpha (0)} 1 0^{1+\alpha (1)}\ldots 0^{1+\alpha (n)}\ldots$ .

For any $Q\in \Sigma ^1_1$ , let $P\subseteq \omega ^\omega \times \{0,1\}^{\omega }\times \omega$ be a total computable predicate with

\begin{equation*}y\in Q\iff \exists \alpha \in \omega ^\omega \ \forall s,\ P(\alpha ,y,s).\end{equation*}

Let $f$ be such that

\begin{equation*} f(x\oplus y)=\begin{cases} y & x=\pi (\alpha )\text{ for some }\alpha \ \land \ \forall s,\ P(\alpha ,y,s) \\ \uparrow & \text{otherwise} \end{cases} \end{equation*}

Then $f$ is partial computable and $f(\{0,1\}^{\omega })=Q$ .

When $f$ has positive domain it has an effective restriction with $\Pi ^0_1(\emptyset ')$ range.

By Proposition 2.5, the complexity bound in Proposition 2.4 can be reduced by considering partial computable restrictions of $f$ .

2.3 Complexity of inversion

For $f, g:\subseteq \{0,1\}^{\omega }\to \{0,1\}^{\omega }$ we say that $g$ is an inversion of $f$ if

\begin{equation*} \forall y\in f(\{0,1\}^{\omega }),\ f(g(y))=y. \end{equation*}

By [Barmpalias and Zhang (Reference Barmpalias and Zhang2025), Corollary 3.2] every total computable injective $f$ has a total computable inversion. We are particularly interested in functions that preserve randomness.

By [Miller and Yu (Reference Miller and Yu2008), Theorem 4.3], if $x$ is $w$ -random and $y\leq _T x$ is random, then $y$ is $w$ -random. So partially computable random-preserving functions preserve $w$ -randomness for all  $w$ .

Proof. Let $(z'_s)$ be the universal enumeration of the jump $z'$ of $z$ and set

\begin{align*} p^z(\langle n,s\rangle )\ &:=\ \begin{cases} \ \ 2n & \textrm {if} n\in z'_{s+1}-z'_s \\ 2\langle n,s\rangle +1 & \text{otherwise} \end{cases} \\ h^z(x)(\langle n,s\rangle )\ &:=\ x(p^z(\langle n,s\rangle )) \end{align*}

By the relativization of [Barmpalias and Zhang (Reference Barmpalias and Zhang2025), Theorem 4.5]:

1. (i) $h^z$ is a $z$ -computable $z$ -random preserving total surjection

2. (ii) if $w$ computes an inversion of $h^z$ then $w\geq _T z'$ .

Since $z\mapsto h^z$ is effective, by [Barmpalias and Zhang (Reference Barmpalias and Zhang2025), Lemma 5.5], the map

\begin{equation*} f(x\oplus z):=h^z(x)\oplus z \end{equation*}

is a total computable random-preserving surjection. For contradiction, assume that $g$ is a continuous inversion of $f$ . Since $f$ is total, $g$ has $G_\delta$ domain and therefore must be $w$ -computable for some $w$ . Now

\begin{equation*} \forall y,z:\ f(g(y\oplus z))=y\oplus z. \end{equation*}

Let $g^z(y)$ be the even bits of $g(y\oplus z)$ , so $g^z$ is an inversion of $h^z$ and

\begin{equation*} g^z\leq _T z\oplus w \hspace {0.3cm}\textrm {and}\hspace {0.3cm} \forall z,\ z'\leq _T z\oplus w \end{equation*}

by (ii). In particular, $w'\leq _T w\oplus w$ which is a contradiction.

Partial inversions of effective maps on the reals are more tractable.

By [Barmpalias and Zhang (Reference Barmpalias and Zhang2025), Theorem 4.5], there is a total computable random-preserving surjection $f$ such that every oracle that computes a probabilistic inversion of $f$ computes ${\text {0}}'$ . We show that this complexity bound is optimal.

Proof. Clearly $f^{-1}(y)\in \Pi ^0_1(y)$ uniformly in $y$ : $\{\hspace {0.03cm}{x\oplus y} : {x\in f^{-1}(y)}\hspace {0.03cm}\}\in \Pi ^0_1$ .

So there exists a Turing functional $\Phi$ such that

\begin{equation*} \forall y\in f(\{0,1\}^{\omega }):\ \Phi (y')\in f^{-1}(y). \end{equation*}

By [Downey and Hirschfeldt (Reference Downey and Hirschfeldt2010), Theorem 8.14.5], we have $y'\leq _T y\oplus \emptyset '$ for almost every $y$ . Since $f(\{0,1\}^{\omega })$ is positive, by countable additivity there exists a Turing functional $\Psi$ with

\begin{equation*} \mu (L)\gt 0\,\textrm {where}\,L:=\{{y\in f(\{0,1\}^{\omega })} : {\Psi (y\oplus \emptyset ')=y'}. \end{equation*}

Let $g(y)=\Phi (\Psi (y\oplus \emptyset '))$ so $g\leq _T {\text {0}}'$ and $g$ inverts $f$ on

\begin{equation*} \{\hspace {0.03cm}{y\in f(\{0,1\}^{\omega })} : {g(y)\in f^{-1}(y)}\hspace {0.03cm}\}=\{\hspace {0.03cm}{y} : {f(g(y))=y}\hspace {0.03cm}\}\supseteq L. \end{equation*}

Since $\mu (L)\gt 0$ this is a positive subset of $f(\{0,1\}^{\omega })$ .

We can now characterize the complexity of positive and probabilistic inversions of total computable functions $f:\{0,1\}^{\omega }\to \{0,1\}^{\omega }$ with positive range.

It is not hard to show that ${\text {0}}'$ does not compute a positive inversion of some partial computable $f:\{0,1\}^{\omega }\to \{0,1\}^{\omega }$ with positive range. We show that a mild condition on $f$ oracle ${\text {0}}''$ is sufficient for this purpose. The condition is that $f$ maps to random reals with positive probability, which is weaker than randomness-preservation and present in Levin’s one-way functions Barmpalias and Zhang (Reference Barmpalias and Zhang2025).

Proof. By Proposition 2.5 (ii), we may assume that $\mathsf{dom}(\,f)\in \Pi ^0_1(\emptyset ')$ . Then

(2) \begin{equation} \{\hspace {0.03cm}{x\oplus y} : {x\in f^{-1}(y)}\hspace {0.03cm}\}\in \Pi ^0_1(\emptyset ') \end{equation}

so $f^{-1}(y)\in \Pi ^0_1(y\oplus \emptyset ')$ uniformly in $y$ and for some Turing functional $\Phi$ :

\begin{equation*} \forall y\in f(\{0,1\}^{\omega }):\ \Phi ((y\oplus \emptyset ')')\in f^{-1}(y). \end{equation*}

By [Downey and Hirschfeldt (Reference Downey and Hirschfeldt2010), Theorem 8.14.5] for almost all $y$ we have $(y\oplus \emptyset ')'\equiv _T y''\equiv _T y\oplus \emptyset ''$ .

Since $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ , there exists a 2-random $x$ such that $f(x)$ is random. By [Miller and Yu (Reference Miller and Yu2008), Theorem 4.3] and $f(x)\leq _T x$ , we get that $f(x)$ is a 2-random.

Since $f(\{0,1\}^{\omega })\in \Pi ^0_1(\emptyset ')$ , we have $\mu (\,f(\{0,1\}^{\omega }))\gt 0$ , and by countable additivity, there exists a Turing functional $\Psi$ with $\mu (L)\gt 0$ where

\begin{equation*} L:=\{\hspace {0.03cm}{y\in f(\{0,1\}^{\omega })} : {\Psi (y\oplus \emptyset '')=(y\oplus \emptyset ')'}\hspace {0.03cm}\}. \end{equation*}

Let $g(y)=\Phi (\Psi (y\oplus \emptyset ''))$ so $g\leq _T {\text {0}}''$ and $g$ inverts $f$ on

\begin{equation*} \{\hspace {0.03cm}{y\in f(\{0,1\}^{\omega })} : {g(y)\in f^{-1}(y)}\hspace {0.03cm}\}=\{\hspace {0.03cm}{y} : {f(g(y))=y}\hspace {0.03cm}\}\supseteq L. \end{equation*}

Since $\mu (L)\gt 0$ , this is a positive subset of $f(\{0,1\}^{\omega })$ .

3.1 Inversion without random oracles

The simplest example of a nowhere effectively invertible partial computable function is the projection $f:\ x\oplus z\mapsto x$ restricted to a positive $\Pi ^0_1$ class $P$ of randoms. However, $f$ is a.e. probabilistically invertible in the sense that

(4) \begin{equation} \mu (\{\hspace {0.03cm}{y\oplus r} : {f(g(y\oplus r))=y}\hspace {0.03cm}\})=\mu (\,f(\{0,1\}^\omega ))\gt 0 \end{equation}

for some partial computable $g$ .

Proof. Let $f$ be the restriction of $x\oplus z\mapsto x$ to a positive $\Pi ^0_1$ class $P$ of randoms. Then $f$ is partially computable, random-preserving, and

\begin{equation*} x\oplus z\in P\ \implies \ x\oplus z\not \leq _T x \end{equation*}

by van Lambalgen’s theorem, so $f$ is nowhere effectively invertible. By Fubini’s theorem (4) holds for $g(y\oplus r):=y\oplus r$ so (ii) holds.

We turn to examples with null (and nonempty) domain or range.

Proof. By Proposition 2.3 (i) $\{\emptyset ^{(\omega )}\}\in \Pi ^0_2$ so by Proposition 2.1 (ii)

\begin{equation*} f:\emptyset ^{(\omega )}\mapsto 0^\omega \hspace {0.3cm}\textrm {is partial computable.} \end{equation*}

Any $g$ that inverts $f$ on $y=0^\omega$ defines $\emptyset ^{(\omega )}$ , which is not arithmetical.

By Proposition 2.3 (ii), let $P$ be an uncountable $\Pi ^0_2$ class with no $\Delta ^1_1$ members. The restriction of $x\mapsto 0^{\omega }$ to $P$ meets the requirements of (ii).

A nowhere effectively invertible partial computable $f:\subseteq \{0,1\}^{\omega }\to \{0,1\}^{\omega }$ with

\begin{equation*} \textrm {positive} \,\mathsf{dom}(\,f)\subseteq \mathsf{ML} \, \, \, \textrm {and}\, \, \, f(\{0,1\}^{\omega })\cap \mathsf{ML}=\emptyset \end{equation*}

can be given by Kurtz (Reference Kurtz1981) (see [Downey and Hirschfeldt (Reference Downey and Hirschfeldt2010), Theorem 8.21.3]), who constructed $f$ with the above properties and every real in its range is 1-generic. Since 1-generics do not compute randoms [Downey and Hirschfeldt (Reference Downey and Hirschfeldt2010), Theorem 8.20.5], $f$ is nowhere effectively invertible.

We end with the symmetric case of null domain and positive range.

Proof. Let $Q\neq \emptyset$ be a positive $\Pi ^0_2$ class of 2-randoms and

\begin{align*} f(x\oplus z):\simeq \begin{cases} z & \textrm {if} x=\emptyset ' \textrm {and} z\in Q\\ \uparrow &\textrm {otherwise.} \end{cases} \end{align*}

Since $x=\emptyset '$ is $\Pi ^0_2$ by Proposition 2.1 (ii), $f$ is partially computable. By the choice of $Q$ we get (ii). Since 2-randoms do not compute $\emptyset '$ we get (i).

3.2 Inversion with random oracles

In computational complexity one-way functions are effectively calculable finite maps that cannot be effectively inverted with positive probability. Levin (Reference Levin2023) defined one-way functions $f:\subseteq \{0,1\}^{\omega }\to \{0,1\}^{\omega }$ to be partially computable with

(5) \begin{equation} \mu (\,f^{-1}(\mathsf{ML}))\gt 0 \hspace {0.3cm}\textrm {and}\hspace {0.3cm} \mu (\{\hspace {0.03cm}{y\oplus r} : {f(g(y\oplus r))=y}\hspace {0.03cm}\})=0 \end{equation}

for each partial computable $g$ . A total computable one-way function was constructed in Barmpalias and Zhang (Reference Barmpalias and Zhang2025). Gács (May 8, 2024) constructed a partial computable $f$ with

\begin{equation*} \mu (\mathsf{dom}(\,f))\gt 0 \hspace {0.3cm}\textrm {and}\hspace {0.3cm} \mu \big ({\{\hspace {0.03cm}{x\oplus r} : {f(g(\,f(x)\oplus r))=f(x)}\hspace {0.03cm}\}}\big )=0 \end{equation*}

for each partial computable $g$ . This differs from (5) in that probability refers to the domain rather than the range of $f$ . Another difference is condition $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ which is weaker than randomness preservation but stronger than $\mu (\mathsf{dom}(\,f))\gt 0$ . This suggests two variants of probabilistic inversion.

Definition 3.4. Let $f:\subseteq \{0,1\}^\omega \to \{0,1\}^\omega$ be partially computable. If

\begin{equation*} \mu (\mathsf{dom}(\,f))\gt 0 \hspace {0.3cm}\textrm {and}\hspace {0.3cm} \mu \big ({\{\hspace {0.03cm}{x\oplus r} : {f(g(\,f(x)\oplus r))=f(x)}\hspace {0.03cm}\}}\big )=0. \end{equation*}

For each partial computable $g$ , we say that $f$ is left-oneway. If

\begin{equation*} \mu (\,f(\{0,1\}^\omega ))\gt 0 \hspace {0.3cm}\textrm {and}\hspace {0.3cm} \mu (\{y\oplus r:f(g(y\oplus r))=y\})=0 \end{equation*}

for each partial computable $g$ , we say that $f$ is right-oneway.

Given the absence of $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ in the above definition, note that

(6) \begin{equation} \mu (\,f^{-1}(\mathsf{ML}))\gt 0\underset {\not \Leftarrow }{\Rightarrow } \big ({\mu (\mathsf{dom}(\,f))\gt 0\ \wedge \ \mu (\,f(\{0,1\}^\omega ))\gt 0}\big ). \end{equation}

The first implication is trivial, and by Proposition 2.5, we may assume that the domain and range of $f$ are $\Pi ^0_1(\emptyset ')$ . Since $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ there is a 2-random $x$ such that $f(x)$ is random. By [Miller and Yu (Reference Miller and Yu2008), Theorem 4.3], we get that $f(x)$ is a 2-random member of $f(\{0,1\}^\omega )$ which is $\Pi ^0_1(\emptyset ')$ so $\mu (\,f(\{0,1\}^\omega ))\gt 0$ .

The failure of the converse in (6) is demonstrated later in Theorem 3.8.

Before we separate the classes of left and right one-way functions, we show that $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ is equivalent (up to restrictions) to randomness-preservation.

Proof. Suppose that $f$ extends a random-preserving partial computable $h$ . Then $h$ has a positive domain $P$ , and by Proposition 2.5, we may assume that $P$ consists of randoms. Since $h$ is random-preserving, $h^{-1}(\mathsf{ML})=P$ so

\begin{equation*} \mu (\,f^{-1}(\mathsf{ML}))\geq \mu (h^{-1}(\mathsf{ML})) =\mu (P) \gt 0. \end{equation*}

For the converse, assume that $\mu (\,f^{-1}(\mathsf{ML}))\gt 0$ , so there is

• • $Q\in \Pi ^0_1$ of randoms with $\mu (\,f^{-1}(Q))\gt 0$

• • $P\in \Pi ^0_1$ of randoms with $\mu (P\cap f^{-1}(Q))\gt 0$ .

Let $g$ be the restriction $f$ to $P\cap f^{-1}(Q)$ . By Proposition 2.2 (ii), the class $P\cap f^{-1}(Q)$ is $\Pi ^0_2$ so $g$ is partially computable by Proposition 2.1 (ii). Since $P\cap f^{-1}(Q)$ is positive and $P, Q$ consist of randoms, $g$ is random-preserving.

Assuming randomness-preservation right-oneway implies left-oneway.

Proof. Suppose that $f$ is random-preserving so it has positive domain.

If $f$ is not left-oneway, there is a partial computable function $g$ with

\begin{equation*} \mu (L)\gt 0 \hspace {0.3cm}\textrm {where}\hspace {0.3cm} L:=\{x\oplus r:f(g(\,f(x)\oplus r))=f(x)\} \end{equation*}

To show that $f$ is not right-oneway, it suffices to show that

\begin{equation*} \mu (R)\gt 0 \hspace {0.3cm}\textrm {where}\hspace {0.3cm} R:=\{y\oplus r:f(g(y\oplus r))=y\}. \end{equation*}

Since $\mu (L)\gt 0$ , there is a $2$ -random $x\oplus r\in L$ . By van Lambalgen’s theorem, $x$ is $r\oplus \emptyset '$ random. Since $f$ is random-preserving, $f(x)$ is random, and since $f(x)\leq _T x$ by [Miller and Yu (Reference Miller and Yu2008), Theorem 4.3], it is also $r\oplus \emptyset '$ -random. By van Lambalgen’s theorem, $f(x)\oplus r$ is a $2$ -random member of the $\Pi ^0_2$ class $R$ so $\mu (R)\gt 0$ .

The converse is not true, even for total computable random-preserving $f$ .

Proof. Let $f$ be a random-preserving partial computable one-way function, which exists by [Barmpalias and Zhang (Reference Barmpalias and Zhang2025), Theorem 4.4]. Let $\bar {f}$ be defined by

\begin{align*} \bar {f}(x)=\begin{cases} 0f(z) & \text{ if } x=0z \text{ for some }z \\ 1z & \text{ if } x=1(0^\omega \oplus z) \text{ for some }z \\ \ \uparrow & \text{ otherwise} \end{cases} \end{align*}

then $\bar {f}$ is random-preserving since $f$ is. The partial computable function

\begin{equation*}1z\mapsto 1(0^\omega \oplus z)\end{equation*}

inverts $\bar {f}$ on all $y\in [\![ 1]\!]$ , so $\bar {f}$ is not one-way or right-oneway.

On the other hand, any partial computable $\bar {g}$ such that

\begin{equation*}\mu (\{x:\bar {f}(\, \bar {g}(\, \bar {f}(x)\oplus r)=\bar {f}(x)\})\gt 0\end{equation*}

induces a partial computable $g$ such that

\begin{equation*}\mu (\{x:f(\, g(\, f(x)\oplus r))=f(x)\})\gt 0\end{equation*}

which is impossible since $f$ is left-oneway. Therefore, $\bar {f}$ is left-oneway.

We show that Theorem 3.6 fails if we do not require randomness preservation. We say that a real $x$ is incomplete if $\emptyset '\not \leq _T x$ .

Proof. Let $P=\bigcap _s P_s$ be the $\Pi ^0_1$ class of $\mathsf{PA}$ reals where $P_s$ is clopen and $s\mapsto P_s$ is computable. Define the total computable surjection $f:\{0,1\}^{\omega }\to \{0,1\}^{\omega }$ by

\begin{align*} f(x\oplus z)=\begin{cases} \ \ z&\textrm {if}\, x \in P \\ z\upharpoonright _n \ 0^{\omega }&\textrm {if}\, n=\min \{\hspace {0.03cm}{s} : {x\not \in P_s}\hspace {0.03cm}\}. \end{cases} \end{align*}

If $x\oplus z$ is random, $x\not \in P$ so $f(x\oplus z)$ is computable. So $f(\mathsf{ML})\cap \mathsf{ML}=\emptyset$ .

Almost all reals $y\in f(\{0,1\}^{\omega })$ are incomplete randoms. For each random $y$ , every $w\in f^{-1}(y)$ computes a $\mathsf{PA}$ real. So for almost all $r$ and $y\in f(\{0,1\}^{\omega })$ :

• • $y\oplus r$ is an incomplete random

• • each real in $f^{-1}(y)$ computes a $\mathsf{PA}$ real.

By Stephan (Reference Stephan2006) incomplete randoms do not compute $\mathsf{PA}$ reals so

\begin{equation*} \mu (\{\hspace {0.03cm}{r} : {r\oplus y \, \textrm {computes a member of}\, f^{-1}(y)}\hspace {0.03cm}\})=0 \end{equation*}

for almost all $y\in f(\{0,1\}^{\omega })$ . This shows that $f$ is right-oneway. Since

\begin{equation*} x\not \in P\implies f(x\oplus z)\ \text{ends with}\ 0^{\omega } \end{equation*}

the set $f((\{0,1\}^\omega -P)\times \{0,1\}^{\omega })$ is countable. Since $\mu (P)=0$ by countable additivity, there is $y$ with $\mu (\,f^{-1}(y))\gt 0$ . For this $y$ , we have

\begin{equation*} \mu (\{v\oplus r:\, f(v)=f(r)=y\})=\mu (\,f^{-1}(y))^2\gt 0 \end{equation*}

so for the function $g(w,r):=r$ we get

\begin{equation*} \mu \left (\{v\oplus r:\, f(g(\,f(v)\oplus r))=f(v)\}\right )\gt 0. \end{equation*}

Since $g$ is computable, this shows that $f$ is not left-oneway.

4.1 Outline of the proof

Our argument is self-contained but follows the standard framework for constructing probabilistic maps; see [Downey and Hirschfeldt (Reference Downey and Hirschfeldt2010), Section 8.21] or Barmpalias et al. (Reference Barmpalias, Day and Lewis-Pye2014); Bienvenu and Patey (Reference Bienvenu and Patey2017).

Let $(\Phi _e)$ be an effective enumeration of all Turing functionals. We construct a partial computable injectiion $f$ with positive domain such that for all $e$ :

\begin{equation*} R_e\text{:}\ \ \mu (\{x:\Phi _e(\,f(x))\downarrow =x\})=0. \end{equation*}

We construct a representation $\hat {f}$ of $f$ in stages. At stage $s$ , the domain of the current approximation $\hat {f}_s$ of $\hat f$ is a finite tree where each node with a successor has two successors. The leaf nodes of $\hat f_s$ are the leaf nodes of its domain.

Satisfying $R_e$ . Suppose that $\hat {f}(\sigma )$ is defined and all $\hat {f}(\sigma \tau ), \tau \neq \lambda$ are undefined. To satisfy $R_e$ in $[\![\sigma ]\!]$ , we need to define $f(x)$ so that for almost all $x\in [\![\sigma ]\!]$

\begin{equation*} \Phi _e(\,f(x))\uparrow \ \ \vee \ \ \ \Phi _e(\,f(x))\neq x. \end{equation*}

Case 1. If $\Phi _e(y)\uparrow$ for all $y\in f([\![\sigma ]\!])$ then $R_e$ is automatically satisfied.

Case 2. If $\Phi _e(y)(|\sigma |)\downarrow =i$ for some $y\in f([\![\sigma ]\!])$ with oracle-use $\rho \prec y$ then

(7) \begin{equation} \big ({\rho \prec f(x)\ \wedge \ x(|\sigma |)\neq i}\big )\ \implies \ \Phi _e(\,f(x))(|\sigma |)=\Phi _e(y)(|\sigma |)\neq x(|\sigma |) \end{equation}

which means that $R_e$ is satisfied for this $x$ . So we

1. (a) satisfy $R_e$ in $[\![\sigma (1-i)]\!]$ by defining $\hat {f}(\sigma (1-i))=\rho$

2. (b) define $\hat {f}(\sigma i)$ arbitrarily and try to satisfy $R_e$ with $\sigma i$ in place of $\sigma$ .

By iterating, we satisfy $R_e$ for almost all $x\in [\![\sigma ]\!]$ .

Non-uniformity. Unfortunately, we cannot effectively distinguish which case is true. We deal with this by creating a branch $\sigma \tau$ above $\sigma$ for each $\tau$ of certain length $l+1$ and assign to them different guesses. Branches $\sigma 00^l$ , $\sigma 10^l$ :

• • believe case 2 and search for $\rho$ as in (7)

• • if $\rho$ is found they define $\hat {f}(\sigma (1-i)0^l)\succ \rho$ satisfying $R_e$ in $[\![\sigma (1-i)0^l]\!]$ .

The $\hat {f}$ -value at $\sigma i0^l$ is defined arbitrarily, and $R_e$ in $[\![\sigma i0^l]\!]$ is considered by the nodes above. If the guess is wrong:

• • the search never stops and $f(x)\uparrow$ for $x\in [\![\sigma 00^l]\!]\cup [\![\sigma 10^l]\!]$

• • $R_e$ is satisfied since $f(x)\uparrow$ and $f$ is undefined in $[\![\sigma 00^l]\!]\cup [\![\sigma 10^l]\!]$ .

In the meantime, the remaining branches above $\sigma$ believe Case 1 and proceed to other requirements. If $\sigma 00^l$ , $\sigma 10^l$ have the wrong guess, there will be a stage where this belief is seen to be wrong. At this point, although $\hat {f}$ will have been defined above the remaining branches out of $\sigma$ , we will extend the latter appropriately and reconsider $R_e$ on these newly added leaves.

Markers. The assignment of requirement $R_e$ to a $[\![\sigma ]\!]$ is done by placing an $e$ -marker on node $\sigma$ as elaborated above. The marker acts if the $\rho$ in (7) is found. At each stage, we keep a record of the status of each requirement on each leaf node: initially $\lambda$ is $e$ -unattended for each $e$ and

• • when $\sigma$ receives an $e$ -marker, $\sigma 00^l$ , $\sigma 10^l$ become $e$ -waiting and the other branches are temporarily $e$ -satisfied

• • when this $e$ -marker acts, the $e$ -waiting branch $\sigma (1-i)0^l$ becomes $e$ -satisfied and the other $e$ -waiting branch along with the temporarily $e$ -satisfied nodes extending $\sigma$ become $e$ -unattended

• • in all other cases the status of the leaf node is the same as its parent.

A node is inactive if it is $e$ -waiting for some $e$ , indicating that no definition of $\hat f$ is permitted above them under this status. We ensure that

\begin{equation*} f(x)\uparrow \iff x\upharpoonright _n \textrm {stays inactive forever for some} n. \end{equation*}

Positive domain. As we elaborated, if an $e$ -marker on $\sigma$ never acts:

• • $f$ becomes undefined on measure $\leq 2^{-l}$ relative to $[\![\sigma ]\!]$

• • no other $e$ -markers are placed above $\sigma$ until the $e$ -marker on $\sigma$ acts

so the set of strings with $e$ -marker that never acts is prefix-free. Thus each $R_e$ can only cause $f$ undefined on measure $\leq 2^{-l}$ . By letting $l=e+k$ for $k:=2$ :

\begin{equation*} \mu (\mathsf{dom}(\,f))\geq 1-\sum _{e}2^{-e-k}=1-2^{1-k}\gt 0. \end{equation*}

Injective. We make $f$ injective by ensuring that at any stage $s$ :

1. (i) for any active leaf nodes $\sigma \ |\ \tau$ we have $\hat {f}_s(\sigma )\ |\ \hat {f}_s(\tau )$ ,

2. (ii) if there is an $e$ -marker on $\sigma$ then $f_{s+1}([\![\sigma ]\!])\subseteq f_s([\![\sigma ]\!])$ where

   \begin{equation*} f_s([\![\sigma ]\!]):= \bigcup \left \{[\![\hat {f}_s(\sigma \tau )]\!]:\sigma \tau \text{ is an active leaf node of }\, \hat {f}_s\right \} \end{equation*}
   so $f([\![\sigma ]\!])\subseteq f_s([\![\sigma ]\!])$ .

To this end, we often extend $\hat {f}_s$ to $\rho$ naturally, which means that we find the unique leaf node $\sigma \prec \rho$ in $\hat {f}_s$ and let $\hat {f}_{s+1}(\sigma \tau )=\hat {f}_s(\sigma ) \tau$ for all $\tau$ such that $\sigma \tau \preceq \rho$ . Note that (i), (ii) are preserved under natural extensions.

4.2 Construction and verification

We divide the stages for the construction to 3 types:

• • initialization stages $3\langle e,t\rangle$ where we put new $e$ -markers on $e$ -unattended nodes and do the initialization from them

• • activation stages $3\langle e,t\rangle +1$ where $e$ -markers requiring action act

• • expansion stages $3t+2$ where we expand $f$ at its active leaf nodes.

Construction. Let $k=2$ , $\hat {f}_0(\lambda )=\lambda$ and $\lambda$ be $e$ -unattended for each $e$ .

Stage $s=3\langle e,t\rangle$ : for each active $e$ -unattended leaf node $\sigma$ :

• • put an $e$ -marker on $\sigma$

• • for $\tau =\sigma 00^{e+k}$ and $\tau =\sigma 10^{e+k}$ set $\hat {f}_{s+1}(\sigma \tau )=\hat {f}_s(\sigma )$ , define $\hat {f}_{s+1}$ on strings between $\sigma$ and $\sigma \tau$ , and set $\sigma \tau$ $e$ -waiting;

• • for all other $\tau$ with $|\tau |=e+k+1$ naturally extend $\hat {f}_s$ to $\sigma \tau$ and set $\sigma \tau$ temporarily $e$ -satisfied.

Stage $s=3\langle e,t\rangle +1$ : for each $e$ -marker on $\sigma$ with $|\sigma |=n$ that has not acted, find $\tau$ with $\hat {f}_s(\sigma \tau )\downarrow =\hat {f}_s(\sigma )\rho$ and $\Phi _e(\rho )(n)[s]\downarrow =i$ . If $\tau$ does not exist proceed to the next stage. Otherwise we may assume that $\sigma \tau$ is a leaf node of $\hat {f}_s$ , since otherwise we can replace $\tau$ with an extension of it on leaf nodes. We then set:

• • $j=1-i$ , $\hat {f}_{s+1}(\sigma j0^{e+k})=\hat {f}_s(\sigma )\rho 00$ and $\sigma j0^{e+k}$ be $e$ -satisfied

• • $\sigma i0^{e+k}$ be $e$ -unattended, $f_{s+1}(\sigma \tau )=f_s(\sigma )\rho 1$ , $\hat {f}_{s+1}(\sigma i0^{e+k})=\hat {f}_s(\sigma )\rho 01$

• • all temporarily $e$ -satisfied leaf nodes of $\hat {f}_s$ extending $\sigma$ be $e$ -unattended

and declare that this $e$ -marker has acted.Footnote ²

Stage $s=3\langle e,t\rangle +2$ : for each active leaf node $\sigma$ naturally extend $\hat {f}_s$ to $\sigma 0,\sigma 1$ . This ensures $f(x)\downarrow$ when $x$ does not have prefixes that stay inactive forever.

Verification. As we discussed in Section 4.1 the domain of $f$ is positive.

By induction on $s$ we get (i), (ii) from Section 4.1.

Proof. Assuming $x\neq y$ , $f(x), f(y)\downarrow$ , we show $f(x)\neq f(y)$ .

Let $\chi _s$ be the unique leaf node of $\hat {f}_s$ with $\chi _s\prec x$ and similarly for $\gamma _s\prec y$ .

Since $x\neq y$ for sufficiently large $s$ , we have $\chi _s\ |\ \gamma _s$ . So if $\chi _s$ and $\gamma _s$ are both active at $s$ by (i), we get $\hat {f}_s(\chi _s)\ |\ \hat {f}_s(\gamma _s)$ so $f(x)\neq f(y)$ . For this reason, we may assume that at most one of $\chi _s$ , $\gamma _s$ is active at sufficiently large $s$ .

Without loss of generality pick $s$ such that $\chi _s$ is active and $\gamma _s$ is inactive.

Since $f(y)\downarrow$ , there exists $t\gt s$ such that

\begin{equation*} \chi _t\succ \chi _s \, \textrm {is inactive and} \, \gamma _t=\gamma _s \, \textrm {is active.} \end{equation*}

Let $\sigma$ be the node with an $e$ -marker that made $\chi _t$ inactive so

• • $\chi _s\preceq \sigma \prec \chi _t$ and $\chi _s\ |\ \gamma _s$ , $\tau \ |\ \gamma _t$ for any leaf node $\tau \succ \sigma$

• • by (i) we have $\hat {f}_t(\tau )\ |\ \hat {f}_t(\gamma _t)$ so $f_t([\![\sigma ]\!])\cap [\![\hat {f}_t(\gamma _t)]\!]=\emptyset$ .

By (ii) we have $f(x)\in f([\![\sigma ]\!])\subset f_t([\![\sigma ]\!])$ and $f(y)\in [\![\hat {f}_t(\gamma _t)]\!]$ , so $f(x)\neq f(y)$ .

It remains to show that if $g=\Phi _e$ for some $e$ then $g$ inverts $f$ on measure $0$ .

For a contradiction assume otherwise so $\mu (L)\gt 0$ where

\begin{equation*} L=\{x:\Phi _e(\,f(x))=x\}. \end{equation*}

By Lebesgue’s density theorem, there is $x_0\in L$ with density $1$ in $L$ . For each $s$ let $\chi _s$ be the unique leaf node of $\hat {f}_s$ with $\chi _s\prec x_0$ . Then:

• • if $\chi _s$ is $e$ -satisfied the $e$ -status of $\chi _t$ remains $e$ -satisfied forever;

• • if $\chi _s$ is $e$ -waiting, since $f(x_0)\downarrow$ there must be $t\gt s$ where $\chi _t=\chi _s$ becomes $e$ -satisfied or $e$ -unattended;

• • if $\chi _s$ is $e$ -unattended there must be $t\gt s$ where an $e$ -marker is put on some $\chi _t$ and $\chi _{t+1}$ is $e$ -waiting or temporarily $e$ -satisfied;

• • if $\chi _s$ is temporarily $e$ -satisfied, the $e$ -status of $\chi _t$ might remain temporarily $e$ -satisfied forever, or might become $e$ -unattended for some $t\gt s$ .

Therefore, there are three cases for the status of $\chi _s$ as $s\to \infty$ .

Case 1. $\chi _s$ is $e$ -satisfied for all sufficiently large $s$ . Then $R_e$ is satisfied on all $x\in \chi _s$ so $R_e$ is satisfied for $x_0$ , contradicting $x_0\in L$ .

Case 2. $\chi _s$ is temporarily $e$ -satisfied for all sufficiently large $s$ . Then the $e$ -marker on some $\sigma \prec \chi _s$ never acts so the corresponding $\tau ,\rho$ are never found and $R_e$ is satisfied in $[\![\sigma ]\!]$ . Since $x_0\in [\![\sigma ]\!]$ this contradicts $x_0\in L$ .

Case 3: the $e$ -status of $\chi _s$ as $s\to \infty$ loops indefinitely through

1. (a) $e$ -unattended

2. (b) $e$ -waiting or temporarily $e$ -satisfied

3. (c) $e$ -unattended

Transition (a) $\to$ (b) is caused by an $e$ -marker on some $\sigma$ which will act when transition (b) $\to$ (c) occurs. Each such action produces a set of relative measure $2^{-e-k-1}$ where $R_e$ is satisfied, so the density of $x_0$ in $L$ is $\leq 1-2^{-e-k-1}$ , contradicting the hypothesis that $x_0$ has density $1$ in $L$ .

We conclude that $\mu (L)=0$ so all requirements are met.