# Is there any demonstrably uncomputable concrete problem which does not rely on diagonalization?

So diagonalization as we all know is an extremely productive way of showing uncomputability, the other main tool used by CS people for this task being reduction.

But it has occurred to me that I do not know a single uncomputable problem whose demonstration of uncomputability does not rely on diagonalization or reduction to a problem which relies on diagonalization.

Is there any example out there?

• Have you seen this closely related question?
– Evil
Mar 16, 2017 at 21:59
• In particular, do you consider this a proof by diagonalization? Mar 17, 2017 at 11:35
• it appears that uncomputability and diagonalization (over the reals) are nearly the same phenomenon.
– vzn
Mar 17, 2017 at 15:26
• @YuvalFilmus I would consider it to use diagonalization, but it is a great addition to my toolbox, thanks! Mar 17, 2017 at 19:44
• more research, there are several questions on Theoretical Computer Science that are nearly identifical see eg Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization & linked questions
– vzn
Mar 25, 2017 at 15:45

there appear to be "no known examples" of undecidable problems that are not proven through "diagonalization" (precisely formalized), or more strongly, apparently diagonalization is the only way of showing uncomputability. in fact diagonalization, formalized, is an even more general property than undecidability, because exactly the same "mechanism" is behind other key mathematical proofs namely Godels theorem and the uncountability of the reals. this is revealed in the Lawvere fixed point formalism/ theorem.[1][2]

maybe inadvertently, your question is also related or nearly equivalent to the Church-Turing thesis in some subtle or direct ways. the thesis is, roughly, that anything computable is computable by a Turing machine. therefore, equivalently, anything that is not computable is not computable by a Turing machine and all uncomputable Turing languages are reducible to the halting problem and vice versa.

the idea that there exist computations not captured by TMs is considered at best speculative and at worst verging on a "generally not credible" idea by the majority of computer scientists; see eg summary/ "debunking" by Fortnow which also cites several published/ peer reviewed counterclaims.[3] a more recent survey on applicability of Turing machine model and "hypercomputation" etc can be found in [4]

[2] Lawvere, F. William. Diagonal Arguments and Cartesian Closed Categories. Lecture Notes in Mathematics, 92 (1969), 134-145

[4] Turing's Titanic Machine? / Cooper, communications ACM

• All uncomputable languages are not reducible to the Halting problem. Consider for example the language formed by the tuples of TM with access to a halting oracle and inputs such that they halt on that input. By a similar argument to the vanilla halting problem, this augmented halting problem is not computable by a TM with access to a halting oracle. Mar 18, 2017 at 16:56
• agreed there is a hierarchy of undecidability/ reducibility degrees and there is some concept of incomparability in that sense but ofc at the root of that construction is the halting problem. will admit/ concede the assertion/ claim that "diagonalization is the only way of showing undecidability" is maybe not a generally recognized concept in the field... "yet"... have not seen it claimed elsewhere myself. the refs cited are best supporting that have come across in years of research/ pondering nearly the same question.
– vzn
Mar 18, 2017 at 17:03
• But the claim "all uncomputable Turing languages are reducible to the halting problem" is simply not true. Since you appear to agree with this, you should remove it from your answer. Mar 18, 2017 at 18:16
• there are different meanings of the word "reducible", some technical, some not, it has both a narrow and broader meaning and is used both ways in my answer, while there are potentially controversial elements do not consider the answer incorrect, am not interested in hairsplitting or "trick questions", maybe the questioner already has his suitable answer in mind and should answer his own question, anyone who thinks it is incorrect should respond with their own superior/ authoritative/ definitive answer and let audience/ peers/ voters decide as SE is designed/ intended
– vzn
Mar 19, 2017 at 0:35