<p>In this context, uniformity usually means that there exists an algorithm/Turing machine computing the thing that is being called uniform. That is, in this case, that there is a Turing machine that will compute <span class="math-container">$i,j$</span> from (Turing machines for) <span class="math-container">$f,g$</span>.</p>
<p>More formally (in the context of the paper), it means:
There is a Turing machine <span class="math-container">$B$</span> such that, for any total Turing machines <span class="math-container">$F,G$</span>, where <span class="math-container">$G$</span> has infinite range, <span class="math-container">$B(F,G)=(i,j)$</span> such that...</p>

CC BY-SA 4.0
2020-12-02T22:04:16.527Z
Great, thanks! This matches my intuitive guess based on usage in that paper, but I could not find a definition. Searches that I made turned up results on probabilistic computation or circuit theory.

Is this standard nomenclature? The usage of 'uniform' does not appear anywhere, say, in _Sipser's Theory of Computation_ (except regarding uniform circuits) or Rich's _Automata, Computability, and Complexity_. What is the origin of this usage or a reference to the definition?
user10108
CC BY-SA 4.0
2020-12-02T23:05:29.933Z
Yes, it is standard. The distinction arises when one starts learning about circuit complexity, which is a *non*-uniform version of complexity, so "uniform" becomes more important as a distinguisher. (Prior to that, they could've just called it "recursive" or "computable"). "Uniform" originates from its more general use in math as "something holds for all blah" e.g. "uniform upper bound on f(x)" means for all x, etc. In this case, instead of one bound for all inputs, its one Turing machine for all inputs.
Joshua Grochow
CC BY-SA 4.0
2020-12-03T22:57:52.380Z
This is really helpful. Is there a reference I can lookup where this usage of uniform is defined?
user10108
CC BY-SA 4.0
2020-12-02T15:07:28.683Z
2020-12-02T15:07:28.683Z
Joshua Grochow
<p>In Blum's &quot;On the Size of Machines&quot; he uses the word 'uniform' in several places.</p>
<p>For instance, in Theorem 1, he writes</p>
<blockquote>
<p>Let <span class="math-container">$f$</span> be any recursive function. Then there exists <span class="math-container">$i,j\in \mathbb{N}$</span>, both uniform in <span class="math-container">$f$</span>,<span class="math-container">$g$</span> such that...</p>
</blockquote>
<p>What does the word 'uniform' mean in this context?</p>
<p>In addition, is there a reference that defines what it means when one says a variable is uniform in a function?</p>
<p><a href="https://www.sciencedirect.com/science/article/pii/S0019995867905463" rel="nofollow noreferrer">Blum's paper is available at this link.</a></p>

<computability>
What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"
user10108
# What is the meaning of 'uniform' in Blum's paper "On the Size of Machines"

(Asked by: username_0 on 2020-12-02)

In Blum's "On the Size of Machines" he uses the word 'uniform' in several places.

For instance, in Theorem 1, he writes

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

What does the word 'uniform' mean in this context?

In addition, is there a reference that defines what it means when one says a variable is uniform in a function?

[Blum's paper is available at this link.](https://www.sciencedirect.com/science/article/pii/S0019995867905463)

**Tags:** computability

---

## 1 answers

### Answer by username_1 on 2020-12-02. Score: 4

In this context, uniformity usually means that there exists an algorithm/Turing machine computing the thing that is being called uniform. That is, in this case, that there is a Turing machine that will compute $i,j$ from (Turing machines for) $f,g$.

More formally (in the context of the paper), it means:
There is a Turing machine $B$ such that, for any total Turing machines $F,G$, where $G$ has infinite range, $B(F,G)=(i,j)$ such that...

> **Comments:**
> **username_0**: Great, thanks! This matches my intuitive guess based on usage in that paper, but I could not find a definition. Searches that I made turned up results on probabilistic computation or circuit theory.  Is this standard nomenclature? The usage of 'uniform' does not appear anywhere, say, in _Sipser's Theory of Computation_ (except regarding uniform circuits) or Rich's _Automata, Computability, and Complexity_. What is the origin of this usage or a reference to the definition?  
> **username_1**: Yes, it is standard. The distinction arises when one starts learning about circuit complexity, which is a *non*-uniform version of complexity, so "uniform" becomes more important as a distinguisher. (Prior to that, they could've just called it "recursive" or "computable"). "Uniform" originates from its more general use in math as "something holds for all blah" e.g. "uniform upper bound on f(x)" means for all x, etc. In this case, instead of one bound for all inputs, its one Turing machine for all inputs.  
> **username_0**: This is really helpful. Is there a reference I can lookup where this usage of uniform is defined?  

---

