8
votes
3answers
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 ...
23
votes
15answers
4k 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 ...
13
votes
6answers
1k 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?
75
votes
42answers
16k 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 ...