Computability and countability

This may well be the last blog post of this semester, the course has been amazing. Our group's solution for assignment 3 has been finalized, and I'm 95% sure they are all correct, one point for that. On another front, the lecture has been about computability and countability, something I can barely understand on the first try. These topics have been the most abstract of all the topics we've covered in CSC165, including big O, logic and proof. Final exam is coming, I wish everyone good luck.

Computers are basically perfect logical number-adding machines, they operate based on logic and instructions, with the power of mathematics. The power and speed of a computer can make even the most demanding calculation for human look easy, therefore we often assume computers are better at human. However, this is not wholly correct, as there are something that's really difficult for computer to solve, like: what do I feel? will this program halt?

The halting problem make me laugh, and the proof that no one can write a halt function amazed me. Basically, we assume someone can write a halt function, then using the halt function to bring a function into an infinite loop, making it non-halting, vice versa to create a contradiction. This proof is constructed by Church and Turing, two of the greatest computer scientists.

We then defined the terms "well-defined" and "computable"

We can often reduce a function F to another function G, by returning G in the definition of F, then we get two implications:

G computable => F computable, because if we can compute G, and F can be represented with G, then F is computable, and

F non-computable => G non-computable, because if F is non-computable, there is no way of writing a G that is computable, since F can be written with G.

When we prove something is non-computable, we just have to reduce a non-computable function, in our case, halt, to that function.

Countability is even more messy, we say something is countable if we can enumerate that thing, for example, natural number and rational numbers are countable, but real number is not. Anything that has a smaller size than N is countable.

How many python functions can be written?

countably infinitely many, because python is written with UTF-8 characters, therefore we can visualize all python functions as natural numbers, making it countable, however, there are uncountably infinitely many functions, as there are non-progr

amable functions such as halt, something we can prove using diagonalization.

Diagonalization guarantees at least a mismatch at every row, making it not in the table of programmable functions, which proves there are more programs than there are programmable programs.

The course has been amazing, I learned a whole lot about computers from a different perspective, as they say math and logics perspective, instead of the traditional notion that computer science is all about coding and programming. This course has provided me with important knowledges going into future years, I'm feeling great! Have a good year!