All Questions
Tagged with computability-theory big-list
11 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}$ ?...
18
votes
5
answers
2k
views
What are some interesting applications/corollaries of Kleene's Recursion theorem?
Lately I became very interested in the theory of computability and a fundamental early result you learn is the Recursion Theorem also known as the Fixed point theorem. At first sight you can see it's ...
- 893
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?
15
votes
10
answers
2k
views
Can you prove equivalence without being able to calculate it?
In mathematics we often seek to classify objects up to an equivalence relation, where two objects A and B are said to be equivalent if there exists a map $f:A\rightarrow B$ satisfying certain ...
9
votes
1
answer
753
views
List of finitely presented groups with undecidable word problem
Is there any reasonably updated list of (representative) examples of finitely presented groups with undecidable word problem?
By "representative" I mean "avoiding obvious redundancy", i.e. examples ...
- 343
8
votes
3
answers
1k
views
Undecidable problems in geometry
Are there any (many) algorithmically undecidable problems in computational (combinatorial/discrete) geometry?
Update: the Wang tiles answer the question with "any". (I have somewhat overlooked to ...
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
-1
votes
0
answers
94
views
Relation between properties of functions/sets and Grzegorczyk's hierarchy
I know for example that the first level of the Grzegorczyk hierarchy contains the functions which enumerate the c.e sets and that it has an interesting relation to the provably total functions in ...
- 893