Hmmmm

Last week we talked more about computable functions. On Friday we had another class problem about diagonals. The professor showed that the halting function is not computable because there's a counterexample that uses the halt function. It feels weird because that's a special function that makes the halting function doesn't work. I didn't get it last time too, because if the halting function is well defined, and we know what the output should be for all inputs, then what's the right output for the halting function? I think it would have been cool if they talked about if it was possible to write a halting function for functions that don't try to use the halting function

Hmmmmm

Last week we began talking about the halting function in Danny's section. We also talked about the size of sets, and how to count big sets like the rational numbers. He showed that the size of even numbers is the same as the size of natural numbers. It's not intuitive but I guess it makes sense from the definition. Hmmmmm

Hmmmm

We are learning about using big O notation for algorithms in class. It's mostly the same as our old proofs but we have to count how many steps a function takes. Then we started doing more big O proofs in class. They also seem like our old proofs, except the statements are much longer and there is a similar structure in most big O proofs. Finally we started learning about computability in Larry's class. I'm confused about what a well defined function is. Larry said a well defined function is a function we know what the output should be for every input. Or something like that. And he said that a computable function is a function we know how to get the output. The halting function is supposed to say whether a program or function halts, and he gave an example of a function that loops if the halting function says it halts, and stops if the halting function says it doesn't, so there is a contradiction. But if the halting function is well defined, what is the output supposed to be for this special function? I wish I understood this class better, like those people who always raise their hand and speak really loudly. Someone even took the time in lecture to explain to everyone where the number 42 comes from. That was very helpful, because I would have been confused about the code example otherwise.

Hmmmm

Last class the professor did a full example of proving that insertion sort is O(n^2). I think it made sense, but I'm starting to get confused about all the formats we have to follow. In the tutorial, the quiz was another proof. I'm worried about the formats of my proof in assignment 2. It's also hard to find new things to talk about because I'm not very good at programming algorithms and we've talked a lot about proofs

Hmmmmm

Hi, this week the professor said we were finishing up on proofs. I enjoyed the proofs section of the class. In high school, my teacher said epsilon delta proofs were hard, but they made more sense when the professor in this class did it. But when I tried thinking about it myself, it was frustrating. I felt good about the tutorial quiz this week. Even though I'm not that good with proofs, the problems are usually like the homework problems. I like them because I think they test people's understanding.

We started learning about sorting algorithms in class. To start, the professor asked us how we sort cards in our hands. Other people had specific ways they sort them. I thought about it, and I don't know how I sort my cards. I just move them around until they look sorted. Maybe I would be better if I knew how to sort my cards. My friend laughed and said I used bogosort, but it wasn't one of the algorithms in the lecture slides. Then he showed me it on wikipedia, and I don't think it was a good sorting algorithm. The professor said python uses timsort, so I should try to learn to sort my cards better.

Hmmmm

There was only 1 lecture so far this week because of thanks giving, and there were no tutorials. So I'm not sure what to write about. But I was thinking about something someone said in tutorial, and I thought of an answer this week, and I think it's interesting, so I will write about it.

Someone said that when you do ∃x, y, it should automatically mean x is different from y, because whenever you write ∃x, y you don't want them to be the same thing. It seemed right, but sometimes you don't care if x and y are the same. I thought of this example this week.

I say "The set S of positive even numbers excluding four is closed under addition." You say that's not true, and there's a counterexample: ∃x, y ∈ S, ¬(x + y ∈ S). But I don't think there are counterexamples if x and y are different. But if x and y are the same, 2 + 2 is 4 which is not in S.

So, sometimes when we use ∃x, y, we don't care if x and y are the same. Actually, in this example, it's important that x and y are generic.

