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.