What does it mean for a value to be "uniform in" some other value?

50 Views Asked by At

I came across this expression in the "On the Size of Machines" paper by Manuel Blum. Here is an example usage:

"Let $f$ be any recursive function. Then there exist $i, j \in \mathbb{N}$, both uniform in $f$, $g$ such that ..."

and another:

"We give a procedure for determining the two integers $i$ and $j$ uniformly in $f$, $g$."

edit: interpreting it as "independent of choice of..." seems a bit odd, given for instance:

excerpt from the paper

I'm not sure how the index $z$ of $\varphi_z^2$ can be independent of $f$ and $g$ since its definition depends on $f$ and $g$. Of course it is possible I misunderstood the content of the excerpt above.

Blum, M., On the size of machines, Inf. Control 11, 257-265 (1967). ZBL0165.02102.

1

There are 1 best solutions below

1
On BEST ANSWER

It is not very clear, but the meaning must be that not only does there exist an $i$ and $j$ for each choice of $f$ and $g$, but there is a single function that will produce a suitable $i$ and $j$ when given $f$ and $g$ as inputs, and this function is "nice" in some appropriate way.

From the short excerpt you quote it looks like in this particular case, "nice" is supposed to mean that the function that produces $i$ and $j$ is computable (or perhaps even primitive recursive) when its inputs are programs (or Turing machine indices or whatever) that realize $f$ and $g$.