16 votes
Accepted

Did Turing know of Babbage's work?

See: Alan Turing, Collected works: Mathematical Logic (R.O. Gandy & C.E.M. Yates editors, 2001). [page 10, regarding Turing's paper On computable numbers... (1937)] It should be remarked that ...
user avatar
5 votes

Can we fairly assess Ada Lovelace's talent for mathematics?

As mentioned in the comment by Conifold, it is very hard and subjective to assess a talent for anything. It may be true that Ada Lovelace did some basics mistakes and she had some typos or ...
user avatar
3 votes
Accepted

How did Yao come up with his minimum spanning tree algorithm?

I don't have a fully satisfactory answer, but maybe this helps. Tarjan came up with an O(m log log n)-algorithm roughly at the same time. It's in this technical report: http://www2.eecs.berkeley.edu/...
user avatar
  • 46
3 votes

Why is the Halting problem attributed to Alan Turing?

In my opinion, it's because Turing's proof of the "circularity question" in On Computable Numbers, with an Application to the Entscheidungsproblem is close enough to the Halting Problem to warrant ...
user avatar
  • 1,134
2 votes

How did Yao come up with his minimum spanning tree algorithm?

Adding to Flowi's excellent answer, it seems that the main new ingredient in Yao's algorithm is a linear-time selection algorithm, which was new at the time. I think Yao's algorithm is natural once a ...
user avatar
1 vote

Was a work of Ada Lovelace and Charles Babbage inspiration for pioneers of modern computing?

According to Wikipedia: Ada is a programming language designed a team led by Jean Ichbiah at Honeywell under contract to the US Department of Defense from 1977-1983 to supersede over 450 programming ...
user avatar

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