2 ms·

I'm trying to follow you last example. It seems you are proving that for any computable function `f`, there is a number `n` such that f can be computed by never

I'm trying to follow you last example. It seems you are proving that for any computable function `f`, there is a number `n` such that f can be computed by never looking at more than the first `n` bits of the input? I thought that would fail for a simple function like "Does the stream include a 1", which takes finite time for any stream that includes a "1", but doesn't use a bounded prefix. I guess restricting the input this way somehow makes the set not open?

kmill 5y ago
Indeed, computable functions on binary streams have a uniform bound on how much of a stream they'll look at! "Does this stream include a 1" is not computable, since it won't halt on 00000.... The subset of streams that include a 1 is open, though. If you restrict to the subset of streams that include a 1, then computable functions might look at some unbounded amount of the input (example: is the value after the first 1 a zero? this is computable but takes unbounded time). This doesn't contradict anything because this subset is not compact. Here's another interesting application (not fully fleshed out here). An arbiter is a computable function that watches a stream of messages produced by a distributed system and decides whether the consensus reached is A or B. Suppose each process only sends messages from a finite set (they're TCP packets or something). The space of message streams is compact, so by the same argument the arbiter makes its decision within a fixed amount of time, independent of the message stream. If messages can be delayed or lost and there are at least two processes, then the arbiter has to always answer only A or B, since otherwise it would be possible to construct two message streams that have the same prefix, but impossibly the arbiter answers A for one and B for the other.

2 ms·

I'm trying to follow you last example. It seems you are proving that for any computable function `f`, there is a number `n` such that f can be computed by never

by thomasahle 5y ago

kmill 5y ago
Indeed, computable functions on binary streams have a uniform bound on how much of a stream they'll look at! "Does this stream include a 1" is not computable, since it won't halt on 00000.... The subset of streams that include a 1 is open, though. If you restrict to the subset of streams that include a 1, then computable functions might look at some unbounded amount of the input (example: is the value after the first 1 a zero? this is computable but takes unbounded time). This doesn't contradict anything because this subset is not compact. Here's another interesting application (not fully fleshed out here). An arbiter is a computable function that watches a stream of messages produced by a distributed system and decides whether the consensus reached is A or B. Suppose each process only sends messages from a finite set (they're TCP packets or something). The space of message streams is compact, so by the same argument the arbiter makes its decision within a fixed amount of time, independent of the message stream. If messages can be delayed or lost and there are at least two processes, then the arbiter has to always answer only A or B, since otherwise it would be possible to construct two message streams that have the same prefix, but impossibly the arbiter answers A for one and B for the other.