One-way-function based on <PERSON> numberings
A one-way-function is an easy to compute function $y=f(x)$ which is hard to invert. In 2000 <PERSON> showed an example of a function which is one-way if there are one-way functions. As far as I know, it is still not clear whether true one way-functions exist.
Now with <PERSON> numbering, which roughly speaking, is a programming language with the following properties:
* turing completeness
* no two programs perform the same task
* every computable function has a corresponding program but there's no way to find it. There is a non-existance proof of a compiler in this language. i.e. one can not programm with friedberg numberings. However, if you have for some reason a program in this language it is executable.
In the following argument has to be a a pretty basic flaw as it would establish the existance of one-way-functions if it would be right.
Suppose we have a regular programm $x_p$ in a "normal" language which computes $y = P(x_p)$. Here $P$ is the function which which maps $x_p \rightarrow y$. Also assume a programm $x_F$ in the language of Friedberg enumberings which for some reason computes $F(x_F) = y$ too. 82
If we invert the <PERSON> enumberings $F^{-1}(y) = x_F$ we have established a compiler for <PERSON> numberings by inverting $F$, as we have established a mapping $x_P \rightarrow x_F$. However, we know there is no such compiler, hence our assumption $F$ is invertible is wrong. This establishes them as one-way-function as Friedberg numbering are perfectly computable, but not invertable.
Possible loopholes:
* It is clear that $F^{-1}$ needs to run forever for any input $y$, as every bijective function has an inverse. However, not every bijective function has necessarily a computable inverse. There might be a mapping, but we can not compute it in finite time. I'm not sure if this changes the argument. The point is if we can invert $F^{-1}$ than we have a compiler, and if we can't than we have a one-way-function. Also $F^{-1}$ might be approximateable.
* $P$ is not necessary halting for all $x_p$. Ok, lets restrict us to all halting $x_p$ (which is impossible to know beforhand)
If this argument would be right it would make Friedberg numbering a bijective one-way-function with the stronger guarantee of beeing impossible to invert instead of just beeing hard to invert.
What is wrong with this argument? 603