Difference between revisions of "Simple math of everything"

From Lesswrongwiki
Jump to: navigation, search
(Computer science)
m (links tying diagonalization to the halting problem)
Line 46: Line 46:
  
 
* [http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument on Wikipedia], definition and a step-through of the proof
 
* [http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument on Wikipedia], definition and a step-through of the proof
 +
* Halting Problem
 +
** [http://www.cse.msu.edu/~torng/Classes/Archives/cps860.95/Documents/Halting/Halting.html at Michigan State], problem, theorem, and proof
 +
** [http://www.ling.ed.ac.uk/~gpullum/loopsnoop.html University of Edinburgh], explanation of proof
 +
  
 
==Blog posts==
 
==Blog posts==

Revision as of 05:27, 4 July 2009

But for people who can read calculus, and sometimes just plain algebra, the drop-dead basic mathematics of a field may not take that long to learn. And it's likely to change your outlook on life more than the math-free popularizations or the highly technical math.

Computer science

Amdahl's law

Relates the speedup of a sub-task to the resulting speedup of the whole. Trivially true, but often needed to knock down false intuition.

Asymptotic notation

Used to abstract away units and fixed overhead when analyzing resource usage.

Deterministic finite state automata

Traditional square one of theoretical computer science, with many practical applications.

The pumping lemma for regular languages

Illustrates many recurring themes. Understanding the proof and usage of the pumping lemma will help you understand and apply more famous, advanced results (e.g. anything involving Turing Machines).

Cantor's diagonal argument

An astonishingly elegant technique for proving certain kinds of theorems. Originally introduced by the mathematician Georg Cantor to show that the set of real numbers is uncountable – that is, there is no one-to-one correspondence between real numbers and natural numbers, but was later found to generalize to several other contexts. Perhaps the most notable uses of this technique, in addition to Cantor's proof, are Alan Turing's answer to the Halting problem, and Gödel's proof of his famous first incompleteness theorem.


Blog posts

See also