<p>You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out.</p>

<p>Here, "at most quadratic" is a little sloppy. It should be read as meaning "at most $|x|^2$ steps", so that there is a concrete time bound to check against. But one should keep in mind that there is a tradeoff between writing that is perfectly rigorous, and writing that can easily be understood by non-specialists, and Wikipedia generally aims for the latter — see <a href="https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable">https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable</a> and its specific guidance to "explain formulae in English".</p>

CC BY-SA 3.0
2016-01-23T13:46:03.193Z
Yes the first paragraph is what I had in mind when I wrote: 'I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$.' 

Your second paragraph makes a LOT of sense - in fact it is not so long ago that I myself would have interpreted at most quadratic as "at most $|x|^2$ step without worrying about any constants. Thanks for clarifying this!
Vincent
CC BY-SA 3.0
2016-01-23T13:47:15.117Z
It seems then however that we are in the situation I described under 'UPDATE' (for $c = 1$) and that Goldreich also uses 'quadratic' in the unusual and stricter sense of 'at most $|x|^2$ steps'. I should stare a bit longer at his argument to verify that it does indeed work with this stronger notion of quadratic.
Vincent
CC BY-SA 3.0
2016-01-22T17:57:55.387Z
2016-01-22T17:57:55.387Z
David Eppstein
<p>(As for the question in the title: the answer must be no, but then I don't understand what is intended.) </p>

<p>The <a href="https://en.wikipedia.org/wiki/One-way_function" rel="nofollow">Wikipedia page</a> on one way functions states:</p>

<blockquote>
  <p>Goldreich gives one construction of a universal one-way function, which is denoted by $f_{univ}$ here.</p>
  
  <p>$f_{univ} (desc(M), x) := (desc(M), M(x))$,
  where $desc(M)$ is the description of Turing machine $M$, and $x$ is an input string. $M(x)$ is defined as the output of machine $M$ given $x$ as input if the running time is at most quadratic on the length of $x$, and otherwise, $M(x) := x$. This definition of $M(x)$ guarantees $f_{univ}$ can be efficiently computed within polynomial time.</p>
</blockquote>

<p>The point of $f_{univ}$ is that whenever there exists one way functions that run in quadratic time, then $f_{univ}$ is a one-way function as well. (And the Goldreich reference proves that whenever one-way functions of any running time exist, they can be used to create one way functions that run in quadratic time, hence obtaining the result that the 'concrete' function $f_{univ}$ is a one way function if and only if one way functions exist at all.)</p>

<p>I am, however, not convinced that the last statement from the quote is obvious.</p>

<p>As I understand it, a computer wanting to compute $M(x)$ needs to do two things:</p>

<p>1) Decide whether or not the running time of machine $M$ given $x$ as input is "at most quadratic on the length of $x$"</p>

<p>2) Either return $x$ or let $M$ run on input $x$ and return the output</p>

<p>Now it is clear that step 2) takes at most quadratic time in the length of $x$ and hence certainly in the length of the total input of $f_{univ}$. What is not clear is that step 1) can be carried out in polynomial time.</p>

<p>To be clear: I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$. I can also think up an algorithm that test in polynomial time (even time $1000|x|^2$) whether or not $M$ runs for at most $1000|x|^2$ steps. Etc etc etc. However the term 'quadratic' gives us no information on how big or small the implied constant is.</p>

<p>It seems that whenever I make the definition of $f_{univ}$ concrete as in the example above (so output the output of $M$ on $x$ whenever it can be computed in less than $1000 |x|^2$ steps and otherwise output $x$), there might be a world imaginable where quadratic time one way functions exist but all of them take time longer than 1000 times their input length squared and $f_{univ}$ is not one way at all. The only way I can think of to avoid this is for the computer to somehow decide if $M$ halts on $x$ at all but that is known to be a hard problem.</p>

<p>What am I missing?</p>

<p>UPDATE: I see another way out of this: when the proof that any one-way function $f$ can be transformed into a one way function $g$ that runs in quadratic time does in fact give that $g$ runs in time $&lt; cn^2$ for a very concrete $c$. However here it is crucially important that $c$ does not depend on the unkonwn function $f$. This is not clear from me from the <a href="https://docs.google.com/viewer?url=http%3A%2F%2Fwww.wisdom.weizmann.ac.il%2F~oded%2FPSBookFrag%2Fpart2N.ps" rel="nofollow">Goldreich notes</a> Wikipedia links to. (The proof is in section 2.4.2.) Any help clarifying this is appreciated!  </p>

<turing-machines><one-way-function>
Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?
Vincent
# Does Wikipedia assume a solution to the halting problem in their description of universal one way functions?

