diff options
Diffstat (limited to 'mindmap')
| -rw-r--r-- | mindmap/duality.org | 16 | ||||
| -rw-r--r-- | mindmap/index.org | 8 | ||||
| -rw-r--r-- | mindmap/induction.org | 10 | ||||
| -rw-r--r-- | mindmap/infinity.org | 9 | ||||
| -rw-r--r-- | mindmap/mathematics.org | 15 | ||||
| -rw-r--r-- | mindmap/natural number.org | 89 | ||||
| -rw-r--r-- | mindmap/recursion.org | 89 |
7 files changed, 221 insertions, 15 deletions
diff --git a/mindmap/duality.org b/mindmap/duality.org index 3836272..a87536c 100644 --- a/mindmap/duality.org +++ b/mindmap/duality.org @@ -5,5 +5,17 @@ #+author: Preston Pan #+html_head: <link rel="stylesheet" type="text/css" href="../style.css" /> #+date: <2023-06-10 Sat> -* One or Two? -This is placeholder text. +* is it One or is it Two? +Is it me, or is it you? Is it false, or is it true? Many things +can be explained by a bimodal or binary system. Everything, from +boolean logic to art, any system whose goal is to make a prediction. + +** The Great Filter +No, not the one about aliens dying or something. I'm talking about the +everyday systems that you use in order to make predictions about the +world. For example, this one, that wants to explain everything. + +*** The problem of explaining everything +Because this is indeed a system that explains everything, I must also +demonstrate why it might be impossible to explain everything. I'll +give the argument in a short set of syllogisms. diff --git a/mindmap/index.org b/mindmap/index.org index b2d1015..bf1d94d 100644 --- a/mindmap/index.org +++ b/mindmap/index.org @@ -19,3 +19,11 @@ No, it's a mindmap you fucking idiot. - Don't use the back button on your browser - Everything here is going to be a link to another mindmap page. - Therefore, if there is a page you want to go back to, you must navigate until you find a loop back to the original page. +** What Happens if I don't Follow the Rules? +You're ruining your own fun I guess. These are just the recommended settings +and if you want to change them then you're free to. + +That won't stop me from following you in real life, though. Teehee! +* How did you make it? +This section of the website was made with ~org-roam~, an emacs package that allows +you to make a web of notes, something close to a wiki. diff --git a/mindmap/induction.org b/mindmap/induction.org new file mode 100644 index 0000000..9ba2cbc --- /dev/null +++ b/mindmap/induction.org @@ -0,0 +1,10 @@ +:PROPERTIES: +:ID: 16b06b82-99cc-4343-b171-fb2166c46a30 +:END: +#+title: induction +#+author: Preston Pan +#+options: num:nil +#+html_head: <link rel="stylesheet" type="text/css" href="../style.css" /> +#+options: tex:dvipng + +* Placeholder diff --git a/mindmap/infinity.org b/mindmap/infinity.org new file mode 100644 index 0000000..b08e723 --- /dev/null +++ b/mindmap/infinity.org @@ -0,0 +1,9 @@ +:PROPERTIES: +:ID: 654280d8-82e8-4a0e-a914-bd32181c101b +:END: +#+title: infinity +#+author: Preston Pan +#+options: num:nil +#+html_head: <link rel="stylesheet" type="text/css" href="../style.css" /> +#+options: tex:dvipng +* placeholder text diff --git a/mindmap/mathematics.org b/mindmap/mathematics.org new file mode 100644 index 0000000..55c3dc5 --- /dev/null +++ b/mindmap/mathematics.org @@ -0,0 +1,15 @@ +:PROPERTIES: +:ID: a6bc601a-7910-44bb-afd5-dffa5bc869b1 +:END: +#+title: mathematics +#+author: Preston Pan +#+html_head: <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> +#+html_head: <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> +#+html_head: <link rel="stylesheet" type="text/css" href="../style.css" /> + +* Mathematics is Logic +With a couple of set theory axioms. One might +describe it as an extrapolation framework +without grounding (i.e. a set of implications; +if p then q, but never specifying if p is a property +of a real system or not). diff --git a/mindmap/natural number.org b/mindmap/natural number.org new file mode 100644 index 0000000..9861df6 --- /dev/null +++ b/mindmap/natural number.org @@ -0,0 +1,89 @@ +:PROPERTIES: +:ID: 2d6fb5ac-a273-4b33-949c-37380d03c076 +:END: +#+title: natural number +#+author: Preston Pan +#+html_head: <link rel="stylesheet" type="text/css" href="../style.css" /> +#+html_head: <script src="https://polyfill.io/v3/polyfill.min.js?features=es6"></script> +#+html_head: <script id="MathJax-script" async src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js"></script> + +* What is a Natural Number? +We can formulate the natural numbers from set construction, or by Peano arithmetic. +I will start with the Peano arithmetic formulation. First, we define an immediate +successor function $S:\mathbb{N}\rightarrow\mathbb{N}$ which effectively "adds one" (although we haven't defined addition yet), +and a number we call $0 \in \mathbb{N}$. We then define an axiom: +\begin{align*} +\forall n \in \mathbb{N} \; \nexists S(n) \; s.t. S(n) = 0; \\ +\forall n \in \mathbb{N} \; S(n) \in \mathbb{N}. +\end{align*} +which is equivalent to saying: adding one to any natural number makes it not equal to zero, and +any natural number's successor is a natural number. Because zero is a natural number, we can define +$1 = S(0)$, and by definition $1 \in \mathbb{N}$. Note that it doesn't matter what we call $S(0)$; we just choose +to name it one because we like working in the base 10 number system. + +In a few lines, we should also try to define equality: +\begin{align*} +\forall a \in \mathbb{N}, \; a = a; \\ +\forall a, b, c \in \mathbb{N}, \; (a = b) \land (b = c) \rightarrow a = c; \\ +\forall a, b \in \mathbb{N}, \; a = b \rightarrow b = a. +\end{align*} +which I already explained just sets up equality in the way we're used to. +These axioms are probably slightly important for our purposes, and as you can imagine, they generalize past +natural numbers. Then we define one more axiom: +\begin{align*} +\forall a, b \in \mathbb{N}, \; S(a) = S(b) \Leftrightarrow a = b. +\end{align*} +simply saying that if we add one to both sides of an equation the equality remains. And we're almost done! +There is one problem: given our current axioms, we can definitely prove propositions like these: +\begin{align*} +S(S(0)) \neq S(0) +\end{align*} +however, they don't allow for the ability for us to extrapolate properties of natural numbers /in general/. +** [[id:16b06b82-99cc-4343-b171-fb2166c46a30][Induction]] +Let's introduce our last axiom: +\begin{align*} +\forall n \in \mathbb{N} \: \forall P(n) \; P(0) \land (P(n) \rightarrow P(S(n))) \rightarrow P(n) \; \forall n \in \mathbb{N} +\end{align*} +now, this is the principle of [[id:16b06b82-99cc-4343-b171-fb2166c46a30][induction]] specific to natural numbers. What it is saying is that a property +$P(n)$ is true for all $n$ if there is a "base case" $P(0)$ which is true, and you can show that $P(1)$ is +true from $P(0)$, $P(2)$ is true from $P(1)$ and so on to infinity, or more generally $P(S(n))$ is true for every $P(n)$. +This "base case" essentially bootstraps you into proving it for infinite cases. There is also a general version +of induction, but the only natural numbers case works for us now. +*** And so on to [[id:654280d8-82e8-4a0e-a914-bd32181c101b][Infinity]]? +Wait a second, so how are we defining "to infinity" here? How do we /know/ that $P(x)$ is going to work with every +$n$ even though we haven't tried it for every single $n$? Well, the answer is we extrapolate. We do the first few loops +and we assume the logic carries out to any arbitrarily large loop. It's less of defining things in terms of infinity +and more like playing a game where one person dares the other to go $n$ times, where $n$ is any natural number. They +can say, "calculate that $P(x)$ is true for $P(6)$!", and the claim is that you can /always/ do that, even if they say +one million instead of six, or one billion instead of one million. No matter how high the number, you can repeat the process +$n$ times and get the result that $P(n)$ is true. +*** [[id:16b06b82-99cc-4343-b171-fb2166c46a30][Induction]] = [[id:8f265f93-e5fd-4150-a845-a60ab7063164][Recursion]]? +Wait: isn't the idea of a "base case" kind of analogous to the idea of recursion? And comparing $P(S(n)) = P(n + 1)$ +to $P(n)$ kind of looks suspiciously like a recursive function, only, instead of using the base case in order +to stop the program from running infinitely, we use the base case as a /starting point/ to "run the program to infinity". +Some connections are beginning to be made… +*** [[id:8f265f93-e5fd-4150-a845-a60ab7063164][Recursion]] ~ [[id:654280d8-82e8-4a0e-a914-bd32181c101b][Infinity]]? +It seems one can describe many recursive structures as inherently relating to infinity. I posit that recursive structures +have a starting point and an ending point -- in the case of the factorial, the starting point is a natural number that is +an input to the function, and the ending point is when it reaches zero (because the factorial function "iterates down", +meaning a number is continually subtracted until it reaches a lower bound, meaning what we call the base case has to be always +lower than the input). It is also conceivable that you can have a recursively defined function that has a base case higher +than any possible inputs and iterates upwards. In this case, calling zero the "base case" of induction is actually misleading. +If you model induction as a function, induction /has no base case/, and the input is usually evaluated at zero. Meaning, +*induction is a special case of recursion where no base case is defined*. Although, I'm not sure actual career mathematicians +would like my wording of this issue. +** Set Construction +Given I've described Peano axioms already, I may as well use them. Although, Peano axioms may also be derived from ZFC set theory +axioms. + +Set $S(x) = \{ x \}$ and $0 = \{\}$. Then set construction describes the process of constructing the natural numbers from the empty set +by nesting sets together. For example, $1 = \{0\} = \{\{\}\}$, and $2 = \{1\} = \{\{0\}\} = \{\{\{\}\}\}$. Then all natural numbers can be constructed +recursively expanding the variables. +*** [[id:8f265f93-e5fd-4150-a845-a60ab7063164][Recursion!]] +And now there is a clear demonstrated link between Peano axioms and recursive structures. +** Addition +Okay, that's all good, but natural numbers don't have a use case if even simple things like addition are not defined. +Let's do that! +** Congrats! +We've just defined a natural number! Every single object that can be described in terms of these axioms is +also an instance of a natural number. diff --git a/mindmap/recursion.org b/mindmap/recursion.org index bf42261..f500fb3 100644 --- a/mindmap/recursion.org +++ b/mindmap/recursion.org @@ -19,18 +19,40 @@ Yeah, but I think it's a good introduction to the subject. You can think of recu as [[id:42dbae12-827c-43c4-8dfc-a2cb1e835efa][self-assembly]] and it has deep connections to topics such as [[id:b005fb71-2a16-40f9-9bb6-29138f4719a2][emergence]]. I will first describe it in a mathematics context, and then a programming context. For demonstration purposes, I will use [[id:5d2e2f3b-96ac-4196-9baf-4c3d6d349c98][python]]. -* Mathematics Describes Recursion +* [[id:a6bc601a-7910-44bb-afd5-dffa5bc869b1][Mathematics]] Describes Recursion For this example, I will be using the factorial. One might define it like so: \begin{align*} f: \mathbb{N}\rightarrow\mathbb{N}\ s.t. \\ f(0) = 1 \\ -f(n) = nf(n - 1) \\ +f(n) = nf(n - 1) \end{align*} - +in other words, we want a function defined over [[id:2d6fb5ac-a273-4b33-949c-37380d03c076][natural numbers]] that is one when the input is zero, +and otherwise multiplies the input with a copy of itself, only the input is one less. Let's try evaluating +this function at $x = 3$. +\begin{align*} +f(3) = 3 * f(3 - 1) = 3 * f(2) \\ +f(2) = 2 * f(1) \\ +f(1) = 1 * f(0) \\ +f(0) = 1 +\end{align*} +once we substitute $f(0) = 1$ in, you will see it all collapses. +\begin{align*} +f(0) = 1 \\ +f(1) = 1 * f(0) = 1 * 1 = 1 \\ +f(2) = 2 * f(1) = 2 * 1 = 2 \\ +f(3) = 3 * f(2) = 3 * 2 = 6 +\end{align*} +and so the result is multiplying $3 * 2 * 1 * 1 = 6$. If you observe what we did, you'll see that we started +by trying to replace unknown variables by trying to evaluate $f(x)$ one number down, and eventually we reach +a "base case" -- zero. As soon as the "base case" occurs, we then "go back up" by replacing all the unknown +values with known ones -- and that's how we evaluate recursive functions. * Programming Describes Recursion +Even if you don't understand programming, it should be clear that this represents the factorial function: #+begin_src python :exports both def factorial(x): - if x <= 0: + if x < 0: + return None + elif x == 0: return 1 return x * factorial(x - 1) return factorial(5) @@ -38,12 +60,17 @@ return factorial(5) #+RESULTS: : 120 + +And it also prints the result that we expect for the factorial of 5. Take note that just like in our mathematics +example, ~factorial~ calls itself until it reaches a base case, ~x == 0~. ** The stack frame We are now going to modify the code to be more transparent in the sense that it is going to print each factorial call out: #+begin_src python :results output :exports both def factorial(x): - if x <= 0: + if x < 0: + return None + elif x == 0: print(1) return 1 n = x * factorial(x - 1) @@ -60,12 +87,48 @@ factorial(5) : 24 : 120 -what is happening here? Why is it printing in the reverse order? Well, it is because we are calling -the factorial function from within itself /before/ we print out the return value, which then -keeps on happening for each iteration until it reaches the "base case" (the case in which x <= 0). +what is happening here? Why is it printing in the reverse order? Well, it is the /exact same phenomenon/ +as the "going back up" procedure we did before! + +You can model this behavior with a [[id:52d255d2-114c-42f4-b362-f0b4a2f7b83d][stack]], which is why it is called a stack frame. What's interesting is that +the "going down until you reach the bottom and then building back up" procedure we did to solve $f(3)$ in the +math section is actually modeled well by a stack. Just look at the far right hand side of all our equations in +that example: we try but fail to evaluate $f(2)$, then $f(1)$, then $f(0)$. Then, we succeed in evaluating +$f(0)$, which leads to being able to evaluate $f(1)$, which leads to being able to evaluate $f(2)$. This reverse +ordering is exactly what we see by pushing a list of items onto a stack then removing them from one. Additionally, +the second equation block from that section's right hand side is identical to the first few entries we see in the +results block of this one, and you can see an exact mirroring of the first block in its evaluations of $f(n)$. + +So, the "going down" procedure is the same thing as pushing values onto some sort of stack, and the "going back up" +procedure is exactly the same as popping those values off a stack! +** Computer Hardware Describes Recursion +Even though we can analogize pushing and popping off the stack to this recursion, there still isn't a clear definite +link to the two ideas in hardware. Therefore, I will do a demonstration using assembly. + +To start with, we will be comparing an assembly function that takes the factorial to this one in C: +#+begin_src C :results output :exports both +#include <stdio.h> + +int factorial(int x) { + if (x < 0) return -1; + else if (x == 0) return 1; + return x * factorial(x - 1); +} +int main(int argc, char **argv) { + printf("factorial of five: %d\n", factorial(5)); + return 0; +} +#+end_src + +#+RESULTS: +: factorial of five: 120 + +Because C is a compiled language, it is easier to see what is actually happening human-wise. However, +we will need to write and analyze some assembly in order to figure out what is actually going on. + +Assembly language section coming soon! We will be using NASM due to its readability. +* TODO Recursion Describes…? -You can model this behavior with a [[id:52d255d2-114c-42f4-b362-f0b4a2f7b83d][stack]], which is why it is called a stack frame. Think about each -iteration as getting put on the top of the stack waiting to be printed, until the base case is evaluated -and printed all in one step. -* Recursion is not Recursion -* Recursion is [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]? +* TODO Recursion is not Recursive +There are some things +* TODO Recursion = [[id:1b1a8cff-1d20-4689-8466-ea88411007d7][duality]]? |