All Questions
Tagged with computability-theory big-list
6 questions
135
votes
43
answers
38k
views
What are the most attractive Turing undecidable problems in mathematics?
What are the most attractive Turing undecidable problems in mathematics?
There are thousands of examples, so please post here only the most attractive, best examples. Some examples already appear on ...
34
votes
9
answers
6k
views
Decision problems for which it is unknown whether they are decidable
In computability theory, what are examples of decision problems of which it is not known whether they are decidable?
33
votes
15
answers
7k
views
What's a magical theorem in logic?
Some theorems are magical: their hypotheses are easy to meet, and when invoked (as lemmas) in the midst of an otherwise routine proof, they deliver the desired conclusion more or less straightaway&...
20
votes
2
answers
2k
views
Any important consequences with presupposition of $\mathbf{P} \neq \mathbf{NP}$
As we know, there are lots of consequences with the presupposition of the Riemann Hypothesis.
Similarly, are there any important consequences with the presupposition of $\mathbf{P} \neq \mathbf{NP}$ ?...
17
votes
7
answers
2k
views
Non-constructive proofs of decidability?
Are there examples of sets of natural numbers that are proven to be decidable but by non-constructive proofs only?
4
votes
1
answer
220
views
The link and equivalence between variant definition of computation model and computational complexity over reals
To unify the numerical computation and classic computability theory, or to pave a foundation for the numerical computation, mathematicians present variant computation model and computational ...
- 3,094