①tips for picking c and B for general big-Oh statements:
1. if the antecedent contains one big-Oh/Omega:
for instance:
pick B' = B
get the appropriate c' = 1/c by computing f(n) ≤ c * g(n) and g(n) ≥ c' * f(n)
2. if the antecedent contains two big-Oh/Omega:
for instance:
pick B" = max(B, B')
get the magic c" = c + c' by computing f ≤ ch， g ≤ c'h， and f+g ≤ c"h
②introduction of computability:
Some questions that look easy for computer to solve are actually non-computable, like halt. I'm taking csc108 so I know some about python, but stuff here is more about logic(e.g. REDUCTIONS, write halt(f,I) by using a helper function) rather than coding.
First let's define the terminology based my own understanding:
well-defined: every x has a corresponding f(x)
computable: there is a way we can get f(x) by x
Knowing that this is a logic course, we are more focusing on using functions for proofs. The main question for this part is：given any function, decide whether it is computable or not by using reductions as I mentioned above.
After reading the course notes, I finally generated a clear plan on how to prove a function non-computable:
Step 1： assume the function is computable, in order to derive a contradiction, which in the case given during lecture, is to derive "halt is computable"
Step 2： find a way to compute halt use a helper function:
what we want is: If halt(f,i)halts, then the helper function makes halt returns True. Vice versa
This time the average is around 72%, which is lower then last time but still pretty good. However, my grade surpassed the average by more than 10%. It seems to be a improvement to me, maybe because I'm better at proofs. Overall, the result is a cheer-up to me!
②introduction of computability:
Some questions that look easy for computer to solve are actually non-computable, like halt. I'm taking csc108 so I know some about python, but stuff here is more about logic(e.g. REDUCTIONS, write halt(f,I) by using a helper function) rather than coding.
First let's define the terminology based my own understanding:
well-defined: every x has a corresponding f(x)
computable: there is a way we can get f(x) by x
Knowing that this is a logic course, we are more focusing on using functions for proofs. The main question for this part is：given any function, decide whether it is computable or not by using reductions as I mentioned above.
After reading the course notes, I finally generated a clear plan on how to prove a function non-computable:
Step 1： assume the function is computable, in order to derive a contradiction, which in the case given during lecture, is to derive "halt is computable"
Step 2： find a way to compute halt use a helper function:
what we want is: If halt(f,i)halts, then the helper function makes halt returns True. Vice versa
This time the average is around 72%, which is lower then last time but still pretty good. However, my grade surpassed the average by more than 10%. It seems to be a improvement to me, maybe because I'm better at proofs. Overall, the result is a cheer-up to me!
没有评论:
发表评论