#StackBounty: #undecidability #mathematical-foundations What is a list of "reasonable but undecidable" theorems?

Bounty: 250

There are some theorems that go along the lines of "all reasonable properties of <math subject> are computationally undecidable." Here are two examples:

  • Rice’s Theorem: "all reasonable semantic properties of programs are undecidable."
  • Adian–Rabin Theorem: "all reasonable properties of finitely presented groups are undecidable."

Even though I only know of two examples, I suspect that there are many theorems like these. Is there a list of these kinds of theorems?


Get this bounty!!!

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.