11th week journal

The week, we were introduced to a function called halt. This is the most confusing topic ever. Basically this is a non-computable function, and it is impossible to write one halt(f.n) that works for all functions f. Halts mean stop. If a function does not halt, it will go into an infinite loop. When I was taking CSC108, I sometimes ran into infinite loops and didn't know the reason for it. It's cool that now I get to know this. We used a technique called reductions to prove this. If some functions f is non-computable, some functions g could be extended to build f, and this is saying if g is computable, then f is computable. The contrapositive of this implication is that if f is non-computable, then g is non-computable. And this is saying f reduces to g. To prove it, we need to use some python codes, and find the contradiction from there. We want the function f(n) halts, then the other function g(n) will return false. This means that f(n) is non-computable, then g(n) is non-computable. The other topic we covered is computability. The sets of  functions are called 1-1 is when each function has its unique variable. This is to prevent over counting. And the sets of functions are called onto is to prevent under counting. The example Danny gave in class helps me to understand 1-1 and onto. He used the first row of students as examples. There were 10 students in the first row, he pointed at each student, their names as a set, and assigned them numbers to each person, and the assigned numbers as another set. This is 1-1 and onto. To violate 1-1, he double counted the third person, by assigning him number 3 and 4. To violate onto, he skipped the third person. This example made me understand this concept much better. But this week materials are still so confusing. Hope I will understand it more after doing the assignment 3.