randomness

Abstract We study the complexity of deterministic and probabilistic inversions of partial computable functions on the reals. Content Overview We regard a Turing functional $f$ as a (possibly partial) map (function) from $2^\omega$ to $2^\omega$, that is, $f(x)$ is the real $y$ such that $y(n)=f^x(n)$ (the output of $f$ with oracle $x$ and input $n$) for all $n$.

Let $U$ be a universal prefix-free Turing machine. Given $X\subset\omega$, let $\Omega[X]=\sum_{U(\sigma)\downarrow\in X}2^{-|\sigma|}$. The following are straight forward observations: $\{\Omega[X]:X\subset\omega\}=[0,\Omega]$. For each $n$ there is a $\Delta^0_{n+1}$ set $X$ such that $A[X]$ is $n$-random.

Abstract One-way functions are the functions that are easy to compute but hard to invert. In terms of oracle Turing machines, we can formalize the notion of computable functions from reals to reals, and define it to be one-way if computable functions almost everywhere fails to invert it.

Abstract A major open problem in computational complexity is the existence of a one-way function, namely a function from strings to strings which is computationally easy to compute but hard to invert.