4 ms·
We're not talking about the size of single values, we're talking about the cardinality of the set of all distinct values of a given type. I.e. "How many differe
by rcthompson 8y ago
We're not talking about the size of single values, we're talking about the cardinality of the set of all distinct values of a given type. I.e. "How many different Strings are there?"
- saagarjha 8y agoYes, I'm aware of that. The set of all languages over a finite alphabet should be countably infinite, since you can list them all. For example, for the alphabet {0, 1} all your strings are just the binary representations of natural numbers, which is countable since ℕ is.
- dagw 8y agoIf you only allow arbitrarily long, but finite, strings then the set is countable. If you allow infinitely long strings then the cardinality of that set is uncountable. For a trivial example consider the string representation of every element in ℝ in the alphabet {0-9,.}
- saagarjha 8y agoYes, you're right; this is what I meant, and I see why my current wording is wrong.
- tomp 8y agoEach string is finite, its characters come from a finite set; that’s countably infinite (think of it as integers written in base Unicode). Bitsequences are infinitely long, so that’s uncountably infinite or continuity (think of it as real numbers between 0 and 1, written in binary).
- rcthompson 8y agoThe point of the original comment was that if you consider BitSequences to be of infinite length, then for consistency you also have to allow infinite-length strings. Otherwise you're ignoring the limitations of machine representation for one type but not the other, which is comparing apples to oranges.