Week 11: A Taste of Computability

I thought computer can do everything, but this week's lecture told me that was not true.

A computer can solve problems if you give it an algorithm. So, if you tell it how to solve those problems, it will give you the answer to the question. No matter how complicated the algorithm is, computer will keep calculating until finish. However, what if you cannot provide an algorithm? Here, I learnt two terms, "well-defined" and "computable". If you say that a function is well-defined, then no matter what your input is, you can tell what the output is (but maybe you don't how you get the output). If you say that a function is computable, first, it must be well-defined. Second, you should be able to tell how do you get the output from the input.

For example, we can assume a simple example. Assume f(x) = 2x, then f(x) is well-defined because for each x in its domain (R), we can tell what f(x) is. Also, it is computable, because we just need to multiply 2 with our input to get the output. The first time I got here I got confused. Is there any function that is well-defined but not computable? I was convinced that there is, and actually there are plenty of them. Assume halt(f, n), which is a function that returns True if function f(n) (input) halts, else return False. Then it is well defined, because for each input, we can tell the output. However, we cannot tell how we get that. If it does not halt, you will never return a value.

We use a strategy called reduction to prove many other functions are all not computable. (And question 5 in assignment 3.) I think we can reach it deeper next week.

After reading a student's slog, I recalled something we learnt last week. In that slog, he focused on the δ-ϵ definition of limit. In the end, he said "Before the  (ε, δ) definition comes out, Newton, Leibniz can't give a precise statement; the very reason because they can't explain infinite small." This is exactly what I heard last year when learning calculation. At that time, we learnt infinite small first, and then learnt the definition of limit using the definition of infinite small rather than the δ-ϵ definition. Last year, the teacher said the δ-ϵ definition was hard for beginners (as the author of this blog said), so we changed the way of learning the limit. Now I have a new sight of the definition of limit from to different but similar angles.