6 ms·

I think I have a half-baked understanding of what's going on here. Let me talk through it. Take a function f : unit_interval -> bool. I believe that if there i

by cvoss 6y ago

I think I have a half-baked understanding of what's going on here. Let me talk through it. Take a function f : unit_interval -> bool. I believe that if there is no bound on the execution time of f, then f must not be a total function. (So conversely, if f is total, then it has bounded execution time, and is therefore only considering prefixes of the digit streams of up to some bounded length. From there, searching for an example input x s.t. f(x) = true is easy.) Naively, it would seem plausible that there exists a total function which, nevertheless, takes longer and longer to run on a particular sequence of inputs. So let such a sequence be given, where the runtime of f(x_i) tends to infinity, even though it is finite for each x_i. But from topology, we know that a sequence of points in a compact space, like the unit interval, has a convergent subsequence. The interesting thing happens when you look at f(y) where y is the limit point of such a subsequence. It is the case that as i increases, x_i and y increasingly look the same for longer and longer prefixes of their decimal (binary) expansions. Therefore, f has to do more and more work to tell apart x_i and y, which gives us an argument that there is no bound on the runtime of f(y); i.e., f doesn't terminate for that particular input. (Except, you have to get nitpicky about redundant representations of reals like 0.0099999... vs 0.010000..., but we can always choose the representation of y that suits us: the one that looks more like the x_i's.)

contravariant 6y ago
Yeah I think there are some small problems with your argument, unless it was only meant to illustrate the idea. For the sake of argument let's say we simply input both decimal representations of each number. A program that simply tries to find the first decimal that isn't 9 for a number in [0,1] would take an arbitrary amount of time, but is still total because 1 can be identified in a single step. The problem here is that while the function is total it isn't continuous and so the compactness of the topology is irrelevant. As far as I can tell the article uses some trickery to ensure that computable functions _are_ continuous, in which case it does work.
- cvoss 6y ago
  You're right, it's not a precise line of reasoning. I was considering only computable functions (else "runtime" isn't a meaningful concept) and treating the input domain as actually being the Cantor space, where 0.9999... and 1.0000... are actually distinct values. I just found it helpful to think about the Cantor space in terms of the unit interval.
  - JadeNB 6y ago
    > the Cantor space, where 0.9999... and 1.0000... are actually distinct value What do you mean here? The Cantor set is a subspace, not a cover, of [0, 1]; values in the Cantor set that are the same in [0, 1] are also the same in the Cantor set.
    - thaumasiotes 6y ago
      Sure, the Cantor set is the set of real numbers in [0,1] with trinary expansions that do not contain 1 at any point. A Cantor space is any set that can be mapped to (and from) the Cantor set. The Cantor space is the set of infinitely long bitstrings; instead of a trinary number 0.200220222200..., you'd conceive of the same entity as the string "100110111100...". The mapping is pretty obvious. 0.99999... and 1.0000... are neither of them bitstrings, so it's not really clear what cvoss was thinking of. But it's certainly true that "0999999..." and "1000000..." are distinct strings. Going back to the Cantor set, you'd usually represent 1 as 0.22222222... for obvious reasons of consistency (that is the only format matching the representation of the rest of the set). It would be weird to represent it as 1.000000000...; that would look like you were considering the left end of the Cantor set in [1,2] rather than the right end of the Cantor set in [0,1].
- JadeNB 6y ago
  The example you suggest has a subtle issue, since the number 0.999… is the number 1; so a program fed numbers (rather than, say, decimal strings, in which case the domain is no longer [0, 1]) cannot meaningfully distinguish the former from the latter, and hence cannot terminate on 1.
  - contravariant 6y ago
    I did use the phrase decimal representations to avoid that exact issue.
    - JadeNB 6y ago
      Right, but then the domain isn't [0, 1] any more (it's got lots of double points, like 0.999… and 1, and 0.8999… and 0.9 etc.), and your function doesn't terminate on input 0.999…. I guess you meant to feed only the terminating decimal if there was one? Then, I agree, this is a good illustration of how a discontinuous function can violate all the nice properties on which the mathematics of functional programming relies.

by cvoss 6y ago

contravariant 6y ago

Yeah I think there are some small problems with your argument, unless it was only meant to illustrate the idea. For the sake of argument let's say we simply input both decimal representations of each number. A program that simply tries to find the first decimal that isn't 9 for a number in [0,1] would take an arbitrary amount of time, but is still total because 1 can be identified in a single step. The problem here is that while the function is total it isn't continuous and so the compactness of the topology is irrelevant. As far as I can tell the article uses some trickery to ensure that computable functions _are_ continuous, in which case it does work.

cvoss 6y ago
You're right, it's not a precise line of reasoning. I was considering only computable functions (else "runtime" isn't a meaningful concept) and treating the input domain as actually being the Cantor space, where 0.9999... and 1.0000... are actually distinct values. I just found it helpful to think about the Cantor space in terms of the unit interval.
- JadeNB 6y ago
  > the Cantor space, where 0.9999... and 1.0000... are actually distinct value What do you mean here? The Cantor set is a subspace, not a cover, of [0, 1]; values in the Cantor set that are the same in [0, 1] are also the same in the Cantor set.
  - thaumasiotes 6y ago
    Sure, the Cantor set is the set of real numbers in [0,1] with trinary expansions that do not contain 1 at any point. A Cantor space is any set that can be mapped to (and from) the Cantor set. The Cantor space is the set of infinitely long bitstrings; instead of a trinary number 0.200220222200..., you'd conceive of the same entity as the string "100110111100...". The mapping is pretty obvious. 0.99999... and 1.0000... are neither of them bitstrings, so it's not really clear what cvoss was thinking of. But it's certainly true that "0999999..." and "1000000..." are distinct strings. Going back to the Cantor set, you'd usually represent 1 as 0.22222222... for obvious reasons of consistency (that is the only format matching the representation of the rest of the set). It would be weird to represent it as 1.000000000...; that would look like you were considering the left end of the Cantor set in [1,2] rather than the right end of the Cantor set in [0,1].
JadeNB 6y ago
The example you suggest has a subtle issue, since the number 0.999… is the number 1; so a program fed numbers (rather than, say, decimal strings, in which case the domain is no longer [0, 1]) cannot meaningfully distinguish the former from the latter, and hence cannot terminate on 1.
- contravariant 6y ago
  I did use the phrase decimal representations to avoid that exact issue.
  - JadeNB 6y ago
    Right, but then the domain isn't [0, 1] any more (it's got lots of double points, like 0.999… and 1, and 0.8999… and 0.9 etc.), and your function doesn't terminate on input 0.999…. I guess you meant to feed only the terminating decimal if there was one? Then, I agree, this is a good illustration of how a discontinuous function can violate all the nice properties on which the mathematics of functional programming relies.