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?

  • $\begingroup$ 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? $\endgroup$
    – D.W.
    Feb 27, 2020 at 19:21
  • $\begingroup$ What's $F$? Is $F$ the same as $P$? Why are they two different variables if they are intended to represent the same mapping? $\endgroup$
    – D.W.
    Feb 27, 2020 at 19:23
  • $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 27, 2020 at 19:24
  • $\begingroup$ 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$. $\endgroup$ Feb 27, 2020 at 19:27
  • 1
    $\begingroup$ 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. $\endgroup$
    – D.W.
    Feb 28, 2020 at 1:06


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.