patternMinor
What is a list of "reasonable but undecidable" theorems?
Viewed 0 times
theoremsundecidablewhatbutreasonablelist
Problem
There are some theorems that go along the lines of "all reasonable properties of are computationally undecidable." Here are two examples:
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?
- 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?
Solution
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.
"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.
Context
StackExchange Computer Science Q#131014, answer score: 2
Revisions (0)
No revisions yet.