This looks kinda short, so I will write about how one of my other classes related to CSC165. There was a question in a past midterm that said "the logic function f is true when any 2 of the inputs are true." My friend and I thought it meant "at least two are true", because if three inputs are true, there are "any 2" inputs that are true. But in the answer, "any" meant "only". In English, people might argue about exactly what things mean. But if I write it symbolically, I think most people would agree that "any two are true" is ∃x, y ∈ S, x not equal to y, x ∧ y. Now, it's clear that if three inputs are true, "any two are true" is still true. It's also clear that P(S) = ∃x, y, z ∈ S, x not equal to y not equal to z, x ∧ y ∧ z is a subset of Q(S) = ∃x, y ∈ S, x not equal to y, x ∧ y (the set of sets such that P holds is a subset of the set of sets such that Q holds). If P is a subset of Q, then P ⇒ Q. If Q(S), then we know three different inputs x, y, z are true. I can pick two for satisfying Q(S). Symbolic notation is good

Hmmmm

In class we started learning about proofs. I saw a cool problem yesterday. I thought I'd try to prove it using the stuff we learned in class.

Prove that f(n) = 1 − n is the only integer-valued function that defined on the integers that satisfies the following conditions:
a) f(f(n)) = n for all integers n
b) f(f(n + 2) + 2) = n for all integers n
c) f(0) = 1

I'm going to try to write it symbolically. Let F be the set of integer valued functions defined on the integers. ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n

Proof. The indents work in my word processor, but I don't know why my indents didn't work here, so I used dashes.

First I want to prove that f is one to one. I'm going to try to write that symbollically. ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Assume x, y ∈ Z # x, y are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume first antecedent
- - Assume f(x) = f(y) # assume second antecedent
- - - Let z = f(x) = f(y)
- - - z ∈ Z # f is an integer valued function function
- - - f(f(x)) = f(z) = x # f is defined on the integers
- - - f(f(y)) = f(z) = y
- - - Then x = y
- - Then f(x) = f(y) ⇒ x = y
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)
Then ∀ x, y ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ (f(x) = f(y) ⇒ x = y)

Now f is one to one.

Assume f ∈ F, n ∈ Z # f, n are generic
- Assume f(f(n)) = n, f(f(n + 2) + 2) = n, f(0) = 1 # assume the antecedent
- - Assume n | 2 (n is even)
- - - Then ∃ x ∈ Z, n = 2x # definition of even
- - - f(f(2x + 2) + 2) = 2x = f(f(2x))
- - - f(2x + 2) + 2 = f(2x) # f is one to one
- - - f(2(x + 1)) = f(2x) - 2
- - - Let a_x = f(2x)
- - - a_(x + 1) = a_x - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0) = 1
- - - d = -2
- - - a_x = a_0 + dx = 1 - 2x
- - - f(2x) = 1 - 2x
- - - Then f(n) = 1 - n
- - Then n | 2 ⇒ f(n) = 1 - n
- - Assume ¬(n | 2) (n is odd)
- - - Then ∃ x ∈ Z, n = 2x + 1 # definition of odd
- - - f(f((2x + 1) + 2) + 2) = 2x + 1 = f(f(2x + 1))
- - - f(2(x + 1) + 1) + 2 = f(2x + 1) # f is one to one
- - - Let a_x = f(2x + 1)
- - - a_(x + 1) = a(x) - 2
- - - a_x forms an arithmetic sequence
- - - a_0 = f(2 * 0 + 1) = f(1) = f(f(0)) = 0 # f is one to one
- - - d = -2
- - - a_x = a_0 + dx = -2x
- - - f(2x + 1) = -2x
- - - Then f(n) = 1 - n
- - Then ¬(n | 2) ⇒ f(n) = 1 - n
- - Then (n | 2) ∨ ¬(n | 2) ⇒ f(n) = 1 - n
- - Then f(n) = 1 - n
- Then (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n
Then ∀ f ∈ F, ∀ n ∈ Z, (f(f(n)) = n ∧ f(f(n + 2) + 2) = n ∧ f(0) = 1) ⇒ f(n) = 1 - n