Final Words Concerning Mathematical Expressions and Reasoning

-D30, M11, Y14-
Hello. So I have been painstakingly attempting to comprehend and apply the halting function to another uncomputable function via reduction, where you define the uncomputable function within the halting function to show that said uncomputable function is in fact uncomputable.
<<about 3 hours later>>
Alright, I think I managed to apply successfully. It seems that these type of not computable functions hold to similar structures: they return only boolean or they return some other output that never changes--such as the number 42. Only then does it seem that the halting function can be (presumably) defined by these functions, and since we know that the halting function is not computable, it is safe to say that the function of interest which was utilized to define the halting function, cannot be computable either.

Now, aside from this, we were briefly introduced to the idea of induction. Although this is a topic in Calculus courses, the steps by which computer science induction is completed has a key difference: you begin with the induction hypothesis, prove it with the induction step, and then determine the base case(s). Although this course makes heavier use of mathematical expressions than Calculus, I do not see how induction problems in this course can so differ from induction problems in Calculus is they are the same thing. The first replaces language with their mathematical equivalents, whilst the second retains the language.
However, the induction problems in this course do bear a striking resemblance to big-Oh and big-Omega proofs, and those are definitely easier to prove when one goes through and proves it and then determines what elements (c and B) were necessary for the now complete proof to work.

It sounds suspiciously similar to circular reasoning, in my opinion, but that is a discussion for a later time. Thank you for reading this conclusion to Mathematical Expressions and Reasoning.

To Halt or Not to Halt: A Vexing Dilemma That Withstands the Passage of Time

-D23, M11, Y14-
Good morning-day-evening-night to you. As expected, programming is indeed not the answer to the universe; there are only a few many problems that cannot be solved by algorithms. Those who are familiar with the likes of Alan Turing and his Turing machine and/or Alonso Church's lambda calculus most likely recognize this dilemma and may have attempted to resolve the vexation because it would be quite nice to be able to solve everything algorithmically. For those of you who are not so well-versed in this issue:
Imagine you wrote a function that contained an infinite loop that would only run if such-and-such a statement were True, and exited the function if said statement were False. Now, could you write a program that could predict if the previous function would halt (exit) or not halt (run the infinite loop until kingdom come)? Therein lies the conflict, for such a program might be capable of managing some extremely simple variables, but because such a program would have to use the function itself in order to evaluate the function, then:
A--If the predicting program returned True, then that means the function should be caught in an infinite loop, and therefore, the predicting program would have never reached the code within its own body that would allow it to have returned anything.

B--If the predicting program returned False, then that means the function halted, which means that the function exited itself, and if this were indeed the case, then how did the predicting program--which contains the now exited function inside it--reach any conclusion?

If this is flying completely over your head, take a moment to catch those thoughts, and mull over them. A key part here is to note that any return statements in the predicting program that come after the return statements and infinite loops of the function should not be reached.

It is truly a marvel to think about, and because we now have an example of a non-computable problem, this problem can be used to implicate the existence of many more non-computable programs in a process called "Reduction."

Final words:
1__2
2__4
3__6
4__8
: __ :
n__2n

Yet another example of a puzzling dilemma: there are just as many even integers as there are integers. No matter what integer you say, I can match an even integer to it. This means, that even though even integers are a strict subset of all the integers--leaving out all the odd integers--the number of even integers that exist (infinity) is the same 'infinity' as all the integers that exist.

And us humans think we are so smart. We cannot even understand what it means to count.
Thanks for reading!

General Statements and a Remark

-D16, M11, Y14-

Welcome back (or welcome, if this is your first time) to another episode of my take on mathematical expressions and reasoning! After the past week, I feel fairly confident that I can complete a big-Oh proof and its negation without serious trouble. What unnerves me is the increasing scope of the proof (e.g., proving general statements about more than one function via the big-Oh). I cannot help but picture a lengthy series of questions that requires me and other students to take two different pieces of code, calculate the bounds of their worst cases, and then prove a general statement between some combination of the four functions. A massive undertaking that could not be successful unless no mistakes are made. I am certain there are well-paying jobs for this; the ability to calculate code and determine its strengths and weaknesses for a software company on paper must be valuable.

