News for hackers. Stuff that matters.
Re:Seemingly impossible functional programs (2007) by contravariant on Friday July 10, 2020 @08:17PM (#23798155)
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.

Re:Seemingly impossible functional programs (2007) by cvoss on Friday July 10, 2020 @08:33PM (#23798260)
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.
Re:Seemingly impossible functional programs (2007) by JadeNB on Friday July 10, 2020 @11:55PM (#23799330)
> 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.

Re:Seemingly impossible functional programs (2007) by thaumasiotes on Saturday July 11, 2020 @02:52AM (#23800149)
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].

Re:Seemingly impossible functional programs (2007) by JadeNB on Friday July 10, 2020 @11:54PM (#23799324)
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.
Re:Seemingly impossible functional programs (2007) by contravariant on Saturday July 11, 2020 @12:24PM (#23803289)
I did use the phrase decimal representations to avoid that exact issue.
Re:Seemingly impossible functional programs (2007) by JadeNB on Saturday July 11, 2020 @02:59PM (#23804749)
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.