Skip to main content
Share Your Experience: Take the 2024 Developer Survey
1 vote

Undecidable problems in finite graphs

Given a graph class $\mathcal G$, computing the set of forbidden graph minors of $\mathcal G$ is undecidable. A Note on the Computability of Graph Minor Obstruction Sets for Monadic Second Order ...
Pål GD's user avatar
  • 16.6k
1 vote

Gödel's theorem and machines' power

I'm limited by Gödel's theorem, and I'm living quite happily with that. The same would be the case with a conscious or intelligent AI. If being limited by Gödel's theorem made you not intelligent, ...
gnasher729's user avatar
  • 30.4k

Only top scored, non community-wiki answers of a minimum length are eligible