In week 11, we learnt a little about the history of algorithms involving two individuals, Alonzo Church and Alan Turing. I found it very interesting to know that they showed that some problems can't be solved by algorithms, anyone or computers. I was surprised, as I thought that computers could solve even the most complicated math or logical problems. As well, I was surprised to know that computer programming languages today can solve as many problems as the old Turing machine. This is because I know that languages and machines have become far more advanced now when compared to the past.
We also learnt the concept of halt, which is a non-computable function that takes an input and returns an output, but we don't know how. As well, a function can halt or not halt, depending on its condition. When it doesn't halt, it enters an infinite loop. The professor also taught us a function which cannot be implemented; it is called the equalizer. This is the code:
def H(f, i):
''' Return True if f(i) will halt, False otherwise.'''
# Once you've figured out how to implement this, delete next line
return True
As seen, it looks simple but is virtually impossible.
We also learnt about reduction, which is where a program predicting whether x is initialized is written. The general statement for this is: g computable ===> f computable
Furthermore, partly-working halts, other uncomputable functions, and the way to count finite sets were other concepts covered in lecture.
Infinity doesn't equal infinity: this was a very interesting concept for me to learn as I initially thought that infinity always had to equal itself. But in lecture, I was told that I had to think of it in terms of different extremely big values that are approaching infinity. For example, 2**10000 and 7**1000 are not the same and yet, they both approach infinity.
Also, the professor highlighted the concept of counting by 1-1 and onto, and how a set of natural numbers has the same size as its subset, the even natural numbers. One more interesting thing that I found was that diagonalization proved that not all sets are countable.
In our last week of classes, we learnt additional concepts ranging from Cantor's example to writing an inductive hypothesis. One concept that I found interesting this week was the principle of simple induction, where if something is a predicate of natural numbers, that is true for all natural numbers. This is so, provided that if the predicate's first value is true. This way, the truth value is passed from each value to the next. As well, when the notation is given like this:
We also learnt the concept of halt, which is a non-computable function that takes an input and returns an output, but we don't know how. As well, a function can halt or not halt, depending on its condition. When it doesn't halt, it enters an infinite loop. The professor also taught us a function which cannot be implemented; it is called the equalizer. This is the code:
def H(f, i):
''' Return True if f(i) will halt, False otherwise.'''
# Once you've figured out how to implement this, delete next line
return True
As seen, it looks simple but is virtually impossible.
We also learnt about reduction, which is where a program predicting whether x is initialized is written. The general statement for this is: g computable ===> f computable
Furthermore, partly-working halts, other uncomputable functions, and the way to count finite sets were other concepts covered in lecture.
Infinity doesn't equal infinity: this was a very interesting concept for me to learn as I initially thought that infinity always had to equal itself. But in lecture, I was told that I had to think of it in terms of different extremely big values that are approaching infinity. For example, 2**10000 and 7**1000 are not the same and yet, they both approach infinity.
Also, the professor highlighted the concept of counting by 1-1 and onto, and how a set of natural numbers has the same size as its subset, the even natural numbers. One more interesting thing that I found was that diagonalization proved that not all sets are countable.
In our last week of classes, we learnt additional concepts ranging from Cantor's example to writing an inductive hypothesis. One concept that I found interesting this week was the principle of simple induction, where if something is a predicate of natural numbers, that is true for all natural numbers. This is so, provided that if the predicate's first value is true. This way, the truth value is passed from each value to the next. As well, when the notation is given like this:
"n Î ℕ, n ≥ k
Þ
P(n)
it means that P is true for all natural numbers greater than or equal to k.
On Friday, the professor conducted another activity involving a rectangular grid with a line passing through it diagonally and shaded squares. The shaded squares were because the line passed through those squares. We had to use various techniques to try and derive the formula for this pattern. It was difficult and I didn't succeed, but I enjoyed doing it very much. This is because this allowed me a chance to apply my critical thinking skills once again in the course.
Personally, the concepts were generally moderate in terms of difficulty. This is why I asked my professor questions during lecture, and he clarified my doubts very well. This is what I intend to do in addition to rereading if I don't understand the lecture material, as it is part of seeking help from others.
No comments:
Post a Comment