Welcome to my final slog for CSC165. It’s crazy how we are already at the end of the term. In this slog, I will be quickly going over weeks 11 and 12 and also briefly go over Big Theta. In weeks 11 and 12, halting, computability, and countability were the main topics we covered.

Going off last week’s slog, I talked about Big Oh and Big Omega which are the lower bound and upper bound. Big Theta is basically in between. Big Theta represents the average case. Where a function is both lower bounded and upper bounded by another function. In notation statement would be:

f ∈ Θ(g)

This means:

{f : ℕ → ℝ⁺ | ∃ C₁ ∈ ℝ⁺, ∃ C₂ ∈ ℝ⁺, ∃ B ∈ ℕ, ∀ n ∈ ℕ, n ≥ B ⇒ C₁g(n) ≤ f(n) ≤ C₂g(n)}

Notice in the beginning of the statement where there is a natural number and positive real number notation. That means that we are passing in a natural number as the input and then getting a positive real number as the output for function f.

Now onto halting, computability, and countability. Computers usually solve problems with algorithms in a systematic way. Though there are problems that cannot be solved by any algorithms. Halt functions are non-computable.

In CSC165, we learn to decide whether a function is computable or not by using reductions.

Suppose we have a non-computable function f, we can take perhaps a well-defined function g which could be extended to build f.

g computable ⇒ f computable

We say f reduces to g, and using the contrapositive:

f non-computable ⇒ g non-computable

To prove that a function is computable, show that this function reduces to a function g that is computable.

To prove that a function is non-computable, show that a non-computable function f reduces to this function.

Let’s take the function initialized(f, v) where f is a function and v is a variable is checked to be initialized before its first use in f.

Then for a function f1(x), where it returns x+1 and prints a variable y after, initialized(f, v) will return True because y will never be used in f1.

For a function f2(x), where it returns x+y+1, initialized(f, v) will return False because y has not been initialized before being used in the function.

Now for a problem, lets prove that initialized(f, v) is non-computable. To do that we need to show that some non-computable function reduces to initialized(f, v). This non-computable function can be halt(f, n), where f is a function and n is a variable input. So we need to show that halt(f, n) reduces to initialized(f, v), in other words, implement halt(f, n) using initialized(f, v).

First we create the function halt(f, n) with initialized(f, v) inside the function as well as another function that initialized(f, v) can use for f. For this function, let’s say g, it will take an argument (x) and call the function f with argument n that was passed in with halt(f, n) and then call print (v). At the end of halt(f, n), we will return whether initialized(g, v) will return True or False.

If in the function g, if f(n) halts, then we get to print(v), but v has not been initialized anywhere in the code, so when we call “return not initialized(g, v)”, it will return True.

If in the function g, if f(n) doesn’t halt, then we never get to print(v) so when we call “return not initialized(g, v)” will return False. 

Every pair of (function, input) will never properly be matched up with the correct True/ False values. This comes down to counting infinite sets. So now the question is, how do we count infinite sets? When counting finite sets, we have to be wary that the elements are one-to-one and onto. The definition of one-to-one is:

∀ x, y ∈ A, x ≠ y ⇒ f(x) ≠ f(y)

And the definition of onto is:

∀ y ∈ B, ∃ x ∈ A, f(x) = y

A set is countable if and only if it can be defined as a list. For example:

n ∈ ℕ → f(n)

0 → 0

1 → 2

2 → 4

3 → 6

4 → 8

…

Each item in f(n) corresponds to some element of ℕ.

We also talked a little about simple induction, which is actually something we would do in CSC236. Let’s say we have a function P, we know that P(0) is true, and we want to show that the truth transfers over to P(1), P(2), … P(n). In notation it would be,

∀ n ∈ ℕ, P(n) ⇒ P(n+1)

Then we believe that P is true for all natural numbers. 

∀ n ∈ ℕ, P(n)

But not all functions will start with a base case where P(0) will be true. Instead some functions will start later for example P(0), P(1), and P(2) are false, but then P(3), P(4), P(5), and onward are all true. So then there are two cases we need to consider.

Suppose P(n) is a true predicate of the ℕ. If P

     1) Starts out true at P(0) or starts at P(k) where k ∈ ℕ

     2) Truth of P transfers from each number to the next

And that is what we covered in the last few weeks of CSC165. I'm still practicing Big Oh, Big Omega, Big Theta, and halting problems. And I hope that I will be able to do well in Assignment 3. CSC165 has been very interesting and all computer science students who are going to take it next term and years later should definitely pay attention in this course. Thanks for reading!