3 ms·
He lost me when he started talking about the Halting Problem. How is checking all Swift.String or Swift.Int values equivalent to that? There are a lot of Swif
by ken 8y ago
He lost me when he started talking about the Halting Problem.
How is checking all Swift.String or Swift.Int values equivalent to that? There are a lot of Swift.Int values to check (2^64, on a 64-bit platform), and even more Swift.String values (every combination of characters up to that length), but simply being infeasibly slow to run on your Pentium "in a reasonable amount of time" doesn't mean it's an "impossible function to implement, and also equivalent to the halting problem". We could easily write a function to enumerate all Swift.Int values (though it might take 100 years to run).
He throws out the parenthetical remark "it’s best to think of Int as modeling the infinite set of all integers" without explanation. When you're discussing whether something is theoretically impossible or not, thinking of a finite set as equivalent to an infinite set is brushing over a pretty major distinction.
- joshuamorton 8y agoWith Int you may be right. But there are an infinite number of strings (and indeed every Turing machine may be represented as a String in swift), so it is indeed related to the halting problem.
- wtetzner 8y agoSwift strings don't have a maximum length? Are they nul-terminated?
- ken 8y agoSwift.String is composed of a finite set of symbols, with a finite maximum length. How can you create an infinite number of these? The article ignores the distinction in many places, but "String" in a Swift function means "the Swift.String type", not "an abstract string type like those used to represent Turing machine state".
- timjver 8y agoYou're not wrong, but the author's code does in no way rely on the fact that you could theoretically iterate over all the valid Int values in Swift, so it would have made no difference if the Int type was somehow truly infinite. And the author clearly acknowledges this: >it’s best to think of Int as modeling the infinite set of all integers