# Meaning of “existence” for an uncomputable function related to the Halting Problem

Take the set of all Turing Machines $TM$, we can divide this set in two: $P$, the set of all Turing Machines that will halt if starting from an empty tape, and $Q$, its complement: the set of all Turing Machines that will not halt if starting from an empty tape. We know every TM fits either one of those sets, and $P \cup Q = TM$. But we also know that we can't always decide, given a particular TM, if it is in $P$ or in $Q$: that is the undecidable Halting Problem.

Now have this set $H = \{\text{Haltable}, \text{Unhaltable}\}$, does the following function "exists"?

$$F: TM \rightarrow H\\ F(x) = \begin{cases} \text{Haltable} & \quad \text{if } x \in P\\ \text{Unhaltable} & \quad \text{if } x \in Q\\ \end{cases}$$

$F$ clearly doesn't exists in the sense of recursive function or lambda function, because those are of equivalent computing power of a Turing machine. But it does exists in a sense that every $x \in TM$ is either in $P$ or $Q$.

This question is important when some definition is given concerning the "existence" of some function.

For instance, take the definition of countable set: for a set S to be countable, there must exist a bijective function $C: S \rightarrow \mathbb{N}$.

If we consider the set of computable real numbers, such function $C$ doesn't exists in the constructive sense (it can be shown by diagonalization), but exists in a sense that every computable real number has a TM that computes it, and TMs are countable.

Is there a universally accepted meaning for "existence" in such cases?

• You may be interested in the philosophy of constructivism. – mrp Sep 5 '15 at 16:29
• The title doesn't convey that you are asking about "existence" of a function related to the Halting Problem for Turing machines. Sometimes we may ask if an apparent definition, such as you give here, really defines a unique mathematical thing, and we ask if this "thing" is "well-defined". Please update the title, and give more details of what your concern about the function definition is. – hardmath Sep 5 '15 at 16:31
• The function $F$ is clearly not "computable", but in a "platonic" sense of "exist" (usually that used in math) its definition is "well-formed". See Constructive Mathematics for similar examples. – Mauro ALLEGRANZA Sep 5 '15 at 16:31
• @hardmath Please, give me a suggestion for the title... – lvella Sep 5 '15 at 17:02

Note that in the absence of the law of excluded middle, $\lnot\lnot\exists$ need not be the same as $\exists$.