[Solved]: Are there any specific problems known to be undecidable for reasons other than diagonalization, self-reference, or reducibility?

Problem Detail: 

Every undecidable problem that I know of falls into one of the following categories:

1. Problems that are undecidable because of diagonalization (indirect self-reference). These problems, like the halting problem, are undecidable because you could use a purported decider for the language to construct a TM whose behavior leads to a contradiction. You could also lump many undecidable problems about Kolmogorov complexity into this camp.

2. Problems that are undecidable due to direct self-reference. For example, the universal language can be shown to be undecidable for the following reason: if it were decidable, then it would be possible to use Kleene's recursion theorem to build a TM that gets its own encoding, ask whether it will accept its own input, then does the opposite.

3. Problems that are undecidable due to reductions from existing undecidable problems. Good examples here include the Post Correspondence Problem (reduction from the halting problem) and the Entscheidungsproblem.

When I teach computability theory to my students, many students pick up on this as well and often ask me if there are any problems we can prove are undecidable without ultimately tracing back to some kind of self-reference trickery. I can prove nonconstructively that there are infinitely many undecidable problems by a simple cardinality argument relating the number of TMs to the number of languages, but this doesn't give a specific example of an undecidable language.

Are there any languages known to be undecidable for reasons that aren't listed above? If so, what are they and what techniques were used to show their undecidability?

Asked By : templatetypedef

Answered By : Kaveh

Yes, there are such proofs. They are based on the Low Basis Theorem.

See this answer to Are there any proofs the undecidability of the halting problem that does not depend on self-referencing or diagonalization? question on cstheory for more.

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/51150