Hacker News new | ask | show | jobs
by kevinwang 1693 days ago
I find this very interesting, but I'm unable to understand it, so the result still seems impossible to me.

Can someone explain how find works if the predicate is something like: return true if and only if every other bit is 1

2 comments

The trick is that your predicate can’t be implemented in Haskell, because the predicate itself requires looking at infinitely many elements.
if a predicate depends on finitely many bits then you can exhaustively check whether it is total by enumerating all of it's possible inputs