CSC165 Lecture Week 10/11

This is technically just for lecture week 10, since we won't be having a lecture week 11 for the Tuesday evening class, but anyway, onto the SLOG.

This week in lecture we learned about computability. First let's talk about a few definitions. A function is considered to halt when it eventually stops. For some functions we can write a function halt(f, n) that can tell us whether or not the passed function f will halt with the given input n, but we cannot write a universal halt(f, n) function for all possible inputs.

A function is well defined if and only if we can tell what the output is for every input in some domain. A function is computable if and only if it is well-defined and we know how to compute the output for every input in some domain. By these definitions halt(f, n) is non-computable.

We can prove that a function is non-computable by using reductions. If a function, f, can be implemented by using another function g, that function reduces to g. If g is computable, f is also computable and by the contrapositive, if f is non computable, g is also non computable.