Let us consider the set of machines/algorithms with constant inputs (I would have preferred to say no inputs but I was told that every algorithm/machine has to have an input). We call $\mathcal{M}$ the set of all machines and define $C \in \mathcal{M}$ as follows: $$ C(I) = \begin{cases} LOOP, \hspace{0.5cm} I \neq C\\ HALT, \hspace{0.5cm} I = C \end{cases}$$ We next define the following class of machines: $$ \mathcal{M}_0 = \{ M \in \mathcal{M}| M(I) \text{ halts if } I \neq C \}$$ Please note that $C \not\in \mathcal{M}_0$.
Let us now search for a halting oracle $H: \mathcal{M}_0 \times \{ inputs\} \to \{ Yes, No\}$ defined as follows:
$$ H(M_0,I) = \begin{cases} Yes, \hspace{0.5cm} \text{if } M_0(I) \text{ halts }\\ No, \hspace{0.5cm} \text{if } M_0(I) \text{ does not halt} \end{cases}$$
Next we find impossible to apply the Turing's argument for such a machine. Indeed let's consider the machine $N$ with inputs in $\{Yes,No\}$ defined like so: $N(Yes)$ loops for ever and $N(No)$ halts. Then construct the function $$X(I) = N(H(I,I))$$ for all $I \in \mathcal{M}_0$. Assuming that $X \in \mathcal{M}_0$ one evaluates $$X(X) = N(H(X,X))$$ but
- if $X \neq C$ follows that $X(X)$ halts hence $X(X) = N(Yes)$ which loops $\to$ contradiction
- if $X = C$ follows that $X \not\in \mathcal{M}_0$ $\to$ contradiction
It follows that $X \not\in \mathcal{M}_0$ ... and we cannot apply $X$ to itself!
Question:
Is the above reasoning correct?
