# One-way-function based on Friedberg numberings

A one-way-function is an easy to compute function $$y=f(x)$$ which is hard to invert. In 2000 Levin 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 Friedberg 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. If we invert the friedberg enumberings $$F^{-1}(y) = x_F$$ we have established a compiler for Friedberg 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?

• I still don't understand. You're using $x_p$ for both the program and the input to the program. That's pretty confusing. Can you avoid using the same variable for two different purposes, please? – D.W. Feb 27 '20 at 19:21
• What's $F$? Is $F$ the same as $P$? Why are they two different variables if they are intended to represent the same mapping? – D.W. Feb 27 '20 at 19:23
• I suggest you explain more clearly how you will construct the compiler. The ability to find $F^{-1}$ for a single $F$ does not imply that you have an effective algorithm to do this for all programs. – D.W. Feb 27 '20 at 19:24
• There ist no input to the program (lets make the input the empty string) It's just the programm. $F$ and $P$ are the respective engines which execute programs in their languages and deliver $y$. – Harald Thomson Feb 27 '20 at 19:27
• But you wrote notation that shows an input, where you wrote $y=P(x_p)$. I can't understand what you are getting at, so I'm afraid I can't help with this. Sorry! Hopefully someone else will be able to help you out. – D.W. Feb 28 '20 at 1:06