# 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 count them when I was browsing the answers to general undecidable problems.) But I still suspect that there are not many examples naturally arising in combinatorial/discrete geometry. And I am of course interested in any such example. I do not count artificial reformulations of problems stated (by the authors) in different settings.

For instance, it was open for quite some time whether STRING graphs (intersection graphs of curves in the plane) are recognizable. However, it turned out that they indeed are. If the answer was opposite, it would be an example of problem I seek for.

(Let me also exclude problems very similar to Wang tiles if there are any.)

• In principle I agree with Igor. If you are interested in a list of such problems, please say so and use the big-list tag. (In this case you should also turn the question into Community Wiki mode; edit and tick the checkbox). If you are not so much after a list, but rather something else, please elaborate on what it is more precsiely. – user9072 Sep 21 '11 at 13:52
• You may find something in the following link: www-math.mit.edu/~poonen/slides/cantrell3.pdf – M P Sep 21 '11 at 16:47

The problem to determine whether two 4-manifolds, given as simplicial complexes, are homeomorphic. This was shown to be undecidable by Markov. (Some theories of physics involve a sum over such manifolds, one additive term for each homeomorphism class, and this lead to speculation that physics was noncomputable in some sense [Geroch and Hartle 1986]. I am not sure what the current status of that is.)

• John Stillwell in his book "Classical Topology and Combinatorial Group Theory" 1980, gives an excellent background to this archetypal undecidable geometry problem. He shows the full proof for the case of 5-manifolds, which turns out quite a bit simpler than 4-manifolds, but (apparently) has much of the flavour of the Markov proof. I say apparently because I only understand the one for 5-manifolds – WetSavannaAnimal Sep 23 '11 at 10:31

I'm vaguely aware of two examples, but I can't provide any references.

The first is the colored tiling problem. Suppose you're given a finite collection of squares of equal size such that each edge of each square is colored. The collection is said to tile the plane if you can arrange (possibly infinitely many) copies of the squares in the collection in a grid pattern on the plane such that whenever two squares are adjacent along an edge the edge colors match up. It turns out that the problem of determining when a given collection of colored squares tiles the plane contains the halting problem and hence is undecidable.

The second is the problem of determining when two triangulated manifolds are homotopy equivalent. An algorithm for making this determination would necessarily give a solution to the word problem for groups, so it's undecidable.

• Thank you, the second one I am aware of and I rather count it as a topological problem. – Martin Tancer Sep 21 '11 at 13:55
• @Paul: Your first example is known as Wang Tiles: en.wikipedia.org/wiki/Wang_tile . – Joseph O'Rourke Sep 21 '11 at 14:36
• Paul's second example was mentioned by Scott Carnahan in reply to the MO question "What are the most attractive Turing-undecidable problems in mathematics?": mathoverflow.net/questions/11540 . – Joseph O'Rourke Sep 21 '11 at 15:28