Genetic programming and the halting problem (2006) [video]

youtube.com

59 points·henning··9 comments

"Turing was wrong: the halting problem may be decidable after all! Selecting programs at random from the space of Turing-complete programs we show that almost all of them stop. Therefore, the answer of the Halting problem is "no", with probability 1."

Doesn't providing a single counterexample of a non-halting program prove them wrong?

Yeah I suspect this is a tongue in cheek (but still silly) title. The halting problem is not about probabilities at all.

If there's even one single program that cannot be proven to halt or not, that already makes the halting problem undecidable, regardless of the fact that an infinity of programs can be proven to halt / not halt.

This is equivalent to claiming that if you randomly sample from the real number line the probability of sampling a natural number is 0, therefore natural numbers can't exist.

(Of course I doubt the author(s) were making these claims in all seriousness).

There was this guy in college who claimed to be able to factor big primes. So we gave him the product of two. His nickname became Optimus Prime

I suspect you meant he claimed to be able to factor any number, not just primes? :)

One key thing she mentioned is the growth rate — you can have a fully mature 18 meter bamboo tree in as little as three years. I’m addition to it being both strong & flexible.

And, IIRC, bamboo tend to grow in dense groups— seems like growing bamboo for building material would be a good use of space.

Think this is the wrong thread?

No. Bamboo is genetically programmed to grow quickly; you cause it to halt by cutting it down.

;-)

Woops! Yup, I must have clicked on the wrong tab on my phone.

Reply on news.ycombinator.com