https://wiki.lesswrong.com/api.php?action=feedcontributions&user=Brian+jaress&feedformat=atomLesswrongwiki - User contributions [en]2020-04-05T19:50:13ZUser contributionsMediaWiki 1.31.7https://wiki.lesswrong.com/index.php?title=Simple_math_of_everything&diff=3141Simple math of everything2009-07-03T18:27:55Z<p>Brian jaress: links tying diagonalization to the halting problem</p>
<hr />
<div>{{Quote|<br />
But for people who can read calculus, and sometimes just plain<br />
algebra, the drop-dead basic mathematics of a field may not take that<br />
long to learn. And it's likely to change your outlook on life more than<br />
the math-free popularizations ''or'' the highly technical math.<br />
|[http://lesswrong.com/lw/l7/the_simple_math_of_everything/ The Simple Math of Everything]}}<br />
<br />
==Computer science==<br />
<br />
===Amdahl's law===<br />
<br />
Relates the speedup of a sub-task to the resulting speedup of the whole.<br />
Trivially true, but often needed to knock down false intuition.<br />
<br />
* [http://en.wikipedia.org/wiki/Amdahl%27s_law on Wikipedia], long with examples<br />
* [http://demonstrations.wolfram.com/AmdahlsLaw/ on MathWorld], short without examples<br />
<br />
===Asymptotic notation===<br />
<br />
Used to abstract away units and fixed overhead when analyzing resource<br />
usage.<br />
<br />
* [http://en.wikipedia.org/wiki/Big_O_notation on Wikipedia], long<br />
* [http://en.wikipedia.org/wiki/Big_O_notation#The_family_of_Bachmann.E2.80.93Landau_notations cheat sheet] from the same article<br />
<br />
===Deterministic finite state automata===<br />
<br />
Traditional square one of theoretical computer science, with many<br />
practical applications.<br />
<br />
* [http://en.wikipedia.org/wiki/Deterministic_finite_state_machine on Wikipedia], definition and example<br />
* [http://www.cs.utexas.edu/users/cline/ear/automata/CS341-Fall-2004-Packet/2-Homework/Home04DetFSAs.pdf homework with solutions] (PDF)<br />
<br />
===The pumping lemma for regular languages===<br />
<br />
Illustrates many recurring themes. Understanding the proof and usage of<br />
the pumping lemma will help you understand and apply more famous,<br />
advanced results (e.g. anything involving Turing Machines).<br />
<br />
* [http://www.seas.upenn.edu/~cit596/notes/dave/pumping0.html at Penn Engineering], explanation and examples<br />
* [http://mtc.epfl.ch/courses/TCS-2009/notes/5.pdf handout] (PDF) with concise statement and examples<br />
<br />
===Cantor's diagonal argument===<br />
<br />
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 &ndash; 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.<br />
<br />
* [http://en.wikipedia.org/wiki/Cantor%27s_diagonal_argument on Wikipedia], definition and a step-through of the proof<br />
* Halting Problem<br />
** [http://www.cse.msu.edu/~torng/Classes/Archives/cps860.95/Documents/Halting/Halting.html at Michigan State], problem, theorem, and proof<br />
** [http://www.ling.ed.ac.uk/~gpullum/loopsnoop.html University of Edinburgh], explanation of proof<br />
<br />
<br />
==Blog posts==<br />
<br />
*[http://lesswrong.com/lw/l7/the_simple_math_of_everything/ The Simple Math of Everything] by [[Eliezer Yudkowsky]]<br />
<br />
==See also==<br />
<br />
*[[General knowledge]]<br />
*[[Technical explanation]]<br />
<br />
{{stub}}<br />
[[Category:Work in progress]]</div>Brian jaresshttps://wiki.lesswrong.com/index.php?title=Simple_math_of_everything&diff=3074Simple math of everything2009-06-27T10:17:51Z<p>Brian jaress: started page</p>
<hr />
<div>{{Quote|But for people who can read calculus, and sometimes just plain<br />
algebra, the drop-dead basic mathematics of a field may not take that<br />
long to learn. And it's likely to change your outlook on life more than<br />
the math-free popularizations ''or'' the highly technical math.|Eliezer<br />
Yudkowsky|''[http://lesswrong.com/lw/l7/the_simple_math_of_everything/ The Simple Math of Everything]''}}<br />
<br />
<br />
==Computer Science==<br />
<br />
===Amdahl's Law===<br />
<br />
Relates the speedup of a sub-task to the resulting speedup of the whole.<br />
Trivially true, but often needed to knock down false intuition.<br />
<br />
* [http://en.wikipedia.org/wiki/Amdahl%27s_law on Wikipedia], long with examples<br />
* [http://demonstrations.wolfram.com/AmdahlsLaw/ on MathWorld], short without examples<br />
<br />
===Asymptotic Notation===<br />
<br />
Used to abstract away units and fixed overhead when analyzing resource<br />
usage.<br />
<br />
* [http://en.wikipedia.org/wiki/Big_O_notation on Wikipedia], long<br />
* [http://en.wikipedia.org/wiki/Big_O_notation#The_family_of_Bachmann.E2.80.93Landau_notations cheat sheet] from the same article<br />
<br />
===Deterministic Finite State Automata===<br />
<br />
Traditional square one of theoretical computer science, with many<br />
practical applications.<br />
<br />
* [http://en.wikipedia.org/wiki/Deterministic_finite_state_machine on Wikipedia], definition and example<br />
* [http://www.cs.utexas.edu/users/cline/ear/automata/CS341-Fall-2004-Packet/2-Homework/Home04DetFSAs.pdf homework with solutions] (PDF)<br />
<br />
===The Pumping Lemma for Regular Languages===<br />
<br />
Illustrates many recurring themes. Understanding the proof and usage of<br />
the pumping lemma will help you understand and apply more famous,<br />
advanced results (e.g. anything involving Turing Machines).<br />
<br />
* [http://www.seas.upenn.edu/~cit596/notes/dave/pumping0.html at Penn Engineering], explanation and examples<br />
* [http://mtc.epfl.ch/courses/TCS-2009/notes/5.pdf handout] (PDF) with concise statement and examples<br />
<br />
----<br />
<br />
==Blog Posts==<br />
<br />
* ''[http://lesswrong.com/lw/l7/the_simple_math_of_everything/ The Simple Math of Everything]''</div>Brian jaress