Hello readers!!
I hope most of you have survived last week's cold weather and are enjoying this week's much more enjoyable temperatures!
Last week we were introduced the Turing Machine, which sounds really cool (and it is), but it isn't exactly what it sounds like.
For one, the Turing Machine isn't actually a machine. In fact, it isn't even a tangible object! It was something a thoughtful man named Alan Turing came up with, even before computing machines were even made (or were at least available to most people)!! Secondly, it doesn't exactly set out to 'do' anything. It is rather something that was made to prove what we can't do (or to be more specific, compute).
So what exactly was Turing trying to find out with his not-actually-real machine? He was trying to find the limits of what he thought mechanical machines or nowadays, computers could ever compute. "If you're thinking, oh man, computers can do everything!! Just look at those cool websites like WolframAlpha! It helps me check all my calculus homework." Well, my dear friend, just because there seem like there are infinitely many computable functions out there, it doesn't mean that there aren't any that can't be computed!
As a simple example we learned in class, we can define functions as halting or not halting (not halting refers to functions that go in an infinite loop and are therefore uncomputable).
Let's look as this code:
def cute_puppy(f):
while halt(f, f):
pass
return 'lost_puppy'
Looking at this function, we consider the input cute_puppy and decide if it will halt or not. Lets say we decide that cute_puppy(cute_puppy) halts, which means that the while loop condition will be True, which means that we enter the loop, only to pass and go back to the while loop, which is True, which means that we enter the loop and pass, and then go back to the the while loop?!?!?!?! This means that the function doesn't really halt, since we are infinitely stuck in that while loop! (side note: which isn't so bad, if you've ever gone to one of those websites that showcases cute animals, which feels like an infinite loop of awesomeness)
Ok then, you say, why don't we decide that cute_puppy(cute_puppy)does not halt! Then surely this is true! Let's give it a try: so if we say that halt(cute_puppy, cute_puppy)is False, then the loop condition is not fulfilled and we return the statement lost_puppy............ but wait, our function just halted!! So our statement has just been contradicted once more!!
While I do apologize for the many exclamatory marks all over those preceding 2 paragraphs, I just wanted to show how crazy it is to have thought all my life that probably everything could be solved by a computer, only to learn that something as simple as this has already beaten the computer at its own game. This concept is really cool to me, and I will be looking forward to learning all about halting functions and the limits to what computers can do!
Hope you all learned a little today or at least had a little fun reading this and as always have a nice week!
Lana :)
I hope most of you have survived last week's cold weather and are enjoying this week's much more enjoyable temperatures!
Last week we were introduced the Turing Machine, which sounds really cool (and it is), but it isn't exactly what it sounds like.
For one, the Turing Machine isn't actually a machine. In fact, it isn't even a tangible object! It was something a thoughtful man named Alan Turing came up with, even before computing machines were even made (or were at least available to most people)!! Secondly, it doesn't exactly set out to 'do' anything. It is rather something that was made to prove what we can't do (or to be more specific, compute).
So what exactly was Turing trying to find out with his not-actually-real machine? He was trying to find the limits of what he thought mechanical machines or nowadays, computers could ever compute. "If you're thinking, oh man, computers can do everything!! Just look at those cool websites like WolframAlpha! It helps me check all my calculus homework." Well, my dear friend, just because there seem like there are infinitely many computable functions out there, it doesn't mean that there aren't any that can't be computed!
As a simple example we learned in class, we can define functions as halting or not halting (not halting refers to functions that go in an infinite loop and are therefore uncomputable).
Let's look as this code:
def cute_puppy(f):
while halt(f, f):
pass
return 'lost_puppy'
Looking at this function, we consider the input cute_puppy and decide if it will halt or not. Lets say we decide that cute_puppy(cute_puppy) halts, which means that the while loop condition will be True, which means that we enter the loop, only to pass and go back to the while loop, which is True, which means that we enter the loop and pass, and then go back to the the while loop?!?!?!?! This means that the function doesn't really halt, since we are infinitely stuck in that while loop! (side note: which isn't so bad, if you've ever gone to one of those websites that showcases cute animals, which feels like an infinite loop of awesomeness)
Ok then, you say, why don't we decide that cute_puppy(cute_puppy)does not halt! Then surely this is true! Let's give it a try: so if we say that halt(cute_puppy, cute_puppy)is False, then the loop condition is not fulfilled and we return the statement lost_puppy............ but wait, our function just halted!! So our statement has just been contradicted once more!!
While I do apologize for the many exclamatory marks all over those preceding 2 paragraphs, I just wanted to show how crazy it is to have thought all my life that probably everything could be solved by a computer, only to learn that something as simple as this has already beaten the computer at its own game. This concept is really cool to me, and I will be looking forward to learning all about halting functions and the limits to what computers can do!
Hope you all learned a little today or at least had a little fun reading this and as always have a nice week!
Lana :)
Comments
Post a Comment