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

  1. if $X \neq C$ follows that $X(X)$ halts hence $X(X) = N(Yes)$ which loops $\to$ contradiction
  2. 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!


Is the above reasoning correct?

  • $\begingroup$ Your definition of $M_0$ seems to be cyclic. Is there a typo there? $\endgroup$
    – Shaull
    Nov 4, 2020 at 14:36
  • $\begingroup$ There is no typo ... just wanted to say that "the user" can replace $M_0(C)$ with the unique "thing" that $M_0$ is supposed to do ... That was the best way I found to express that ... I am just trying somehow to say that the machines in $\mathcal{M}_0$ do not have inputs, or do not depend on the inputs $\endgroup$
    – C Marius
    Nov 4, 2020 at 14:43
  • $\begingroup$ Sorry, but I cannot follow your argument at all. It's not clear to me what you're trying to show, nor what the steps are. Perhaps add some more explanations as to what you're trying to achieve. $\endgroup$
    – Shaull
    Nov 4, 2020 at 19:07
  • $\begingroup$ I have made an edit! Is it clearer now? $\endgroup$
    – C Marius
    Nov 4, 2020 at 19:11
  • 1
    $\begingroup$ We discourage "please check whether my answer is correct" questions, as only "yes/no" answers are possible, which won't help you or future visitors. See here and here. Can you edit your post to ask about a specific conceptual issue you're uncertain about? As a rule of thumb, a good conceptual question should be useful even to someone who isn't looking at the problem you happen to be working on. If you just need someone to check your work, you might seek out a friend, classmate, or teacher. $\endgroup$
    – D.W.
    Nov 4, 2020 at 21:14


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Browse other questions tagged or ask your own question.