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.