Another remark: I recoil from the fact that some example proofs we do in class have "omitted book-ends" within them. I recognize that the class is not long enough for these book-ends to be included while staying on track with what must be taught, but unless these book-ends are included in the Course Notes posted online for the course, or these book-ends are nothing more than elementary arithmetic (I have not had time to complete these book-ends as of late), it seems somewhat counter-productive to the primary goal of education. If we were to solve these book-ends incorrectly, and convince ourselves when we study that what we did was correct/complete, we harm our own academic growth. Understanding how to structure a proof is vital--but the same can be said for the proof itself. One helps build and solidify an answer, and the other is the answer. Hopefully, if I can make time during this excessively busy month, I will be able to ask my professor or my TA about these "omitted book-ends."

Thank you for reading. 

Big-Oh and Last Theorem Follow-up

-D08, M11, Y14-

Hello my good sirs and ladies. I shall report that the realm of Big-Oh is not as opaque as it at first appeared. Another course of mine that deals more heavily in actual computer-science programming techniques has introduced the ideas of sorting and selecting types of codes in accordance with their performance. This performance is measured through worst-case scenarios, which has consequently made understanding how to derive crude mathematical equations that describe the steps taken in code clearer. For example, binary searching--which involves breaking sorted lists of data into smaller parts and then reducing the size of the relevant part of the list until you have found the specific data you asked for--is based off of logarithms. In a sorted list of 2048 indices, binary searching would take approximately 11 steps in the worst case scenario (the item is not within the list) to complete the search, while a linear search pattern (looking at each index one by one) would take 2048 steps to complete the same search. As you probably know, the log(2048) with base 2 is equivalent to 11, and thus the general pattern of binary searches are: log(list_size) with base 2 = number of steps n. Big-Oh cases simply aim to state this process in a logical proof.

Alright, aside from that, I have been working on and off on the treacherous Last Theorem, and have managed--I think--to have proven the Last Theorem for all integer exponents that have a factor of 4. If you do not recall, the Last Theorem states that there are no three positive integers a, b, and c that can satisfy the equation a^n+b^n=c^n for any integer value of n greater than 2. In my uploaded photo, you will notice that I did not include a proof for all n that have a factor of 4, because--aside from the fact that it is intuitive to believe that what does not work for the number 4 will not work for the number 4(2) or 4(3) or 4(4) or... 4(n)--I at one point was frustrated by my inability to prove the theorem when n = 3, and ended up looking to the World Wide Web for guidance.

Feel free to peruse my effort and point out my mistakes. My problem-solving process was to transform the theorem into a mathematical expression, analyze the contrapositive and negation to determine what seemed easiest, and attempt a proof for a small portion of the theorem. My proof was a proof by negation. Hopefully, after careful review and anyone else's insight(s), I will be able to revise and/or expand this proof.

Thank you for reading and perusing!

Big-Ohno

-D04, M11, Y14-
Apologies for the tardiness--this past weekend and this week are pushing the limits of what is humane in terms of assignments.
Anyhow, welcome back to the most threatening proof types since I learned about Induction! In the absolute simplest terms possible, big-Oh proofs reveal the number of steps a program will take when faced with a worst-case scenario--such as when a program that sorts things from left-to-right is given 1000 things to sort, and each of these things is in the order right-to-left.

If that doesn't make sense, pretend that you are in charge of organizing storage in Costco and everything in the storage room is at the exact opposite location of where it ought to be.

In order to determine worst-case scenarios, it is necessary to bound all the worst-case scenarios: O(U) = the absolute worst it can ever hope to be (an overestimation that uses the multiplier 'cU' on the size of the list of things 'size(x)' and says the program will either be less than or equal to this amount 'cU(size(x))'), and Omega(L) = the least amount of steps all worst-case scenarios meet (an underestimation with the multiplier 'cL' on the number of steps '(n)' stating that all worst-cases will do more than or equal to 'cL(n)' steps).

Writing the structure of the proofs for these bounds is not difficult--it is having to trace through a lengthy function, determining how many lines are executed only once, n-times, n-times + 1, n^2 times, n^2 times + 1, n^3 times, and so forth, that is challenging. If this is done poorly, the multiplier 'cU' and/or 'cL' will be skewed, and this in turn skews the value B (the number of steps n is always greater than or equal to). Practice will certainly be a must for dealing with these proofs.

