Halting problem

    The materials we learned this week were a real challenge to me. We started a new chapter on computability and more specifically, the halting problem. The halting problem is one of supposedly many questions that computer cannot solve. The idea is to write a function that determines whether a function will halt or not. This is proved to be impossible by both Alonzo Church and Alan Turing, independently, in 1936.

    While in lecture, I found the disproof of the halting problem confusing. Admittedly I was lost in the proof and had to review the lecture slides to fully understand it. To disprove the halting problem, we have to create a contradiction. For example the function below solves the halting problem:

def new(f):

while halt(f, f):

pass

return “haha”

    Consider halt(new, new), which tests if the function new halts. If new(new) halts, then halt(new,new) is true and new(new) gets stuck in the while loop then new(new does not halt). The obvious contradiction in the sentence is highlighted in red, and a similar contradiction is shown when we assume new(new) does not halt.

    What is truly interesting about the halting problem is that it is only impossible in the current programming languages that we have. This leads to other provoking questions. Is it possible to invent a new language that makes some ‘unsolvable problems’ in the current languages solvable? As for me, such a language is beyond my imagination, because it will be a whole new way of thinking and a whole new dimension of logic.

Big Omega and General Statements

    This week we wrapped up the Big O session with Big Omega proofs and general Big O statements. The Big Omega proofs are very similar to the Big O proofs. The way I remind myself is this: if I am trying to prove that g(n) <= c*f(n), I will have to manipulate g(n) into a similar expression, say g’(n), that is greater than g(n). This way if g’(n) <= c*f(n), the statement will be true. By the same logic, for f(n), I will have to find a f’(n) that is smaller. Every time I start a proof, I go through this process to see what I am trying to find. This extra process helps me a lot, since I will not have to memorize the steps and possibly get confused by Big O and Big Omega. In terms of general statements of the Big O, I find that it is crucial to understand the relationships between the variables and to utilize the definition of the Big O. This dictates what examples to pick when proving a statement (ie. max, multiplication). 

Big O Continued

  This was an eventful week for csc165. We continued on with the Big O proofs in class and had our second term test on Wednesday. The test went fairly well since the questions are very similar to the assignment questions.

  After some practice in class, I think I am starting to get the hang of Big O proofs with polynomials. The practices also showed how important having a solid understanding in constructing proofs is. With Big O proofs, the numbers we use for c and B can differ, which makes the proofs more diverse and interesting. However, I find myself having problems with proving the negation of the Big O statement, such as the second question in the tutorial 7 problems. I am guessing that n has to be a function involving c and B, and maybe the roof of c since n has to be a natural number. I look forward to the tutorial on Tuesday to see the actual proof of that question.

Big O

    This week we started a whole new chapter involving counting program steps and the Big-O. The concept of Big O is simple as of now, but I expect to see more complicated variations and examples in the near future. I am understanding the ideas of a breaking point, and I find the graphical representation very helpful. However, counting the number of steps the program takes is surprisingly more difficult than I expected.  When trying to find the worst case scenario, I find it confusing when there is a for loop inside another for loop because of the new variable. While loops are similar, but with a restriction to watch out for. I think overestimating the number of steps making it much easier because I get a general idea of the number of steps. Overestimating the steps may actually not be that bad, since it will still work if we are relating it to the Big O.