0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What are the inputs? What do you mean by writing f(x) as an input? $\endgroup$ – xskxzr Dec 25 '18 at 4:01
  • $\begingroup$ @xskxzr Take a function with an input as input 1 $\endgroup$ – l4m2 Dec 25 '18 at 4:06
  • $\begingroup$ Do you mean HALT(f, x, y)? $\endgroup$ – xskxzr Dec 25 '18 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$ – Andrej Bauer Dec 25 '18 at 10:10
  • 1
    $\begingroup$ Is HALT supposed to be computable? Is f supposed to be partial computable? $\endgroup$ – Andrej Bauer Dec 25 '18 at 17:30
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy

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