On another note, my Professor has given me the go-ahead with Fermat's Last Theorem. My Professor knew that the full proof was pages and pages of work accumulated over time, so it is acceptable if my proof is not as extensive.

Thank you for reading.

Sorting Strategies and the Last Theorem

-D26, M10, Y14-
Hello all! Although, I have this eerie feeling that some of you just pop in and stare at these in silence. Which reminds me--I should ask my TA if he has seen this blog yet.

Last week, we began to discuss sorting strategies (e.g., insertion, selection, quick, merge) and the importance of determining which strategies are more efficient than others given an algorithm. Hardware and software may change over time, but determining which sorting strategy to employ when dealing with algorithms of a certain order (by order, I mean functions that act in similar ways--all quadratic functions are of the same 'order') by comparing their 'speeds' is of chief concern.

In order to properly consider the speed of a strategies' approach to solving an algorithm, the worst case scenario is tested. Clearly, testing what happens in the best case is impractical, since all  potential obstructions and errors will eventually arise to cause even more problems in the future. Testing the average--the area most common to the typical user--can be helpful, but requires an excessive amount of work, and we all know that a virtue of a computer scientist is laziness, so this is certainly not an option.

I am not familiar with the definitions of each sorting method, but they will surely come to light in future lectures.

In addition, I have been tasked with solving a mathematical/logic problem on my own. I am unsure of the proper balance between the two, but I do have one question in mind:

