10
$\begingroup$

I understand that most problems are trivial if a halting oracle is available (or, I think equivalently, hyper-computation). However, applying the argument that shows the Halting Problem is impossible for a Turing machine also shows that it is impossible for a Turing+oracle to decide the Halting Problem for a Turing+oracle. Are there any actual, practical, examples of problems unsolvable by a halting oracle?

Note: by "oracle" I mean oracle for a standard Turing machine, not a TM with an oracle itself.

$\endgroup$
  • 2
    $\begingroup$ There are "arbitrarily undecidable" problems, see e.g. here. I don't know about "practical" examples (which also does not match the title you chose); what qualifies as "practical" for you? $\endgroup$ – Raphael Jun 2 '14 at 21:07
  • $\begingroup$ That aren't contrived simply to answer this question. I acknowledged that the next-level halting problem still applies. $\endgroup$ – ike Jun 3 '14 at 10:41
  • $\begingroup$ In addition, all languages that are not recursively enumerable are not be reducible to HALT. Examples include FINITE, EMPTY, whether two CFG's derive the same language, etc. $\endgroup$ – user16480 Jun 15 '14 at 20:20
14
$\begingroup$

Just take a problem whose Turing degree is above $0'$, which is the degree of The Halting Oracle. In terms of the arithmetical hierarchy you want problems which are above $\Sigma^0_1$. Examples of such problems (where $\phi_n$ is the $n$-th partial computable function and $W_n = \{k \in \mathbb{N} \mid \text{$\phi_n(k)$ is defined}\}$ is the $n$-th computably enumerable set):

  • $\{n \in \mathbb{N} \mid \text{$\varphi_n$ terminates for finitely many inputs}\}$ is $\Sigma^0_2$-complete.
  • $\{n \in \mathbb{N} \mid \text{$\varphi_n$ is a total function}\}$ is $\Pi^0_2$-complete.
  • $\{n \in \mathbb{N} \mid \text{$W_n$ is a computable set}\}$ is $\Sigma^0_3$-complete.

None of these can be solved even if you have a Halting Oracle. For instance, consider the second example, "is $\varphi_n$ total?" Given $n$ how would the Halting Oracle help us decide whether the Turing machine encoded by $n$ halts on every input?


[Added 2014-06-03] For a "practical" aspect of all of this, consider the problem: a programmer has written a function void charge_credit_card(int card_number, int amount) and we would like to know whether the function terminates on all inputs. It is impossible to write a compiler which can automatically check this in general. Moreover, even if we allow the compiler to ask us questions of the form "does charge_credit_card terminate when given input (k,m)?", it is still impossible.

$\endgroup$
  • 2
    $\begingroup$ Sayng "I do not understand the example" without explaining what confuses you is not productive. Did you read the relevant Wikipedia pages I pointed to? Those are directly related to your question, so the first thing you should od is familiarize yourself with the basic concepts involved. $\endgroup$ – Andrej Bauer Jun 3 '14 at 11:26
  • 1
    $\begingroup$ @ike, the example was meant to have an infinite amount of int, quite obviously. Do you really need me to write BigInt or some such, or will you then complain that computer memory is finite? $\endgroup$ – Andrej Bauer Jun 9 '14 at 20:43
  • 1
    $\begingroup$ Whatever. I told you what the answer to your question was. If you don't want to understand it in good faith, then don't bother us with questions. $\endgroup$ – Andrej Bauer Jun 11 '14 at 7:48
  • 2
    $\begingroup$ A practical example is, $\overline{HALT}$, the compliment of halt. This is $\{<M,w>: \text{M doesn't halt on w} \}$ Given an arbitrary program and input to the program, determine if the program doesn't halt. This problem, along with every other non-recursively enumerable language, doesn't reduce to HALT. $\endgroup$ – user16480 Jun 15 '14 at 21:18
  • 1
    $\begingroup$ @tAllan: you should post that as an answer. It beats me what the OP considers "practical", but your example is certainly better than mine. $\endgroup$ – Andrej Bauer Jun 15 '14 at 21:26

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.