Functions are funny

     These past few lectures showed how the structure of a function affects its behaviour. First we looked at bounds of worst-case runtime for Python functions and extended it to any type of mathematical function that can be put into a computer. Then viewing functions through the lens of set theory, we were introduced to the concept that some functions just cannot be physically ran because of the Halting problem. I will go over bounds of worst-case runtime first since they are still firmly in the "sane" camp of math concepts.

    Big-Oh, big-Omega, and other types of bounds are extremely useful when we want a general idea of how efficient our programs are and why certain functions take more steps than others. It's interesting, and also convenient how most of the runtime behaviours can be described by polynomials. I recall in CSC148 that there were a number of functions for big-Oh from best to worst. The best were constant runtime or logarithmic runtime, which makes a lot of sense. However, not all functions display this behaviour, and the best functions have at best n*log(n) realistically speaking. I can't imagine what use we would have for functions of exponential runtime or even factorial runtime!

     Something I've had trouble with was figuring out just how to come up with the equation that describes runtime for a particular Python function, even if I had a basic idea of what loops do to functions. Professor Heap's method of going through the function step by step and using different markers for different parts of the function that have different runtime behaviours is helpful, but it can get messy for longer functions. Eventually I found at least one pattern, which was that every loop will increase the order of the function by 1, and something that should be constant if it wasn't in a loop, like assigning a variable a value, would no longer be so inside a loop. Hopefully I will get better at this before the exam, since this part is tricky, since the straightforward proofs that involve big Oh and big Omega depend on understanding this part.

     Well now I have to admit that the Halting problem confuses me a whole lot, and I'm fairly sure it's not because of lack of sleep. It makes sense that not every function can be computable, but the way that it isn't really bugs me. When there are paradoxes about abstract concepts like time travel, we don't think much of them, but when it is something that feels quite real due to the many real world applications it has like Boolean statements, and even programming languages, it's really weird how they can have paradoxes too! Explaining behaviours of halt or navel_gaze as part of a set of uncomputable functions, which are uncountable does seem to make more sense, in the same way that I feel like "reality" is countable makes sense (the world is quantized after all, so we could we map every particle to a natural number?). There is still a lingering uneasy feeling about this though, and it is not unlike the uneasy feeling of the properties of the empty set.

    It seems this is something that we as computer science students, and scientists in the future, will simply have to get used to.

What is the distinction between arts and mathematics?

       Like any student who wishes to graduate university, I must take courses that fulfill breadth requirements. Like any student who isn't masochistic, I chose to complete them by taking seminars. The last requirement I had to fill was a category 1, so I chose a seminar called "How Stories Work" that was from my own college. It seemed pretty innocuous at first, but that course made me realize that the boundary we put up between art and science is more blurred than we think. We all know there is a beauty to mathematics very similar to the beauty in different forms of art visual design and music. I do not claim to be an expert in art at all, but I have taken lessons. In art classes, students learn the basics and are asked to reproduce a figure as accurately as they can with a sketch. This seems to be what we are doing with proofs. We are given a basic proof structure, and through following the form closely, we see what makes each proof distinct from the next, and we can form an idea of what a good proof would look like just how you learn what a good drawing looks like in art class or how a good piece of music sounds. But this all starts with the basic structure that we are given.
       Another important connection between mathematics and the arts are in storytelling. In a story, we assume certain things about the world, the characters, and the events that happen later will follow through with these assumptions as far as they can. Does that sound familiar? This is exactly what we do when proving logical statements. The "plot" would be analogous to the arguments and calculations that we put into the middle of the proof, which does take us on a journey through a problem and leads us to a satisfying conclusion at the end.This is of course, not very surprising since the system of thought we as humans came up with is a generally universal thing so stories and proofs will share the same structure, and how we learn also follows that structure as well.

On Proofs

      When a student is first introduced to proofs in a math course, they are always presented in as cryptic a way as possible and dressed up in all the fancy math terms the textbook writers can think of. Thankfully, someone with a compassionate heart created this course and so that us poor students get a real introduction to such a fundamental can actually digest proofs and be able to write our own.

      In my experience, students never understand a proof fully if it is just given to them without all the details explained. The "eureka" moment when you get to that connects the antecedent to the consequent is usually glossed over in many proofs, and that leaves me confused when I suddenly see something surprising, but the usage of it does indeed affirm the implication. It's always a good idea to explain why something is used in a proof because not everyone is smart enough to understand that extraordinary algebra in a rearrangement, or why and how the function with a and b in it is necessary in showing a certain relationship relationship. And it goes without saying that the lectures in class also tell us where we should elaborate in the proofs that we construct in the future.

      Now that I am taking this course along with second year calculus, I find that I can really dig into the proofs and understand the thinking process of the person who came up with them. I can fully appreciate just how ingenious some of them are, like the proof for the Bolzano-Weierstrass theorem is a bit long written out but I can see the basic idea is sort of like searching for an element in a list and that's the point in the set that the sequence is approaching...sort of. Well,  before I couldn't even find analogies to help me understand proofs so I would say that this course is definitely putting me on the right path.
 

Translating logical statements in a way YOU understand

       As a person who is absolutely terrible at explaining what is on their mind, naturally I love the idea of formal language. There aren't any double meanings that arise from subtle contextual differences, it stubbornly adheres to only one layer of context, which is that it means what it means. Novelists and poets, go eat your "lavished tomes of nuance and texture" (wow, count those double meanings!). So understanding formal language is the easy part most of the time, it's just like looking at an equation. The hard part is translating our imprecise natural language into formal language symbols. I'm still having difficulties with this, but generally when an English sentence uses "and", it means conjunction. "Or" could be inclusive or exclusive though (the "or" in this sentence is exclusive), but it is easy to tell the different between them. Inclusive or is disjunction, but exclusive or is more analogous to A "and not" B "or" B "and not" A. "And not" is also usually represented in English as "except", but the word "except" could translate into other symbols or operators depending on the context. One could say "and not" implies "except" but "except" does not imply "and not"!
       Logical statements might have precise diction that I appreciate a lot, but their meaning and equivalent statements are a bit harder to internalize. For me, I don't really see why "antecedent implies consequent" could also be written as "(not antecedent) or (consequent)". de Morgan's law was more straightforward though, and I was able to see how that works with Venn diagrams, so maybe if I tried to draw a Venn diagram for any statement or rule I don't understand I would see the connection. Actually Venn diagrams help with vague English statements as well, so I might as well just draw them for everything. Actually truth tables would probably be better for most things. The point is to draw a diagram or use whatever tools you have at your disposal to help you understand.

First Week

       This week, we talked about sets, quantifiers, and statements. which is quite a happy coincidence because my calculus class was also going over the same topics but in a more formal way, so there are a huge number of symbols on the board. Mathematicians are like that. The way they explained it is comprehensive enough (by math department standards), but in 165, you get a more intuitive understanding of sets and how they could be used. Sometimes, intuition aids in internalizing concepts in mathematics and I'm glad that I gained this insight. What I learned in 165 also helps me grasp topics gone over in CSC148, which I took last year. (Of course that is obvious since 165 is supposed to be a co-requisite to that course.) When we look at how any high level computer language is built, we can see they are just a representation of mathematical concepts constructed in a way that is efficient and can be easily understood by people. "Object oriented" programming, as it is called mostly just operates on the same ideas as sets, quantifiers, and statements. Python or any other language will have symbols and syntax very similar to math notation for statements because those are already built into them. If we want to construct anything with those languages we should have a basic understanding of mathematical logic.