(Asked by: username_0 on 2016-01-22)

(As for the question in the title: the answer must be no, but then I don't understand what is intended.)

The [Wikipedia page](https://en.wikipedia.org/wiki/One-way_function) on one way functions states:

> Goldreich gives one construction of a universal one-way function, which is denoted by $f\_{univ}$ here.
>
> $f\_{univ} (desc(M), x) := (desc(M), M(x))$,
> where $desc(M)$ is the description of Turing machine $M$, and $x$ is an input string. $M(x)$ is defined as the output of machine $M$ given $x$ as input if the running time is at most quadratic on the length of $x$, and otherwise, $M(x) := x$. This definition of $M(x)$ guarantees $f\_{univ}$ can be efficiently computed within polynomial time.

The point of $f\_{univ}$ is that whenever there exists one way functions that run in quadratic time, then $f\_{univ}$ is a one-way function as well. (And the Goldreich reference proves that whenever one-way functions of any running time exist, they can be used to create one way functions that run in quadratic time, hence obtaining the result that the 'concrete' function $f\_{univ}$ is a one way function if and only if one way functions exist at all.)

I am, however, not convinced that the last statement from the quote is obvious.

As I understand it, a computer wanting to compute $M(x)$ needs to do two things:

1) Decide whether or not the running time of machine $M$ given $x$ as input is "at most quadratic on the length of $x$"

2) Either return $x$ or let $M$ run on input $x$ and return the output

Now it is clear that step 2) takes at most quadratic time in the length of $x$ and hence certainly in the length of the total input of $f\_{univ}$. What is not clear is that step 1) can be carried out in polynomial time.

To be clear: I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$. I can also think up an algorithm that test in polynomial time (even time $1000|x|^2$) whether or not $M$ runs for at most $1000|x|^2$ steps. Etc etc etc. However the term 'quadratic' gives us no information on how big or small the implied constant is.

It seems that whenever I make the definition of $f\_{univ}$ concrete as in the example above (so output the output of $M$ on $x$ whenever it can be computed in less than $1000 |x|^2$ steps and otherwise output $x$), there might be a world imaginable where quadratic time one way functions exist but all of them take time longer than 1000 times their input length squared and $f\_{univ}$ is not one way at all. The only way I can think of to avoid this is for the computer to somehow decide if $M$ halts on $x$ at all but that is known to be a hard problem.

What am I missing?

UPDATE: I see another way out of this: when the proof that any one-way function $f$ can be transformed into a one way function $g$ that runs in quadratic time does in fact give that $g$ runs in time $< cn^2$ for a very concrete $c$. However here it is crucially important that $c$ does not depend on the unkonwn function $f$. This is not clear from me from the [Goldreich notes](https://docs.google.com/viewer?url=http%3A%2F%2Fwww.wisdom.weizmann.ac.il%2F~oded%2FPSBookFrag%2Fpart2N.ps) Wikipedia links to. (The proof is in section 2.4.2.) Any help clarifying this is appreciated!

**Tags:** turing-machines, one-way-function

---

## 1 answers

### Answer by username_1 on 2016-01-22. Score: 4 | Accepted answer

You don't need to know whether it is quadratic on all $x$, only on the particular $x$ that is given as input. And it's easy to decide whether a machine runs in a given time bound on a fixed input $x$. Just simulate it for that many steps and check whether it stops before the time bound runs out.

Here, "at most quadratic" is a little sloppy. It should be read as meaning "at most $|x|^2$ steps", so that there is a concrete time bound to check against. But one should keep in mind that there is a tradeoff between writing that is perfectly rigorous, and writing that can easily be understood by non-specialists, and Wikipedia generally aims for the latter — see <https://en.wikipedia.org/wiki/Wikipedia:Make_technical_articles_understandable> and its specific guidance to "explain formulae in English".

> **Comments:**
> **username_0**: Yes the first paragraph is what I had in mind when I wrote: 'I can think of an algorithm that tests in polynomial time (even time $|x|^2$) whether or not $M$ runs for at most $|x|^2$ steps on $x$.'   Your second paragraph makes a LOT of sense - in fact it is not so long ago that I myself would have interpreted at most quadratic as "at most $|x|^2$ step without worrying about any constants. Thanks for clarifying this!  
> **username_0**: It seems then however that we are in the situation I described under 'UPDATE' (for $c = 1$) and that Goldreich also uses 'quadratic' in the unusual and stricter sense of 'at most $|x|^2$ steps'. I should stare a bit longer at his argument to verify that it does indeed work with this stronger notion of quadratic.  

---

