2
$\begingroup$

In Pass's lecture notes 2.13 section, a universal OWF is constructed. But I have some confusion about:

Let $M_g$ be the smallest machine which computes function $g$. Since $M_g$ is a uniform algorithm it has some constant description size $|M_g|$. Thus, on a random n-bit input $y = <M, x>$, the probability that machine $M = M_g$ (with appropriate padding of 0) is $2^{-\log n} = 1/n$.

$g$ in the context is a strong OWF. $|M| = \log n$ in the quote.

I mean, $\log n$ bits just generate $n$ Turing machines, why the specific $g$ must be there? So the $n$ Turing machines are all the TM?

I know that Turing machine is countable when alphabet set and other settings are fixed. But why in this case $n$ TMs can work?

It confused me for days, can anyone help?

$\endgroup$
0

1 Answer 1

2
$\begingroup$

The crucial sentence is

Since $M_g$ is a uniform algorithm it has some constant description size $|M_g|$.

Uniform means that the same machine can compute the function $g$ for arbitrary input lengths. This machine then has a constant size description that is in particular independent of $n$.

So for a large enough $n$, $\log n \geq |M_g|$.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.