The similarity isn't entirely coincidental: http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem http://en.wikip

The similarity isn't entirely coincidental: http://en.wikipedia.org/wiki/Halting_problem#Relationship_with_G.C3.B6del.27s_incompleteness_theorem http://en.wikipedia.org/wiki/Halting_problem#Relationship_wi... I wouldn't characterize either as "trivial", though. May seem obvious in hindsight, but both were a pretty big deal at the time.