The article uses an intuitive approach trying to find a way to crack the halting problem.
But the truth is that halting dilemma is real and despite any attempt to "unwind" or "simplify" the control and data flows, there is a real barrier. It is in the math.
My favorite example: finding an odd perfect number. Euler stated: "Whether (...) there are any odd perfect numbers is a most difficult question". More recently, Carl Pomerance has presented a heuristic argument suggesting that indeed no odd perfect number should exist. [1]
Does it exist? Definitely. Somewhere in 10^300 range. What is the exact value? Nobody knows. You can write a program that finds an odd perfect number:
def odd_perfect_number():
n = 1
while True:
if sum(filter(lambda x: n % x == 0, xrange(1, n))) == n:
return "OK! I FIND IT!"
n += 2
Will this program ever complete?
Maybe. However nobody can say for sure. Avoiding recursion or some kind of groups won't give you any favor.
This is the halting problem in all of its glory.
[1] https://en.wikipedia.org/wiki/Perfect_number
But the truth is that halting dilemma is real and despite any attempt to "unwind" or "simplify" the control and data flows, there is a real barrier. It is in the math.
My favorite example: finding an odd perfect number. Euler stated: "Whether (...) there are any odd perfect numbers is a most difficult question". More recently, Carl Pomerance has presented a heuristic argument suggesting that indeed no odd perfect number should exist. [1]
Does it exist? Definitely. Somewhere in 10^300 range. What is the exact value? Nobody knows. You can write a program that finds an odd perfect number:
Will this program ever complete?Maybe. However nobody can say for sure. Avoiding recursion or some kind of groups won't give you any favor.
This is the halting problem in all of its glory.
[1] https://en.wikipedia.org/wiki/Perfect_number