What decides completability of a first order theory? [EDIT]: To make the question (the original posting presenting it I've put in a separate section below) non trivial a definition of "inference rule" needs to be given [Noah Schweber] as clearly presented in the answer given to the question by Noah. So here I'll represent the question with its edit:
Let's say that a theory $T$ is completable if there is a computable inference rule $\rho$ such that $T+\rho$ is complete.
What I mean by "computable inference rule" exactly here is:  a meta-theoretic expression of the form  INPUT|OUTPUT, now INPUT must be a recursively defined set of sentences and OUTPUT must be a single sentence, but there must be an effective string manipulation procedure whereby OUTPUT is produced from INPUT in the statement of the rule.
For example the known $\omega$-rule extending PA fulfills those conditions, since $Successor_i(\emptyset)$ is definable recursively as:
$Successor_0 (\emptyset) =  \emptyset$
$Successor_{i+1} ( \emptyset) = S(Successor_i(\emptyset))$
And the schematic representation of the INPUT set of the rule is:
$\forall x (x=Successor_i(\emptyset) \to \phi(x))$
Which of course denotes a recursively generated set of sentences for each formula $\phi(x)$, so the condition for INPUT is met.
Now the output sentence is $\forall x (\phi(x))$ which can be obtained by a simple syntactical manipulation rule of deletion of the substring $``x=Successor_i(\emptyset) \to"$ from the schematic representation of the input of the rule. So the condition for OUTPUT is met.
So clearly PA is a completable theory according to this definition.
So the questions remains the same as posted in the original questions, i.e. those of completability of ZF, and what generally decides completability for a first order theory?
This was raised because in several prior postings, I noticed that ZFC cannot be rendered complete by adding to it $\omega$ like rules? while with PA it works fine!

The original question:
Let's say that a theory $T$ is completable if there is an inference rule $\rho$ such that $T+\rho$ is complete. For example $PA$ is completable, because if we simply let $\rho$ be the known $\omega$-rule, then  $PA + \rho$ is complete.

Question 1: is $ZF$ completable?
Question 2: if not every first order theory is completable, then what make some of them completable and what render others non-completable?

 A: EDIT: I think this question deserves a better answer than I initially gave. In particular, the post-edit restriction to computable inference rules opens up a very interesting door.
Below (following my original answer) I'll dispense with some trivialities, and then (the new stuff) turn to what I think is the right question to ask here.
Since my answer is hecka long, here's a table of contents:

*

*General, and deterministic, inferences


*Naive complexity bounds


*A better complexity analysis


*Silly is still simple


*Complexity + truth?


*A negative result


*Conclusion

General, and deterministic, inferences
It's time to introduce the silly rule(s):
Let $S$ be any completion of $T$; then the rule "from any sentence and any $s\in S$, infer $s$" gives a "$T$-completing" inference rule.
You may object that this is "nondeterministic," and you want an inference rule that only gives you one output for a given input. But that's fixable: assuming for simplicity that our language is countable, injectively write $S=\{s_n:n\in\omega\}$, $T=\{t_n:n\in\omega\}$, and let $\rho$ be "from $t_n$ infer $s_n$."
In general, I don't think determinism/nondeterminism is a useful dividing line here, so I'll ignore it going forward.

Naive complexity bounds
There's a natural "complexity-based" objection to the rule above: namely, it's really really complicated! To tell if an inference is valid, we need to ask whether a given sentence is in the fixed completion $S$. Isn't that hard?
Well, not really. In fact, it's simpler than the classical $\omega$-rule! The question of whether the $\omega$-rule lets us infer $\psi$ from a recursively axiomatized theory $T$ in the language of arithmetic is a $\Pi^0_2$ question, but any consistent recursive theory $T$ has a $0'$-computable (indeed, low) completion $S$ making the corresponding $\rho$ much simpler in general than the $\omega$-rule.

A better complexity analysis
... But that's obviously nonsense. The $\omega$-rule is "easily describable," while the silly rule above was somehow not. The sense given in the previous section in which the silly rule was simpler than the $\omega$-rule wasn't really about the rule but rather the result of applying of the rule, and in some sense missed the "intensionality," according to which the $\omega$-rule is simple but the silly rule is complicated.
So we now want to ask: is there a natural simplicity property which the $\omega$-rule has but which silly rules like the above lack (or at least don't have a priori)? This property in turn should give us the right way to pose your question.
The key point is that the $\omega$-rule has two aspects:

*

*What are the "basic inferences" it can draw?


*Given a set of sentences $T$, does (the usual deductive closure of) $T$ in fact contain the set of hypotheses for a given such basic inference?
To see what I mean, note that the $\omega$-rule  instance

From "$n$ isn't a counterexample to the Goldbach conjecture" for each $n$, infer the Goldbach conjecture

is really a simple thing - it's clear what it means, and it's clear that it is in fact an instance of the $\omega$-rule - but it's not clear whether it applies to (say) PA. Contrast this with the silly rule above: the problem of testing applicability was less complicated, but the description of the rule itself was more complicated.
So this is what we want to focus on: not how hard it is to determine whether an inference can be made, but the set of inferences itself. From here on I need to employ computability-theoretic language, but I think the following captures our intuitions:

A computable infinitary inference rule $R$ is a c.e. set of pairs of (Godel numbers of) sentences; the interpretation is that for each sentence $p$, $R$ says "From $\{q: (q,p)\in R\}$, infer $p$."


*

*This gives us a corresponding deduction relation: $\vdash_R$ is the smallest relation extending $\vdash$ such that we have $A\vdash_Rp$ whenever $\{q: (q,p)\in R\}$ is a subset of the (usual $\vdash$) deductive closure of $A$.

For example, the classical $\omega$-rule amounts to the c.e. set of pairs of sentences $(q,p)$ such that $p$ has the form $\forall x(\varphi(x))$ and $q$ has the form $\varphi(\underline{n})$ for some numeral $\underline{n}$.
(The conflation between "computable" and "computably enumerable" may seem odd, but it simplifies the formal definition noticeably and doesn't result in a different notion via Craig's trick.)
I think this amounts to a meaningful notion of complexity of the rule as opposed to its application.
Unfortunately ...

Silly is still simple
Your favorite theory $T$ has a $\Sigma^0_2$ completion, uniformly: namely, the one built by the "greedy algorithm" of going through sentences one by one and adding whatever we can without yielding contradiction. It turns out - sadly, for our purposes - that every $\Sigma^0_2$ set of sentences can be gotten by a computable infinitary inference rule in a brute-force-ish way:
Suppose $S$ is a $\Sigma^0_2$ set of sentences, that is, we have some bounded-quantifiers-only predicate $\theta$ such that $$S=\{p: \exists a\forall b(\theta(a,b,\ulcorner p\urcorner))\}.$$ For a sentence $s$ and a natural number $n\ge 1$, let $s^n=s\wedge s\wedge ...\wedge s$ ($n$ times), and let $\top$ be the sentence "$\forall x(x=x)$."
Call a sentence "primitive" if it isn't of the form $s^n$ for any $n>1$; WLOG $S$ consists only of primitive sentences (we can always replace such with their "roots").
Now let $R$ be the set of pairs $(q,p)$ such that for some sentence $t$ and some natural number $n$ we have

*

*$p=t^n$,


*$q=\top^k$ for some $k$, and


*for that $k$ we have $\theta(n,k,\ulcorner t\urcorner)$.
For each $t\in S$, we have $\emptyset\vdash_R t^n$ for some $n\in\mathbb{N}$, and hence $\emptyset\vdash_Rt$ since $t^n\vdash t$. Conversely, it's easy to see that we don't get anything not in $S$.
Darn.

Complexity + truth?
There's one obvious thing to push back on, that I can see: the silly rules above tend to concentrate on false completions of the theory.
Specifically, in this sort of situation we generally have more than just a starting theory $T$ - we also have a "designated class" $\mathbb{K}$ of models which we're actually interested in. For example, $\mathbb{K}$ could have a single element (up to isomorphism), the intended model (e.g. the standard model of arithmetic); alternatively, $\mathbb{K}$ could be the set of models of $T$ satisfying an additional non-first-order principle which, while not pinning things down up to isomorphism, is still quite powerful (e.g. the class of transitive models of ZFC).
Now we can restrict attention to computable infinitary rules which preserve truth. The "naive" approach to this interprets "truth" as "the theory of $\mathbb{K}$:"

*

*Version 1: If $A$ is a set of sentences true in every structure in $\mathbb{K}$ and $A\vdash_Rp$, then $p$ is true in every structure in $\mathbb{K}$.

For example, taking $\mathbb{K}$ to consist of just the standard model of arithmetic, the $\omega$-rule has this property. However, this doesn't seem appropriate for your question, since it immediately rules out completeability as long as $\mathbb{K}$ has more than one element up to elementary equivalence. Interpreting the structures in $\mathbb{K}$ as the "good enough" structures, our inference rule should be allowed to focus on some of them as opposed to others (since they're all "good enough") as long as it does so in a self-consistent way. This motivates:

*

*Version 2: If there is some $\mathcal{M}\in\mathbb{K}$ with $\mathcal{M}\models A$, then the $\vdash_R$-closure of $A$ is also satisfied by some structure in $\mathbb{K}$.

This version is more flexible, and seems more appropriate for contexts where $\mathbb{K}$ contains several structures; e.g. it allows for infinitary rules to "pick out" a given transitive model of ZFC from amongst the class of transitive models.

A negative result
We can now finally give a contentful negative instance:
Take $\mathbb{K}$ to be the class of transitive models of ZFC (working in an ambient theory which is sufficiently strong - say, MK). Any computable infinitary inference rule which is truth-preserving with respect to $\mathbb{K}$ in the version 2 sense above cannot possibly yield a complete theory: the closure of ZFC under such a rule is hyperarithmetic but no transitive model of ZFC has a hyperarithmetic theory.
(Why does no transitive model of ZFC have a hyperarithmetic theory? Well, transitive models of ZFC compute well-foundedness correctly, so if $M$ is a transitive model of ZFC then its theory computes the set of indices of computable well-orderings; but this is non-hyperarithmetic. In fact, this tells us that the theory of a transitive model of ZFC is always $\Pi^1_1$-hard! This isn't too far from sharp, by the way: if a transitive model of ZFC exists at all, then there is a transitive model of ZFC whose theory is $\Delta^1_2$ - by Shoenfield absoluteness, such a model exists in $L$, and we can now use the $L$-ordering to locate its theory.)
More generally, we have:

Obstruction: If $T$ is a computable theory and $R$ is a computable infinitary inference rule, then the closure of $T$ under $R$ is hyperarithmetic.

(Indeed we could replace each "computable" above with "hyperarithmetic" - modifying the relevant definitions accordingly - and the result would still hold.) Whenever we want to restrict attention to structures whose theories aren't hyperarithmetic, we get a negative answer to your question interpreted per the above.

Conclusion
Everything above was really just chipping away at the real problem underlying your question: how do we appropriately capture the "naturalness" of the $\omega$-rule as opposed to more ad hoc infinitary inference rules? Ultimately, I think some progress has been made, but the extent to which it's satisfying is of course subjective.
Personally, I'm fairly pleased with it - in particular, the fact that transitive models of ZFC never have hyperarithmetic theories while the standard model of arithmetic does (to put it mildly) is a very satisfying dividing line - but I still feel like a crucial dimension is missing, and bringing $\mathbb{K}$ into the mix at the end feels like a bit of a cheat. How can we fix this? I'm not sure. Silly inference rules can of course be ruled out by imposing syntactic restrictions on their formulations, but these don't feel honest to me either - whatever we whip up should be "implementation-independent." Leaning on computability is fine, by the Church-Turing thesis, but the specific syntax of first-order logic isn't similarly justified in my opinion.
However, I have said everything I can think of so far, and I'll stop here. Hopefully the above was interesting!
