Can there be a function HALT(f, y) so that:

  • There are some x such that f(x) halts iff there are some y such that HALT(f, y) return true;
  • There are some x such that f(x) doesn't halt iff there are some y such that HALT(f, y) return false;
  • HALT always halt and return a boolean

? It makes lots of old conflict don't work. E.g. If f(x) loops forever when HALT(f, x) is true, HALT may return true for half of x.

  • $\begingroup$ What are the inputs? What do you mean by writing f(x) as an input? $\endgroup$
    – xskxzr
    Dec 25, 2018 at 4:01
  • $\begingroup$ @xskxzr Take a function with an input as input 1 $\endgroup$
    – l4m2
    Dec 25, 2018 at 4:06
  • $\begingroup$ Do you mean HALT(f, x, y)? $\endgroup$
    – xskxzr
    Dec 25, 2018 at 6:31
  • 2
    $\begingroup$ You should fix your notation. What is the difference between HALT(f(x),y) and HALT(f,y)? You should make sure you understand the difference between f(x) and f. And also, your question is unclear. For instance, you cannot say "HALT returns true on some y". You should presumably say something like "there exists y such that HALT(f,y) returns true". $\endgroup$ Dec 25, 2018 at 10:10
  • 1
    $\begingroup$ Is HALT supposed to be computable? Is f supposed to be partial computable? $\endgroup$ Dec 25, 2018 at 17:30

1 Answer 1


I assume you mean "Turing machine" by "function", otherwise it is meaningless to say a function halts on some input.

Suppose $\mathrm{HALT}$ exists, then we construct a Turing machine $H$ as follows:

On input $\langle M, w\rangle$ where $M$ is an (encoding of) Turing machine:

  1. Construct a Turing machine $N_{\langle M, w\rangle}$ with input $x$ as follows: run $M$ on $x$ and return what $M$ returns.

  2. Run $\mathrm{HALT}$ on $\langle N_{\langle M, w\rangle}, 0\rangle$ and return what $\mathrm{HALT}$ returns.

Note the result of running $N_{\langle M, w\rangle}$ has nothing to do with its input $x$. If $M$ halts on $w$, $N_{\langle M, w\rangle}$ halts on all inputs, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns true. otherwise $N_{\langle M, w\rangle}$ halts on no input, thus $\mathrm{HALT}( N_{\langle M, w\rangle}, 0)$ returns false.

Now we can see $M$ halts on $w$ if and only if $H$ accepts $\langle M, w\rangle$. Since $H$ always halts, $H$ is a decider for the normal halting problem, a contradiction!

So $\mathrm{HALT}$ does not exist.


Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.