When is the Law of the Excluded Middle Valid/Not Valid?

Sometimes, you can use the Law of the Excluded Middle (LEM) to validly prove things by contradiction (e.g. irrationality of sqrt(2)).

However, at other times, you can not, for example when you have self-referential statements (e.g. Liar Paradox).

My question is: Is there an algorithm/rule that allows one to decide when LEM can be validly used in a proof?

In mainstream mathematics the law of excluded middle is always considered a valid proof step.

There are still some contexts where one is interested in the existence of proofs that avoid this law (as well as various other things deemed "non-constructive") but there's a firm expectation that one has to declare explicitly that one expects proofs in such a restricted style.

The mainstream response to the liar paradox is not to restrict the law of excluded middle, but to refuse completely to make self-referential statements as part of proofs.

Strictly speaking, what is forbidden is not self-reference, but any claims of the form "such-and-such is true" or "such-and-such is false" where "such-and-such" is not a concrete statement but instead an explanation of how to construct the statement we're talking about. This excludes both "this statement" and varieties such as "such-and-such preceded by a quotation of itself".

In practice we do allow writing things such as "Now, if equation (4) above is true, then bla bla bla", but only because the reader can easily unfold it to something where everything is explicit, as in "Now, if $x^2=e^{3x}-\sin^2\theta$, then bla bla bla".

Formulas that include "$\ldots$" are strictly speaking only recipes for making a statement, rather than statements themselves, and at such they are at risk of paradox unless we have a concrete definition that shows how to unfold them to something that does not refer to the truth of constructed statements -- often using an auxiliary recursive definition.

Mainstream mathematics can investigate self-referential statements by treating them as objects of study in an appropriately defined formal system -- running them "in a sandbox", as it were. They can be spoken about but not uttered as claims in their own right at the meta-level.

Your underlying question is philosophical, but that's fine; logic is just as much philosophy as it is mathematics. Let me state your question:

How do we know that LEM is always valid?

The only reasonable answer to this is that there is only one reality, and when we consider totally precise and unambiguous statements about this reality, it is necessarily the case that every such statement is either true or false about this reality, meaning that either it correctly describes reality, or it does not correctly describe reality. We don't care about statements that are ambiguous or not well-defined, just like we don't care about nonsense like ß\EÂ{8ÄäÉ5¨5;-c1÷ÌOm¶ÑzYè:ÏÁôví2QêIxú·9Ñ5u¤­åÉ¡nçßów⧸}tì-Ì«ÞB8r%sHÛæW¯*".vD because it is meaningless.

Based on this, we get classical logic. In classical logic one is only allowed to refer to objects that exist. Because of that, it is impossible to construct the liar sentence, because it is equivalent to:

??? Let $P$ be a sentence such that $P$ is equivalent to $\neg P$.

Which is clearly invalid because we have not proven that such a sentence exists. Indeed, we can show that no such sentence exists. Same for other paradoxes using self-reference (such as Curry's paradox) and paradoxes that assume the existence of objects without proof (such as the Barber paradox).

However, there is another deeper paradox in natural language. Consider the following sentence $S$:

" preceded by the quotation of itself is not a true sentence." preceded by the quotation of itself is not a true sentence.

Flawed argument: Notice that $S$ is a grammatically well-formed sentence of the form X is not a Y., so it ought to be true or false. If $S$ is a true sentence, then by what it claims, $S$ is not a true sentence. Therefore $S$ is not a true sentence. But then by what it claims, $S$ is a true sentence. Thus we get a contradiction.

Where is the error? Think for a while before continuing!

The key is that we will never be able to justify that $S$ is a statement about reality, and so we cannot apply LEM to it.

Sentences can be considered as strings of symbols in reality, so we can rightly say that $S$ is a sentence, and that "$S$ is a sentence" is a sentence, but once we want to say something about truth, it may not be a statement about reality anymore. Let us see what we can and cannot say regarding $S$. (Note that we always interpret "true sentence" to mean "true statement about reality" unless otherwise specified.)

First note that $S$ is the exactly the same string as " preceded by the quotation of itself is not a true sentence." preceded by the quotation of itself.

Thus $S$ is equivalent to asserting that $S$ is not a true sentence.   [(*)]

If $S$ is a true sentence:

  $S$.   [We can state $S$ since it is a true sentence.]

  $S$ is not a true sentence.   [By (*).]

  Contradiction.

If $S$ is not a true sentence:

  $S$.   [By (*).]

  $S$ is a true sentence.   [What we can validly state must be a true sentence.]

  Contradiction.

But we do not have LEM for "$S$ is a true sentence", since we did not prove that it is a statement about reality!

Thus all we can say is that "$S$ is a true sentence" is not a statement about reality, and likewise $S$ is not a statement about reality.

In general this approach can be used to resolve all paradoxes, including Quine's paradox (the one above) and Berry's paradox and the Surprise test paradox.

Note that some things like the circularity of modus ponens are not paradoxes but are intrinsically circular and cannot be justified non-circularly.