This week we had our last
three lessons, and it is still a little bit tough for me to understand them.
The content we learned this
week is about halt, and it is related to another lesson I am taking, which is
programming.
Halt, which means ‘stop’, is opposite to the
computing method ‘loop ’. If a code runs, and it can finally return a result (sometimes
maybe more results), then the function halts; on the other hand, if it keeps
looping, the function does not halt.
Then the ‘halt’ problem leads to
another important topic, ‘computable’ and ‘non-computable’.
To comprehend ‘computable’, we have to firstly comprehend the concept
of ‘well-defined’. A function is
well-defined if and only if we can tell what f(x) is for every x in some
domain. A function is computable if and only if it is well-defined and we can
tell how to compute f(x) for every x in the domain. Here is another definition.
If function f(n) can be implemented by extending another function g(n), then we
say f reduces to g.
Now we can combine and simplify these two definitions: ‘f reduces to g’ means
‘g computable⇒ f computable’. It is an important
transformation because we can solve the problems about ‘computing’ by using the knowledge on proof. It is also
remarkable that ‘g computable⇒ f computable’ can be written as ‘f non-computable⇒ g computable’.
Above are what we learn this week, and next week we may learn more interesting
theories on computing.
