I imagine you are refering to a Turing Machine halting or not halting.
There are statements in Set Theory, which Turing Machines cannot interpret at all ( formally, they have a particular complexity), and require the introduction of “Oracles” in order to assist in interpreting. These are called Oracle Turing Machines. They come about frequently in Descriptive Set Theory.
What do you mean by “believe in the Law of Excluded Middle”
Do you need to believe it applies to all conceivable statements?
Usually, when one is working within a framework assuming the Law Of Excluded Middle, it’s only true for their Domain of Discourse.
Whether it’s true outside that domain is irrelevent.
The Law of Excluded Middle is obviously false, in the framework of quantum bits, where 1 = true, 0 = False. So, I doubt anyone believes it applies Universally, under all interpretations.