Not really sure what week's material needs to be covered at this point. I've been a bit scatterbrained recently with computer science, and today I really felt that way as Danny discussed infinite sets and I just sat there thinking, "Whaaaaaaaaaaat?"
I mean, if there are infinite natural numbers in the set of natural numbers, and we can produce all rational numbers by dividing each natural number by every other natural number (since that would produce every fraction possible), wouldn't that mean that the size of the set of rational numbers is equal to the size of the set of natural numbers squared? This whole diagonal-function thing seemed to come out of thin air to me.
I think I have one more week before I have to formally outline a problem-solving episode, so let's procrastinate on that front a little longer.
I have to say I am curious to see how CSC236 will go, given how theoretical our discussions are becoming. Computability is causing me a bit of a headache on that front. The use of "halt" appears to be for any situation in which the function stops running - it returns or it breaks or it has an error or exception. Not sure if that's right....
If such is the case, then it seems like there are definitely interesting implications to such a problem of what can a computer compute or fail to compute. Once again, we're using proofs to solve those kinds of questions.
What I've been wondering about is as follows: is it possible to write a piece of code that you can know if it's looping forever or if it's just taking a while?
I know I've had times where I've accidentally created infinite while loops in the past, but it's usually pretty obvious that the while loop is the problem and that the rest of the code executes normally.
Say my code was:
f(n):
while True: pass
return n
Then it's obvious that my code will either loop forever or return right away. But does this prove anything? Not really, except that f() loops forever for all n.
The problem is about the bits of code that could just be taking a long time. It's like Schrödinger's Cat in a sense: we cannot be sure based on our models of whether the code is "dead" (reaching some eventual end) or "alive" (looping forever) -- although I can't imagine anyone has posited these bits of code are both looping forever and eventually going to end, so I guess it's a bad analogy.
But again, if we had a function which looped forever, then any calls on that function would loop, and any calls on those calls would loop. So we can't simply pass it to another function to call.
Suppose we did know that a function ran for a really long time n. Then no matter what we add to the function, aside from infinite loops, the function will always run for some finite amount of time. Another assignment might make it n+1, or a search through the elements could make it n*n. But so long as we have a finite number, we can predict how long it should take, right?
So then we should be able to look at functions and identify the step which causes the question of infinite loops. If we are able to evaluate smaller parts to finite amounts, then we can determine which part makes the function non-computable. For f(n), we know that the "while True" causes the problem... we could make it something else which would have the same effect.
g(n):
while abs(n/2) > 0: return g(n/2)
return n
Unless n is 0, g(n) will loop forever, which we know because of how the set of real numbers works. Half of something is always a real number, so we are always going to end up with a smaller real number that approaches 0 but never quite gets there.
If we take the limit, we can see that as the denominator approaches infinity (being 2^n), abs(n/2) gets closer and closer to 0 but never reaches it unless n is assigned to be 0.
And there are an infinite number of powers of 2 after all, as there are infinitely many integers. Oh boy.
No comments:
Post a Comment