3 ms·
It works for any decidable/recursive predicate on bit sequences, i.e. one that is guaranteed to halt for any input. `and` on an infinite bit sequence is not gu
by wz1000 8y ago
It works for any decidable/recursive predicate on bit sequences, i.e. one that is guaranteed to halt for any input.
`and` on an infinite bit sequence is not guaranteed to halt because it is co-recursively enumerable, i.e. it will reject bit sequences that contain `False`, but it will not halt on bit sequences that contain only `True`, since to verify that a bit sequence only contains `True`, you have to check all elements of the sequence.
In ghci,
> and $ repeat True
<doesn't terminate>
> and $ (replicate 10000 True) ++ (False: repeat True)
False
- repsilat 8y agoI noticed my post missed the point a bit... I was thinking about functions that check properties of bit sequences, not functions that check properties of predicates on bit sequences. I get how it works now, thanks. Wish I could edit/delete my old post :-/. Just to check my understanding: a terminating program that decides bit sequences will have - a maximum number of bit checks it will make regardless of input, and - a maximum bit index it will access regardless of input, and even - a maximum running time (measured however).