HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

What is a list of "reasonable but undecidable" theorems?

Submitted by: @import:stackexchange-cs··
0
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:

  • 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.

Context

StackExchange Computer Science Q#131014, answer score: 2

Revisions (0)

No revisions yet.