3 ms·
> It’s going to seem incredible, almost magical, but be assured you there are no tricks involved. The trick involved is: BitSequence.find is a naïve brute-forc
by mrmr1993 8y ago
> It’s going to seem incredible, almost magical, but be assured you there are no tricks involved.
The trick involved is: BitSequence.find is a naïve brute-force search, but the predicates only check n bits (for some n), and laziness ensures that at most n bits are generated.
We run into the expected problems if n is large, or there is no such n. For example,
func evenNumberOfOnesAtStart(_ s : BitSequence) {
return (s.atIndex(0) == .zero ||
(s.atIndex(1) == .one &&
evenNumberOfOnes(BitSequence { s.atIndex($0 + 2) })))
}
evenNumberOfOnesAtStart == evenNumberOfOnesAtStart
will never terminate. (Disclaimer: I don't write Swift.)
While it's nice to try smuggling in some mathematics at the end, I think a better conclusion for the article to draw is: if you ask a computer to do a brute-force search on some fixed number of bits, it will do it, even where has to compute this number of bits itself along the way.
- Spivak 8y agoI think there might be a clearer explanation. If a predicate only looks a finite number, n, of bits of a bitsequence then you can brute-force search the space containing the (2^n) sequences shorter than n. And a predicate can't possibly look at infinitely many bits of a bitsequence as the function which resolves that predicate would never terminate.
- mrmr1993 8y agoAgreed. (Although it's (2^m) sequences, where m is the largest index of the n.)