CSC165 SLOG Week11

What’s something new I learned this week?

• A function f is well-defined iff we can tell what f(x) is for every x in some domain.
• A function f is computable iff it is well-defined and we can 
  tell how to compute f(x) for every x in the domain. ot
  herwise, f(x) is non-computable.
• Halt(f, n) is well-defined and non-computable.
• It is impossible to write one halt(f, n) that works for all functions f.( Proof: 
  construct a clever function that leads to contradiction )
• Given any function, we use reductions to decide whether it is computable or not.

• Reductions: If function f(n) can be implemented by extending another function g(n), then we say f reduces to g.

                         g computable => f computable 

                f non-computable => g non-computable (by contrapositive)

    

•    To prove a function computable, show that this function reduces to a function g that is computable
•  To prove a function non-computable,  show that a non-computable function f reduces to this function.

What’s something that frustrated and challenged me this week?

It definetely should be the proof for halt(f, n). At first I was quite confused about why we picked a 'clever' function in the lecture, since we could write a certain halt(f, n) that works. And I also post the question on Piazza. After the instructor replied to me, I undrstood that I missed an important point : Here clever() is deliberately constructed counterexample for proving that there does not exist a halt() that works for ALL functions, so it is meant to be in this "bad" way. If we add a "not" after the "while", then it would work correctly therefore it is no longer the counterexample that we wanted. 

How confident do you feel about material covered this week?

Not quite sure, still a little confused with the code appeared in the lecture slides and the halting problem. So I think I should read more in Course Notes and lecture notes.

How does course material relate to other classes or interests?

I think the code in the lecture slides are much like codes in python, but also different.

How did your tutorial/test/assignment go this week?

No tutorial this week :) and for assignment 3, I'm still working on it.