Week 12 [Computability] and [Countability]

In week 10's lecture we talked about halt. Here is the prove nobody can write halt(f, n). We assume we could write it and get the contradiction.
def clever(f):
    while halt(f, f):
        pass
    return 42
Now consider two cases: case 1: assume clever(clever) halts, then halt(clever, clever) is true, then entering and infinite loop, then clever(clever) does not halt; case 2: assume clever(clever) does not halt, then halt(clever, clever) is false, then return 42, then clever(clever) halts. We get contradiction in both cases, so we cannot write halt(f, n). We conclude halt(f, n) is well-defined and non-computable. ( 1. A function f is well-defined iff we can tell what f(x) is for every x in some domain. 2. A function f is computable iff it is well-defined and we can tell how to compute f(X) for every x n the domain.)

How do we know if the function is computable or not? We can use reductions. If function f(n) can be implemented by extending another function g(n), then we say f reduces to g. If g is computable then f is computable; if f is non-computable then g is non-computable.

Back to the halt example: a computable initialized would allow a computable halt. No way that's possible. All we need to show here is halt(f, n) reduces to initialized(f, v). In other words, implement halt(f, n) using initialized(f, v).

My friend Udara mentioned two good videos in his post about halt http://udaracsc165.blogspot.ca/2014/11/omega-theta-halt.html



In week 12's lecture, we use mapping f: X-->Y to explain well-defined: each x maps to a unique y; 1-1: each y mapped to by at most one x; onto : every y has some x maps to it.
We also talked about countable: any set A that satisfies size of A smaller or equal to size of N is countable. (Z is countable Q is countable R is uncountable).  Remember we only program countably infinitely many python functions; there are uncountably many functions that we cannot program in python.