141–149 of 149 posts
1. No closed form solution for polynomials of degree 5 or larger.
2. 4-color theorem for painting planar graphs.
There are lots more counter-examples: not 0, not 1 and probably not infinite. Probably some other number of counter-examples.
If you were making a paint the map algorithm - your data structure should assume you need 0, 1 or infinite colors, instead of no more than 4? Is that the point of the principle?
Earlier quoted context omitted.
You absolutely can justify infinity - even if your real system can't represent numbers larger than X, you can't guarantee that won't change in the future. For example, in C, integers have minimum sizes, but no maximum. We're lucky nobody ever went, "well, our PDP-11 can only go up to 2^16, so let's set the maximum there." That's not to say it doesn't make sense to limit things after a certain point, but you'd damn we…
I can guarantee it’ll never be able to support infinity records. I can also guarantee that most data structures can’t even support a googol of records and never will. Some won’t ever support a quintillion records due to complexity, and quantum won’t fix all of those. There may be structures that support this, but they aren’t the ones we use today. And the reason is that complexity theory is on shaky ground these days…
n^3/2 * log(n)²
The time required for 1000n is 3 million times more than n. If anyone makes a computer that is 6 orders of magnitude faster than current computers, none of us here will be alive to see it.
While this has some theoretical merit, IME, limits are quite useful to catch bugs (or prevent degenerate cases). For example I was recently working on a permissions system wherein there can be members of groups. I set a reasonable limit on the size of a group based on a maximum of actual usage and what I could foresee being reasonable. A few days later, this limit was triggered, and I got a bug report. But it turned…
If there is a loop, we will hit the limit while evaluating the cycle because it’s a DFS. With a BFS we could hit the limit in a sibling of the problematic node.
Scheduling budgets are how most people avoid the halting problem. You set a fixed multiple of expected halting time and work hard to make sure that’s your p99 time instead of your p75 time, and stop trying to violate core principles of computational theory.
Earlier quoted context omitted.
You absolutely can justify infinity - even if your real system can't represent numbers larger than X, you can't guarantee that won't change in the future. For example, in C, integers have minimum sizes, but no maximum. We're lucky nobody ever went, "well, our PDP-11 can only go up to 2^16, so let's set the maximum there." That's not to say it doesn't make sense to limit things after a certain point, but you'd damn we…
I can guarantee it’ll never be able to support infinity records. I can also guarantee that most data structures can’t even support a googol of records and never will. Some won’t ever support a quintillion records due to complexity, and quantum won’t fix all of those. There may be structures that support this, but they aren’t the ones we use today. And the reason is that complexity theory is on shaky ground these days…
> Forty years and six orders of magnitude ago we treated a bunch of operations as constant , which is a clever fiction that is blatantly obvious now,but some of you knuckleheads continue to not look at. Most C terms are in fact stair-stepped log(n). Every time log(n) doubles and crosses a threshold, the cost of the operation doubles, and therefore is in log(n), not C.
Memory latency hasn't really budged in 25 years and is significantly faster than it was 40 years ago.
Pointers have gotten bigger, but they're not that big compared to data and they're only one notch away from the maximum you could ever use in a single computer.
Where are we seeing these slowdowns?
> I can also guarantee that most data structures can’t even support a googol of records and never will. Some won’t ever support a quintillion records due to complexity
A B-tree will do fine.
> Memory access, as it turns out, is sqrt(n)
Not in real single computers.
And if our baseline is 1983 latency, it would take more than unrealistic amounts of circuits and size for the speed-of-light delays to drag modern tech down to equal it, let alone be worse.
I agree that actual infinity is impractical, but “zero, one, and out of memory” gives the wrong idea, because it implies you might limit things to the amount of memory currently available or available soon. "Infinity" is better at getting across the idea that your code is not allowed to bake in any limits.
While this has some theoretical merit, IME, limits are quite useful to catch bugs (or prevent degenerate cases). For example I was recently working on a permissions system wherein there can be members of groups. I set a reasonable limit on the size of a group based on a maximum of actual usage and what I could foresee being reasonable. A few days later, this limit was triggered, and I got a bug report. But it turned…
Sure, this is why code designed by ZOI rule has those straight forward test cases: none, one, some, many aaaand crash (at most).
and for safeguard of correct use (limits as undefined behaviour) many languages have assertions.
Earlier quoted context omitted.
I want to say, INT_MAX, but I know what you mean. It has been useful that the value varies by implementation (and even by compiler flag, on occasion).
I think you both need to watch some YouTube math videos on what exactly infinity means. As Everyday Maths put it, it’s not “count until you can’t count anymore and then add one to the number”. That’s the sort of wrong frame of thinking that makes you think that an infinite pile of hundred dollar bills is worth more than an infinite pile of one dollar bills. They are both worth $infinity. We don’t have any algorithms…
When somebody says "this algorithm is unbounded" they of course don't mean that they've changed the laws of the universe to allow for an infinite array of memory that it can work with. They just mean that if you could do that, it'd work.
As an example: `while (node) node = node->next;` (in C, where `node`'s type defines a reference to `next` of the same type) will traverse an unbounded list. It will work just as well for zero nodes, one node, a dozen nodes, a billion nodes, and so on, as the number of nodes approaches infinity. Obviously it is impossible for you to ever create a computer with an unbounded amount of memory, but computer scientists can talk about algorithms the same way mathematicians can talk about what `f(x)=x^2` at infinity.
No mathematician, with the knowledge we have now, would ever say, "It's unreasonable for us to talk about infinity. That's simply not possible, ever, now or in the future, so let's limit things at 999,999,999,999,999,999,999,999,999." We settled this debate back in the 1600s.
Earlier quoted context omitted.
The principle applies to all kinds of structures. For example a common way to implement a generic tree that respects this rule is to model each node with exactly one parent and any number of children. My statement instead is that you may have legitimate reasons to want exactly one parent and from zero to two children, but not more.
What would be the use case of such a tree?
Earlier quoted context omitted.
What would be the use case of such a tree?
An Abstract Syntax Tree, where each node can have zero children (e.g. a literal value), one child (unary operator like 'Not') or two children (a binary operator like +).
Earlier quoted context omitted.
An Abstract Syntax Tree, where each node can have zero children (e.g. a literal value), one child (unary operator like 'Not') or two children (a binary operator like +).
And what exactly is the benefit of restricting such a tree to two children? Why not just allow an arbitrary amount of children and then only use it with 0,1,2? After all, you might later want to extend the language.