3 ms·

Pure functional programming? Yeah. But those aren't magic. Whenever you have conditional branching, the halting problem reintroduces itself. (def (collatz-

• steveklabnik 13y ago
  Total functional programming is different than purely functional programming: http://en.wikipedia.org/wiki/Total_functional_programming http://en.wikipedia.org/wiki/Total_functional_programming
  • vbuterin 13y ago
    Ah okay, interesting, thanks for the link. So it's basically a maximally powerful non-Turing-complete language. I would argue that the section in our v2 whitepaper on non-Turing-complete languages still covers the fallacy behind that: you can still have exponential blowup, so you still need a concept of maximum steps, but then once you have a concept of maximum steps there's little benefit to restricting the programming language.
• emn13 13y ago
  In essence, it's just recursion that's only allowed when the recursive input is in some sense strictly "smaller" than its input and therefore necessarily terminates if the input is of finite size and cannot drop below zero. However, it's not magic: it's not automatically trivial to generate such a proof of termination (I'd assume there exist definitely terminating programs for any given proof system that cannot be proven to terminate in that formalism), and it may be a moot point since a slow enough algorithm is for all intents and purposes non-terminating...