It is impossible to separate a cube into two cubes, or a fourth power into two fourth powers, or in general, any power higher than the second, into two like powers. 
[Fermat's Last Theorem, 1637]

This states that no two positive integers to the power of n can be added together to produce another positive integer to the same power of n. The first successful proof of this was finally published in 1995 by Andrew Wiles, 358 years after the theorem's discovery, and the theorem has been noted as one of the most difficult mathematical problems in the Guinness Book of World Records.

I don't expect to give a full proper proof to this, but it would certainly be fantastic practice in dealing with difficult problems.

Thank you for reading.

More Proofs

-D19, M10, Y14-
Welcome back to the nth instalment (because I am not counting how many times I have written) of blog posts concerning mathematical expressions and logic! Due to Thanksgiving, we only had two hours of class this past week, so we dealt with proofs that do not involve boolean values, disproving, cases, and delta-epsilon proofs.
Concerning non-boolean proofs, the definition of floor was utilized. In English, the definition is: for all real numbers, the floor of a real number is the same as the integer that is less than or equal to the specified real number and this integer has no other integers greater than it that are closer to the specified real number. It is the same thing as dividing any real number and only looking at the whole number value of it. In Python, this is signified by "//", so 5 // 3 would return 1.
I never thought that mixed numbers would reappear after having only used them up to grade five in elementary school.

For proving things false, it was similar to the typical idea of proving something wrong by providing a counterexample (in the case of Universal statements), but with structure.

As for proofs by cases, this is inception, but with proofs: proof-ception, where in order to prove or disprove a statement, one must prove the statement true/false for a specific category, number, and the like, and then do the same proof for the next related category. It is ironic, that in order to prove something as simple as all natural numbers squared added to themselves will be even, we must build an extensive and relatively complex proof for it, in spite of the fact that academia likes to assert that--if we truly understand something--we can reduce it to its simplest form with relative ease.
Is a fourteen line proof for a simplistic concept support this idea that understanding implies a simple explanation? I believe it disproves this implication.
Sure, it may be true in a number of skills and fields, but it most certainly does not seem to be a universally true statement.

Thanks for watching reading

Proof by Contradiction

-D11, M10, Y14-

Hello! So! Had my first midterm this past week for this class. The difficulty was in-between the short and simple class quizzes and the noticeably more challenging homework assignments, making it a fair midterm in my eyes. I am confident I did well, a few small mistakes here and there--but overall I understood how to 'read' math and use it properly,

Aside from this, we continued with proof structure and solving and proving examples. I must say, this is quite abstract knowledge: it can be a simple task to prove something true or false to yourself, but to prove it to completion, leaving absolutely no loose ends, can be a menial task.

Even the 'simple' idea of proving that there are an infinite number of prime natural numbers becomes complex when you have to prove it. Specifically, it is proven through contradiction--which simply assumes the negation of the thing (that you are trying to prove as true) is true, resulting in some fundamental impossibility--say, 1 = 2--which in turn means the assumption must have been false, thus stating the original statement was in fact true.

This proof by contradiction is very difficult when utilizing the English language, due to its ambiguity in communication--nonetheless, it is a logical argument if all sides/parties hold to the same definitions.

I am not at all firmly grounded in these proofs though. I am unable to complete the proof by contradiction for prime natural numbers at the moment. I have this vague idea that, since the negation of there being an infinite number of natural primes is, there exists a natural number n such that the last prime |P| <= n , I need to set this |P| to be n and then have |P| +1 become the new |P| in the form: m + 1 <= m  where m is a natural number. This would be the necessary contradiction to finish off the proof, but I am probably missing a step somewhere here. Anyone have an insight?

Thank you for reading.

Proof Logic and Existence

-D05, M10, Y14-
Hello again, great to see you all! Joe, Steve, how's it going Toph? Bill, Michelle, Pete, Lyra, Zuko. It would be fantastic if someone reading this was actually named above, but I digress. Last week, we learned about proofs and proof techniques as well as reviewed limits--as in delta-epsilon proofs. The concept of proofs does not intimidate me--nonetheless, I would still like to know the relevance of proofs to programming. Will we create programs that can solve mathematical proofs? This sounds beyond the depth of a first year undergraduate course, however, I could be wrong. This form of communicating truth does remind me of a more philosophical conflict: the argument that everything is subjective.
This perspective of reality has its reasoning--I personally prefer x colour, whilst you might prefer y colour--but when it is expressed mathematically, it is easy to obliterate this idea that life is subjective. For all things (x) in the Universe (U), if it exists in reality or (inclusive) abstractly (E(x)), then it is Subjective (S(x)).
Mathematically:

∀x∈U, E(x) ⇒ S(x)

As a universal statement, all that is needed to prove this statement incorrect is a single counter-example. Ironically, in stating that everything is subjective, the statement itself must be included in this definition. The statement is objective, and thus, the idea that everything is subjective nullifies its own conclusion. The statement is its own counter-example, and everyone who believes that statement needs to reconsider the purpose of their existence. This may have been a philosophical topic of existentialism, but it is still exciting to see how logic intersects these supposedly 'unrelated' fields.

Of course, as this course continues, I hope to return to this "philosophical proof" and reinterpret it entirely within the structure of a mathematical proof. The chain of results was not quite extensive when stated in English--maybe the mathematical proof will be just as brief.

I am certain that a few people would rebel against this logic, others might redefine their idea of subjectivity, and still others might raise their fists in triumph. I hope to hear some feedback.

Until next time. Thank you for reading.

What Math Critical Thinking Questions Ought to Have Looked Like

-D27, M09, Y14-
Hello all, great to (figuratively) see you all here again. So it has been a week, and I can legitimately say that, if any of you ever wondered if folding a strip of paper from end to end, and from left to right, had a pattern...it does.
If you are having trouble envisioning this, then I cannot help you--I attempted to use brackets, underscores, and the like to create a visual of the process, but even I could not comprehend such meaningless chicken scratch.
Aside from discovering a 'mirror image' of folds pointing upwards and folds pointing downwards with the same friend of mine (let us dub him 'Steve' for future reference), I also ended up determining a mathematical expression between the number of folds created by folding n number of times, and the number of folds pointing downwards:
((2^n) - 1) / (2^n-1)
Sure, that was not the point of the problem-solving exercise, but it is nonetheless amazing to discover  an expression for something that people would often be quick to deem as 'random.'

Over the past week, we learned about the logic symbols Conjunction, Disjunction, and Negation, as well as how some laws of arithmetic apply to these operations. Conjunctions equate with logical "and," Disjunctions equate with inclusive "or," and Negations clearly equate with "not." This may sound simplistic, but it is not. Combined with actual expressions, these operations explode into a mess of venn diagrams and truth tables in the hopes of translating math logic into an intelligible language. It still does not sound that bad, you say? Here is a link to De Morgan's law, which is a tautology that uses negation to alter conjunctions and disjunctions:
http://en.wikipedia.org/wiki/De_Morgan's_laws

Now that I look at it more closely, it is not as difficult an idea to ingest--you were right. In essence, De Morgan's first proposition asserts that nothing at all satisfies P's standards and Q's standards--or in other words, nothing at all in P or nothing at all in Q (or is inclusive).

Of course, all this logic engenders another question: how do mathematical expressions deal with language paradoxes?
An example:
The following sentence is True.
The previous sentence is False.

Maybe having a programming language deal with the paradox would be the best way to test a paradoxes' mathematical translation. At the moment, an infinite loop seems to be the most viable result.

Thank you for reading.

Expressing Logic: Vacuous Truths

-D20, M09, Y14-
Herzlich willkommen once again to the meager few who have discovered this on the internet or have been tasked with reading this. I know you are just as excited as I am for the latest installment of this diary blog post.

To follow up on my previous confusion concerning {x in S2 for x in S1}, I did not in fact ask the professor for an explanation of the usage of the word "for;" rather, I asked a friend of mine who is also taking the class, but is vastly more experienced in the realm of computer science in general. The use of the word "for" simply explains to the computer--and to the programmer--that the program will evaluate each element (x) that is in S2, and then compare it with the elements within S1. In my mind's eye, I perceive this as a scanning beam going over the various objects within a box labeled S2, and then the same beam scanning a box labeled S1 for the same objects or for objects that are clearly not the same. Not the most exciting analogy admittedly, but it makes sense to me.

Now, concerning vacuous truths. The logic is quite fantastic, for in beginning with a false premise/antecedent, it does not matter if the conclusion is true or false, because the statement is true. This is the summit of arrogance, and it is hilarious. I can legitimately say, that for all cakes that are within the known universe, the cake that can alter the gravitational field around it is also the cake that can harness thrust without a propulsion system.
Now you must find me a cake that satisfies my antecedent but does not satisfy my conclusion.
No matter how hard you try, no matter the sweat, tears, and blood, you will never produce a counterexample to my claim.

Which means I am right.
-Aside-
This is eerily similar to an event on tumblr spoken of as "the science side of tumblr."
An example: http://i.imgur.com/bTL2DNe.jpg
The antecedent is that the kitten with a hat on its body is a turtle. The conclusion is that the type of turtle it is, is dubbed "mitochondria."  Thus, it is true that all 'turtles' of that kind are mitochondria.

Thank you for reading. As in, you reading => my gratitude.

Report Upon Creation

-Day11, Month09, Year14-
I went ahead and created this blog early out of habit. Hello and Welcome to my retreat, where I will report on a weekly basis the trials and tribulations of CSC165. To the TAs and instructors, I offer a hearty welcome. To any fellow students who grace this website with their presence, I give my regards.

Because this blog is primarily for offering my experience of CSC165, I shall begin:
The first class of the course was welcoming and fairly straightforward: the course aims to develop the skill of communicating ideas, thoughts, and actions through a programming medium.
The second class threw a bit of a curve ball when Instructor Heap had us attempt to translate three python expressions into english. Honestly, when that paper was handed to me, and I looked at the expressions, I wanted to panic. However, with numerous references to the notes I had been taking on translating mathematical expressions into Python expressions, I slowly began to understand the relationship between the two sets in each question.
Unfortunately, by the time these relationships began forming coherent words and phrases in my mind, it was time to collect the papers.

This experience was somewhat intimidating, especially since a number of students (who appeared to be older than myself) were able to answer the questions in the same amount of time I had been given. I worked backwards from their answers to my ambiguous understanding, and then put the answer to the first question in my own words. This is what I focused on in question 0:
return not all ({x in S2 for x in S1})

Then, I replaced the letters within the curly brackets with mathematical symbols, which I cannot display since the inclusive symbol is not available on my keyboard, and wrote:
For all x elements in S1, the program will compare these to all x elements in S2, and return the x element(s) that satisfy "not all," which is equivalent to saying "any" element that is in S1 and not in S2.

I turned off the bold tool for the last part because I am not certain of how that conclusion is reached. Does the word "for" lead to this conclusion? I must not know how it is used in this context, so I will ask Professor Heap after class.

This class will be a challenge, but I'd prefer it if the challenge originated from dealing with hard questions and not from being unaccustomed to terminology.

Thank you for reading this report. I do not know if this is how long blog posts ought to be, but feel free to comment, question, and silently laugh or sigh about what I have said.
Cheers.