Comment by dboreham
4 days ago
Confused why the article author believes this is a surprise. The foundations of mathematics and computer science are basically the same subject (imho) and dualities between representations in both fields have been known for decades.
If something people dedicated multiple years of their lives studying and proving seems trivial to you, you're either a genius or you didn't understand the problem.
There is a world of difference between the obvious and the trivial. The post you are replying to only implied it was obvious, the retort is unnecessary.
It's not a surprise that math and CS are related. It's a surprise that this particular subject in math and CS are so intimately related.
Why? Both are basically about how to handle information with a priori indefinitely many cases, types, instances, species
Is it?
The notion of algorithms and computer science were invented to discuss the behavior of infinite sequences: examining if there’s descriptions of real numbers. This was extended by connecting complicated infinite structures like the hyperreals with decisions theory problems.
That descriptions of other infinite sets also corresponds to some kind of algorithm seems like a natural progression.
That it happens to be network theory algorithms rather than (eg) decision theory algorithms is worth noting — but hardly surprising. Particularly because the sets examined arose from graph problems, ie, a network.
I've done a bunch of theoretical PL work and I find this to be a very surprising result... historically the assumption has been that you need deeply "non-computational" classical axioms to work with the sorts of infinites described in the article. There was no fundamental reason that you could give a nice computational description of measure theory just because certain kinds of much better-behaved infinities map naturally to programs. In fact IIRC measure theory was one of the go to examples for a while of something that really needed classical set theory (specifically, the axiom of choice) and couldn't be handled nicely otherwise.
2 replies →
> He wanted to show that every efficient local algorithm can be turned into a Lebesgue-measurable way of coloring an infinite graph
To me this is quite surprising. Distributed systems were not designed to solve measure theory problems.
8 replies →
Reactions to your statement seem to hinge on whether or not the person replying has a CS degree from a math focused program!
It makes perfect sense to me.
True. After Turing and Co, mathematical logic became almost like applied theoretical computer science.