Thoughts:
This week we talked about probably the coolest but most confusing topic in the whole class, halting program and computability.
- Halting Program.
A halting program (e.g. halt(f, i)) is a program that predict that the input f(i) will halt or not. And we proved it is impossible to implement this program. An imprecise way of explaining this is if there is a function that is running, we can't tell if it fall into an infinite loop or it's just on it's way producing an out put. For example a program has ran for 5 hours, we cannot say it won't halt since it ran for a long time. Maybe it will halt at 7 hours, maybe it will halt at 20 hours, maybe it will take a year, a century to halt. And then professor talked about Collatz conjecture as an example.
-Collatz Conjecture
Here are the explanation on wikipedia:
"Take any natural number n. If n is even, divide it by 2 to get n / 2. If n is odd, multiply it by 3 and add 1 to obtain 3n + 1. Repeat the process (which has been called "Half Or Triple Plus One", or HOTPO) indefinitely. The conjecture is that no matter what number you start with, you will always eventually reach 1. The property has also been called oneness."
It was Collatz, a student in University of Hamburg first came up in 1930, and then it became a open question since then. many mathematicians such as Shizuo Kakutani had working on it. But as Hungarian mathematician Paul Erdős says "Mathematics may not be ready for such problems.", no one were able to prove or disprove it. The lecture slice has a small mistake, modern day mathematicians have checked that the code will halt for every integer up to 2^60 in 2009, four times more than 2^58. And I tried to be a genius solving this historically hard question and gave up in 5 minutes. However, visualized graphs of that program are pretty cool.
Back to halt(h, i), during the lecture prof used navel_gaze(f) to prove that it is impossible to implement halt(h, i).
If we defined a function navel_gaze this way:
def navel_gaze(f):
while H(f, f):
pass
return 42 # meaning of life
consider
navel_gaze(navel_gaze), if the it halts, then
H(navel_gaze, navel_gaze) is false, which means
navel_gaze(navel_gaze) won't halt.
But if it doesn't halt, then
H(navel_gaze, navel_gaze) is true, then it will halt. Since both possible cases leads to contradictions, We cannot implement the function halt(). And we say that H(f, i) is computable.
- 42
In The Hitchhiker's Guide to the Galaxy by Douglas Adams, 42 is "The Answer to the Ultimate Question of Life, the Universe, and Everything". And the movie is pretty interesting.
