3 ms·

> Alas, no such computer can exist! As powerful as modern computers are, this task cannot be accomplished. This is the content of one of the deepest theorems in

> Alas, no such computer can exist! As powerful as modern computers are, this task cannot be accomplished. This is the content of one of the deepest theorems in mathematical logic. Basically, the theorem says that the Kolmogorov complexity of a string cannot be computed. I disagree that this theorem is very deep. Even a CS-grad noob like me can easily understand several proofs of it.

cpsempek 8y ago
I disagree that simplicity and ease of understanding precludes deepness.
- FartyMcFarter 8y ago
  Maybe. I was thinking that a deep theorem is one that is apparently only explained by a wealth of previous complex knowledge, but perhaps that is not the accepted definition of depth.
lmkg 8y ago
In math, "deep" means that it connects together many things that seem unrelated on the surface, or that it helps explain or prove many things. By that standard, the existence of uncomputability is a deep result.
throwawaymath 8y ago
> I disagree that this theorem is very deep. Even a CS-grad noob like me can easily understand several proofs of it. I guess this depends entirely on your definition of "deep", but many extremely important and far-reaching theorems (and corresponding proofs) in computer science and mathematics are not particularly difficult to understand for a CS graduate. Ideally you should understand the proofs of various deep results. If you already have an undergraduate degree in computer science, you will likely understand results like the CAP theorem or Noisy-Channel Coding theorem. If you don't already, you can probably get the idea in an hour or two of reading. With a little more effort you can more or less fully understand the proofs of various results in mathematics, like Bolzano-Weierstrass, Bayes, Fundamental Theorem of Calculus, etc. These are all very important results that dramatically changed the research landscape at the time they were discovered. The Pythagorean Theorem and proof (by infinite descent) of the irrationality of non-integral square roots are wildly important, but you should trivially learn those in elementary or middle school. Basically, it's a little odd to assert a result is not deep simply because you can understand its proof. In fact, good students working through a textbook can often formulate their own proofs of important theorems before they read the author's if the book is structured especially well.
- deleted 8y ago
  [deleted]
antidesitter 8y ago
I disagree that this theorem is very deep. See https://math.stackexchange.com/questions/2046777/deep-theorem-with-trivial-proof https://math.stackexchange.com/questions/2046777/deep-theore....

cpsempek 8y ago

I disagree that simplicity and ease of understanding precludes deepness.

FartyMcFarter 8y ago
Maybe. I was thinking that a deep theorem is one that is apparently only explained by a wealth of previous complex knowledge, but perhaps that is not the accepted definition of depth.

lmkg 8y ago

In math, "deep" means that it connects together many things that seem unrelated on the surface, or that it helps explain or prove many things. By that standard, the existence of uncomputability is a deep result.

throwawaymath 8y ago

> I disagree that this theorem is very deep. Even a CS-grad noob like me can easily understand several proofs of it. I guess this depends entirely on your definition of "deep", but many extremely important and far-reaching theorems (and corresponding proofs) in computer science and mathematics are not particularly difficult to understand for a CS graduate. Ideally you should understand the proofs of various deep results. If you already have an undergraduate degree in computer science, you will likely understand results like the CAP theorem or Noisy-Channel Coding theorem. If you don't already, you can probably get the idea in an hour or two of reading. With a little more effort you can more or less fully understand the proofs of various results in mathematics, like Bolzano-Weierstrass, Bayes, Fundamental Theorem of Calculus, etc. These are all very important results that dramatically changed the research landscape at the time they were discovered. The Pythagorean Theorem and proof (by infinite descent) of the irrationality of non-integral square roots are wildly important, but you should trivially learn those in elementary or middle school. Basically, it's a little odd to assert a result is not deep simply because you can understand its proof. In fact, good students working through a textbook can often formulate their own proofs of important theorems before they read the author's if the book is structured especially well.

deleted 8y ago
[deleted]

antidesitter 8y ago

I disagree that this theorem is very deep. See https://math.stackexchange.com/questions/2046777/deep-theorem-with-trivial-proof https://math.stackexchange.com/questions/2046777/deep-theore....