Week 11

We finished the topics of proving and disproving Big Oh, Big Omega, and Big Theta from last week.

This week's contents:

1. Algorithm  
2. Some terminologies (new vocabularies) 
3. Reduction 
4. Infinite does not always equal to Infinite
5. 1 - 1 and onto 
6. Countable

First of all, most of us interested in computer because we want to solve problems in a systematic and logic ways. Enable for our devices to implement our solutions/programs, it will need algorithm to perform the tasks. Algorithm is defined as sequences of executable steps. Alan Turing,  a British computer scientist, who was widely known for his concepts of algorithms and computations, invented the first general purpose computer model which is called Turing machine. Moreover, Turing came up with the proof that there would be uncomputable problems  on any reasonable computing models/devices. In modern times, we realized that even using different modern programming languages, such as Python, C++, Java, and etc., to implement the problems would not work.

Secondly, we learned some new terminologies from following example.

 

Computable: a program/problem that can be solved by algorithms. 

Noncomputable: a program/problem that can't be solve by algorithms. 

Following, reduction was introduced. Let's start with an example: assume I know function f is non-computable, but I was given well defined function g. What I can do next is to extend (by adding some extra executable steps) the function g then build function f, which this step can be shown as an implication ( g computable => f computable). Next, we say f reduces to g, using the rule of contrapositive (not P => not Q), which we have f non computable => g non computable.

Next,  infinite does not always equal to infinite. Here's the reason why,  sets A and B have infinitely many items if they each have more items than any finite number. However, having more than any number isn’t the same as saying they have the same size as each other.  Basically, it means two sets (either finite or infinite) have the same size (same amount of numbers /items). By matching them up(by counting) in two ways ( 1 - 1 and onto). 

Furthermore, 1 - 1 and onto are terms that we use when we describe a function. 

In  1 - 1, it simply means that no two elements in x are mapped to the same element in y. 

On the other hand,  the term onto means when every element in y is covered (even if there is/are extra value(s) in set X. Additionally, there is also an occasion which we call correspondance when onto and 1 - 1 both exist in the case.  

Lastly, we were introduced with Cantor's diagonal proof, commonly known as diagonization. By doing a diagonal proof, it allowed us to know the fact that not all sets are countable. All rational numbers are countable. All real numbers are not countable. (More details were introduced in week 12).