7
$\begingroup$

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?

Improve this question
$\endgroup$
2
$\begingroup$

Godel's First Incompleteness Theorem: "Any consistent formal system within which a certain amount of elementary arithmetic can be carried out is incomplete."

"A certain amount of elementary arithmetic" can be considered as reasonable properties of... well all math.

Incompleteness can also be seen as a form of undecidability.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.