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.

  • 3
    $\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
    Commented Jun 2, 2014 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
    Commented Jun 3, 2014 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
    Commented Jun 15, 2014 at 20:20

2 Answers 2


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.

  • 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$ Commented Jun 3, 2014 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$ Commented Jun 9, 2014 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$ Commented Jun 11, 2014 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
    Commented Jun 15, 2014 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$ Commented Jun 15, 2014 at 21:26

Predicting a random oracle is not solvable using, possibly, any kind of hypercomputation.

  • $\begingroup$ The OP stated they were looking for "actual, practical, examples". $\endgroup$ Commented Jan 14, 2021 at 11:55

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.