More bounding box blatherskeit

The previous definition of bounding box, or something mildly similar, could also arise from adding two additional elements to the domain of `⊴` — call them `⊴_bot` and `⊴_top` — which act respectively as a global infimum and supremum on `⊴`. These elements have a natural representation in `bbb F^n` (where `bbb F` is the set of IEEE floating-point numbers, of whatever precision is relevant) as, respectively, {-Inf, -Inf, ... -Inf} and {+Inf, +Inf, ... +Inf}.

This would imply the existence of semi-infinite bounding boxes extending either positivewards or negativewards on all axes, as well as the existence of the "world box" as the `sube`-supremum. However, the null box would still not be a bounding box under this definition; and the semi-infinite boxes don't have much use for, er, actually computing the bounding boxes of objects or sets. (The world box is at least a useful initial value for foldr `^^`!)

However, in vector spaces constructed as products of sets with with minimal and maximal elements — such as `[0, 2^{:2^{:n:}:}-1] nn NN` or the aforementioned `bbb F` — the local equivalent of `⊴` is already a bounded lattice, naturally yielding the `sube`-supremum as a bounding box in that space without defining it specially.

My initial definition — refined from the above `{⊴_bot, ⊴_top}`-conjoinment, which was itself refined into the definition in the previous entry — was closer to the actual final representation. Perhaps it would be more natural to study the behaviour of posets of pairs of points from lattices, like the representation itself, than to consider "boxes" to be actual delimited sets of points?

Bounding boxes

Select some fixed `n` and basis `\vec{e_i}, 1 lt i le n` of `RR^n`.

Define a relation `⊴` on points in `RR^n` such that `a ⊴ b` iff `forall i: (a.p_1 * \vec{e_i}) le (b.p_1 * \vec{e_i})`. Then (`RR^n`, `⊴`) is a poset, and in fact is also a lattice: the meet `a ^^ b` is merely the point `sum_{i=1}^n [ \vec{e_i} * max(a * \vec{e_i},b * \vec{e_i})]`, and the join is the same, with `min` substituting for `max`.

Let a bounding box be a set of points `B sube RR^n` such that a point `p in RR^n` is in `B` iff `vvv B ⊴ p ⊴ ^^^ B`. Intuitively (using the standard basis for `RR^n`), this is an axis-aligned closed box. A bounding box is uniquely defined by its `⊴`-infimum and `⊴`-supremum. (Note that these two points may be equal if `B` is the singleton set containing only that point; this is a perfectly legal bounding box.)

The relation `sube` defines a poset on the set `bbb B` of bounding-boxes, simply because it also defines one on the powerset of `RR^n`. We may use `sube` to extend `bbb B` into a join-semilattice: the join of two boxes `A` and `B` is the box defined by the `⊴`-infimum and `⊴`-supremum of `A uu B`.

The join is not always in `bbb B`, but we can extend `bbb B` to a complete lattice `bbb B^+` by adding two additional special bounding boxes not defined by their `⊴`-infimum and `⊴`-supremum: the nil box `bot = O/` and the world box `top = RR^n`. Then `(bbb B^+,sube)` is a proper lattice, in which the join is still defined as above (with global supremum `top`), and the meet is merely the intersection. Technically only `bot` is needed to make `bbb B^+` a lattice, but the inclusion of `top` makes it a bounded lattice, which is useful.

---

From a practical perspective, a bounding box may be conveniently represented as a pair of `n`-tuples of IEEE floats. Naively it might appear that we need an additional two bits — one to mark a degenerate case, and the other to distinguish between the two such — but with a small amount of cleverness in the representation, we can avoid both the additional two bits and the need for any special logic in the implementation of meet, join, or containment-of-point.

Specifically, we represent `top` as the pair of `n`-tuples `(-infty,-infty,...,-infty),(+infty,+infty,...,+infty)`, and `bot` as any pair `(a,b)` such that `a⋬b`, possibly with a canonical form `(+infty,+infty,...,+infty),(-infty,-infty,...,-infty)`. The large class of representations of `bot` makes equality testing slightly more difficult, but equality is a much rarer operation to perform on bounding boxes than meet, join, and containment. The natural implementations of binary meet on nondegenerate boxes (taking the min of each element of the left two tuples, and the max of each element of the right two), binary join (as meet, with max and min reversed), and containment-of-point (left[i] <= point[i] && point[i] <= right[i] for all i) naturally work with these as well.

Note that if we are working with integer boxes instead of floating-point, we cannot typically use `infty` as a value. However, most applications for integer bounding boxes involve an implicit universe of discourse (the size of the screen or what-have-you), and where this does not hold, -MAX_INT and MAX_INT will probably still do in practice.

Novikovian Computation (2/2)

(continued from previous post)

Let's simplify and generalize: if the communications channel c has `b` bits, and there are `a` non-paradoxical answers, then (absent NSP) the probability of receiving a valid answer, `P(A_v)`, is `(1-epsilon) a/2^b`; the probability of an invalid answer, `P(A_{stackrel ~ v})`, is `(1-epsilon) {:(2^b - a):}/2^b`, and the probability of external failure, `P(_|_)`, is still `epsilon`. Note that, as required, `P(A_v) + P(A_{stackrel ~ v}) + P(_|_) = 1`, as these three exclusive possibilities make up the entirety of the event space.

In the presence of the NSP, however, the probability function `P_N(*)` is different: `P_N(A_{stackrel ~ v}) = 0`. For convenience, let `bar{:A_{stackrel ~ v}:} = A_v uu _|_` be denoted by `C` (for consistent).

The NSP essentially gives us that, for any event-set `E sube C`, `P_N(E) = P(E|C)`. We can therefore compute `P_N(E)` by Bayes' theorem: `P_N(E) = P(E|C) = {:P(C|E)P(E):}/{:P(C):}`. Of course, `P(C|E) = 1`; so after some mild algebra, we have`P_N(A_v) = {:a (1-epsilon):}/{:a (1-epsilon) + 2^b epsilon:}`, `P_N(_|_) = {:2^b epsilon:}/{:a (1-epsilon) + 2^b epsilon:}`.
If we have a reasonably reliable system, such that `epsilon ≪ 1`, these will basically be `{:a:}/{:a + 2^b epsilon:}` and `{:2^b epsilon:}/{:a + 2^b epsilon:}` respectively. Note that the probability of failure goes up exponentially with the number of bits being communicated and tested (assuming `a` remains constant as `b` increases). For Novikovian computation to be useful, we must have `a > 2^b epsilon`. (Recall that `a` is a small integer, probably on the order of 1 or 2, and definitely bounded above by `2^b`.)

Now suppose multiple time-loop-logic computational apparatuses exist (say, `n` of them), and are all executing problems concurrently. These are not discrete systems, because the probability that two apparatuses `c_1` and `c_2` will fail is not quite independent: for example, a relatively nearby star could suddenly go Type Ia supernova, flooding the solar system with ionizing radiation and thereby destroying all the apparatuses (and quite incidentally all life on Earth).

For the single-system case, divide `_|_` into `_|_ _ L` (local failure, independent) and `_|_ _ G` (global failure), with NSP-less probabilities `epsilon_L` and `epsilon_G` respectively (`epsilon_L + epsilon_G > epsilon`, since there is some overlap). Then, our consistent set `C` is `_|_ _ G + prod_{:i=0:}^n(_|_ _ {:L_i:} + A_{:v_i:})`, so we have`{:(P(C),=,epsilon _ G + (1-epsilon_G)prod_{:i=0:}^n(epsilon_{:L_i:} + (1-epsilon_{:L_i:})a/2^b)),(,=,epsilon _ G + (1-epsilon_G)1/2^{:bn:}prod_{:i=0:}^n(2^b epsilon_{:L_i:} + (1-epsilon_{:L_i:})a)):}`and therefore`P_N(_|_ _ G) = P(_|_ _ G|C) = epsilon _ G / {: epsilon _ G + (1-epsilon_G)1/2^{:bn:}prod_{:i=0:}^n(2^b epsilon_{:L_i:} + (1-epsilon_{:L_i:})a) :}`.The term on the right of the numerator is bounded above by `1/2^{:bn:}prod_{:i=0:}^n(2^b epsilon_{:L_i:} + a)`, which in the case of useful computation is itself bounded above by `1/2^{:bn:}prod_{:i=0:}^n(a + a) = 2a^n/2^{:bn:} = 2(a/2^b)^n`. This clearly goes to zero in the limit as `n` increases.

Therefore we have `lim_{:n rarr infty:} P_N(_|_ _ G) = epsilon _ G / epsilon _ G = 1`, or, in plain English:

Theorem. As the number of useful Novikovian computers in the world increases, the probability of apocalypse nears certainty.

See also the Fermi paradox, and excuse me while I go make an eschaton tag.

---

Edit 2009-03-13: Fixed typo in Bayesian restatement; adjusted formatting; eliminated references to `F`.

Novikovian computation (1/2)

... or, "why time loop logic will almost surely not be developed". (This is not quite correct: see the end result.)

The Novikov self-consistency principle states that the probability of a paradoxical event is zero. This is generally only relevant when closed timelike curves come into play.

For a concrete example, let's suppose I have a time machine, and that I intend to go back in time to shoot my own grandfather. Or Hitler, if you prefer. Now obviously, even in the absence of the NSP, I have a certain chance of failing to do so, for any of several reasons:

• my time-machine may fail to operate correctly;
• my gun may fail to operate correctly;
• I may have a sudden attack of conscience or sanity or heart;
• I could be caught by the police (in either time period);
• I could be intercepted by the Hounds of Tindalos;
  
• I might successfully shoot my grandfather but fail to kill him, explaining the shortness of breath that had always plagued him;
• I might shoot and kill someone that happened to look like my grandfather, and return to the future incorrectly believing myself successful; or
  
• something else.

In a universe in which the Novikov self-consistency principle holds, the chances of the above are effectively increased significantly: I cannot succeed in the attempt any more than I can fly by flapping my arms. If all predictable sources of failure have been ruled out, an unpredicted one will emerge.

So let's consider that briefly in the context of time loop logic:

Note that if N is itself prime, i.e., there is no such prime F ≠ N, then some event will prevent the execution of step 3 that receives the value F from the future.

Assume for the sake of concreteness that the endochronic communications channel c mentioned in the article carries 32 bits of information, and that the base probability of failure due to an external event is `epsilon`. Note also that N has `omega(N)``-2` prime factors. Then, in the absence of the NSP, the probability of receiving a valid `F` is `{:(omega(N)-2)*(1-epsilon):} / 2^32`; the probability of receiving an invalid `F` is `{:(2^32 - (omega(N)-2))*(1-epsilon):} / 2^32`; and the probability of external failure is of course `epsilon`.

(continued in next post)

---

Edit 2009-02-12: corrected count of prime factors.

On commonly-used magic systems (5/?)

I'll have to retract my earlier statement: the element N of non-elemental spells is the unique element such that for all elements E and all targets t∈T, D(E,t) = D(E,t) * D(N,t) — or, equivalently, for which every element is a hybrid element of itself and N. This is less restrictive than the former statement (t∈T, D(N,t) = 1); it is equivalent thereto iff * is associative and invertible on some extension of R. (Which is exceedingly rare, as R will usually include 0 to indicate that an enemy is immune to an element.) This allows enemies to be immune to (via, e.g., antimagic field) or reflective of (via, e.g., Reflect) all magic.

Surprisingly, by this definition, status-inflicting spells are rarely non-elemental: while in some cases (such as Skies of Arcadia) the status magics are explicitly folded into the obvious elemental system, more often certain classes of enemies will simply be exempted from them. (When was the last time you saw a boss that was vulnerable to an instant-death attack? — okay, other than Revive Kills Zombie. And no, the Vanish/Doom trick doesn't count: Vanish changes the value of t the same way Reflect does.)

Exercise for the reader: the class M of Megido ("Almighty-element") spells, from the Persona series, does have a uniform coefficient of effectiveness of 1 for all targets — even those with Makarakarn (the Shin Megami Tensei equivalent of Reflect) cast on them. Is M⊆N?

---

(Edit 2009-02-19: fixed equivalency condition. I think.)

On commonly-used magic systems (4/?)

Dual-elemental magics are relatively uncommon: I'm not offhand aware of any in any of the Final Fantasy games, for instance, although Chrono Trigger has the Antipode series of Double Techniques. Part of this is because it may require special handling: what happens if an enemy is weak to one of the elements, but strong against another? The dissection described in the previous post is silent on the matter effectively assumes that this does not happen, and that identical coefficients do not stack.

The structure we have so far isn't quite enough to describe the case where they do stack. If stacking is to take place, you'll have to define a multiplication operation on R; this is easy if R⊆ℝ, but somewhat less so in, e.g., Persona 3, where R = {2, 1, 0.5, 0, -1, Reflect}. (Just making Reflect override everything [∀r∈R: Reflect * r = Reflect = r * Reflect] would work, but it would be a design decision. P3 evades the issue entirely: it has no multielemental spells.) Then an element h is a hybrid element iff there exists some set of elements V = {v₁, ... v_n} such that for all t∈T, D(h,t) = ΠD(v,t).

(I have really got to find a better way to type up math; that product just looks wrong, and I can't even fit the index in properly without a full-blown table.)

Actually, that's probably a better way to work than protoelements and derived protoelements; the non-stacking case reduces to defining * as being idempotent on R, 1 as being the identity on *, and leaving all other operations of * undefined. Then you don't need to differentiate between protoelements and derived protoelements and construct elements out of them; just let what was described as a protoelement be an element instead, and all the old dual-elementals are hybrid elements. N is, more comprehensibly, the unique element such that ∀t∈T, D(N,t) = 1. (Although there may be t∈T that are "weak against magic" — but in that case "melée" is just another element.)

On commonly-used magic systems (3/?)

(continued from last)

So an elemental magic system, as commonly implemented, has at its base a mapping D from spells s ∈ S and spell-targets t ∈ T to an effect-modifier α∈R (where R is usually a small subset of the real line, but must contain 1). We call β = D(s,t) the coefficient of effectiveness for that spell and target.

Note that any of S, T, or R may be infinite, or even merely absurdly large. In the case of T specifically, we consider a player character with two different sets of equipment to be two distinct targets; likewise considered distinct are entities with statuses such as Reflect, Ice Break, or Zombie applied, or the various states of a boss which switches around its elemental weaknesses.

A collection of spells E⊆S all of which have the same β for any target [∀s₁, s₂∈E: ∀t∈T: D(s₁,t) = D(s₂,t)] we call coelemental; if no superset of E shares this quality, E defines a protoelement. For convenience, we extend the mapping D such that we may write D(E,t) for a protoelement E to refer to that protoelement's shared coefficient for that target. Note that any two distinct protoelements are disjoint.

We say a target t is affected by a protoelement E exactly when D(E,t) ≠ 1. Given two protoelements E and E', if any target affected by E is affected identically by E' [∀t∈T: D(E,t) ≠ 1 → D(E,t) = D(E',t)], we say that E' is a derived protoelement of E.

Finally, an element V is an ordered pair: a single protoelement v which is not a derived protoelement (called the base protoelement), and the collection of all protoelements which are derived protoelements of v. Once again, we extend the mapping D, such that we may write D(V,t) for D(π₁(V),t) (that is, identifying the β of an element with that of its base protoelement). We say that protoelements E belong to V if they are any of the protoelements that compose it, base or derived.

The unique protoelement N that belongs to every element, if it exists, is actually the set of non-elemental spells. (It would include things like Apocalypse, Flare, Giga Flare, Gravity Well, Megido, Meteo, NUKE, Ultima... you may possibly see something of a pattern here.)

Derived protoelements other than N may not exist, in which case we can simply say that every protoelement defines an element (including one special non-element from N), and then essentially forget about the protoelemental structure. (This is the usual case.) However, if another (necessarily derived) protoelement exists which belongs to more than one element, that protoelement is a set of multi-elemental spells (e.g., D&D4e's common Fire and Radiant combination).

A derived protoelement that belongs to only one element would be curious indeed, and doesn't seem to have any concrete examples.

(To be continued, with examples and extensions.)

On commonly-used magic systems (2/?)

(continued from last)

Curiously, both of these strictly-dualistic systems derive from more complicated, less perfectly orthogonal systems. The Final Fantasy series has historically (I-VI) used Fire, Ice, and Lit (aka Bolt, aka Lightning) as elements, with a random potpourri of other unrelated spells: while Fire and Ice oppose, Lightning stands somewhat apart. This in turn stems from AD&D, in which the three most accessible and consistently used damage types were fire, cold, and electric. Chrono Trigger's magic system was similar, in that it used Fire, Water (incl. Ice), and Lightning: the three could combine to form the fourth magic type, Shadow.

This, too, is a common extension: Persona 3, for instance, used Fire/Ice, Lightning/Wind, and Light/Darkness (the last two only existing as instant-death magics), but had an additional, "Almighty" pseudo-element which could not be blocked nor resisted. Many of the Final Fantasy series have had non-elemental Flare or Ultima spells.

Of course, some elemental systems have no concept of "opposing" elements at all. The Chinese classical elements (a source of inspiration sadly underutilized amongst game designers) consists of five elements — fire, water, wood, metal, and earth — each of which supports one element, is supported by another, undermines a third element, and is undermined by the remaining. (This is usually shown as a directed version of K₅, with two separately colored cycles.) Skies of Arcadia's system of elements simply eschews any sort of underlying symmetry.

(TBC)

On commonly-used magic systems

So the basis for... probably most CRPG magic systems is the classical four elements. This can be seen in, for example, Final Fantasy X.

Final Fantasy X doesn't actually use the classical elements outright; rather, its four primary elements are fire, ice, water, and lightning. However, they're still opposed in exactly the same manner as the classics: where Paracelsus had fire/water and earth/air opposed, FFX has fire/ice and water/lightning. It's the same graph, just with different labels.

Of course, this can be extended to more than two opposing pairs, usually by adding light/darkness, or a close facsimile thereof. Chrono Cross used a similar, three-way opposing system: red/blue, green/yellow, and black/white. Exactly what physical concept was represented by each color was a little loose, but the strict opposition and noninteraction between them was not.

Intuitively, these map to `RR^2` and `RR^3` respectively — although the situation is actually a little more complex than that, since games using this system tend to find ways to break the axes at the origin: e.g., a player character wielding a Flame Sword but wearing an Antifreeze Charm, so that they can take on Ice-aspected enemies.

(TBC)

Questions on languages

Let D(⋅, ⋅) be a "distance" operator on phonemes such that phonemes with smaller "distances" sound more similar than phonemes with smaller "distances". (We assume for simplicity that such operators exist and that they can be defined up to isomorphism in a mostly language-independent manner; it is acceptable that they define merely a semimetric rather than a proper metric on any given set of phonemes. If these assumptions are too strong, then for at least the interesting questions below, phonemes may be tagged with their originating language, and D can then be defined strictly in terms of the perception of speakers of the language from which its first argument is drawn.)

Let ℳ be the set of functions from the phonemes of a language a to the phonemes of a language b. Let any M∈ℳ such that ∀x∈a, y∈b: y = M(x) → ¬∃z∈a: D(x,z) < D(x,y) (that is, any M∈ℳ such that M(x) selects a D-closest point in b to x) be called a natural mapping from a to b — a function notionally applied by a speaker of b to obtain familiar phonemes from b from potentially unfamiliar phonemes in a.

We shall write a ⊑ b if there exists an injective natural mapping from a to b; we may then read a ⊑ b as "b phonetically subsumes a" or somesuch. For example, Māori ⊑ Japanese, and Japanese ⊑ French.

Let E be the set of all human languages. What does the graph (E,⊑) look like? (Specifically, what is its graph density?) How strong is the correlation between mutual intelligibility and local symmetry of ⊑? Are there more sources or sinks than one would expect solely from the graph density? Is ⊑ transitive? (Mathematically, it need not be.)

Most relevantly, the question that prompted the definition of ⊑: given languages a, b, and c such that a ⊑ b and a ⋢ c, will a native speaker of a generally notice a qualitative difference between the accent of an accented speaker of b and an accented speaker of c? And is the average intelligibility of speakers of c vs. those of c' related to the degree to which those languages' relevant natural mappings from a fail to be injective?

Matchstick removal

So I was browsing around, and found some elementary-to-middle-school-targeted math problems (PDF), with a possible gem sequestered within.

29. Given a 4×4 square grid made up of matchsticks (i.e. 40 matchsticks), what is the minimum number of matchsticks you can remove such that there are no squares left?

Hmm. Let's see (I says to myself, says I).

If only squares of size 1 are considered, there are sixteen squares to be destroyed; each matchstick is used by at most two such squares, so 16/2 = 8 is a lower bound. And indeed there is a very simple eight-matchstick set which eliminates all of the size-1 squares (see image). And this is probably about right for average eighth-graders under pressure, give or take a grade level.

But what if squares of sizes 2, 3, and 4 are also considered?

It is relatively easily shown, based on the preceding, that 9 is a lower bound. Any outer-edge matchstick will remove only one size-1 square, so will not be contained in a minimal size-1-square-destroying set; but at least one outer-edge matchstick must be removed to break the size-4 square. Similarly, it's easy to show that 10 is an upper bond; there are several solutions, one of the more regular of which is pictured to the right.

So that reduces it to 9 or 10. Which is it? At first I thought it was 10, due to a flawed proof-by-counting similar to the proof for size-1. I later "corrected" it, producing a proof-by-cases over the possible domino-tilings of the 4-square that there was no 9-matchstick set, and found a flaw in that while typing it up.

In attempting to correct that second proof, I found this.


This isn't a very easy solution to find, being quite asymmetric (as, I think, all such solutions must be), tucked into a back corner of the large (40C9 > 2⁷²) solution space, and elusive of elegant derivation. Surely the eighth-grade problem was the first interpretation? But I checked the solutions anyway.

ANS: 9
SOL: First, considering a 1 × 1 square, only one matchstick need be removed to ‘break’ all the squares. Then go to a 2 × 2 square, by inspection one can easily see that three matchsticks must be removed. Now for a 3 × 3 square., [sic] we find that at least six matchsticks must be removed. At this point we could guess that the next number in the sequence is nine.

Uh-huh. Two entirely separate objections leap to mind:

a) The sequence S_n = n(n+1)/2 : 1, 3, 6, 10, ... (the triangular numbers) is a much more natural sequence to extrapolate from the values 1, 3, 6.
b) Guessing based on a few values of an initial sequence is worth absolutely nothing anyway.

How much would you like to bet that their original solution was "10" by the logic involved in a), hastily changed to "9" when a particularly lucky or clever student found a nine-stick solution like the one above?

Quick proof

So two posts ago I posited that ‘for any given open set U ⊆ ℂ, (∀z∈U: ζ(z) = ζ(z+k)) ⇒ (k = 0)’. This is almost true; the correct statement begins "for any given nonempty open set U ⊆ ℂ", and follows almost immediately from the identity theorem.

First, note that both ζ(z) and ζ_k(z) = ζ(z+k) are holomorphic everywhere in ℂ, except at their respective singularities, 1 and 1-k. Note also that the set S = ℂ\{1, 1-k} is open (since its complement, the set {1, 1-k}, has an empty interior is equal to its boundary and is therefore closed) and connected (since, e.g., it is path-connected).

Assume the antecedent holds for some open set U. It then also holds for the open set U' = U ∩ S. Select any point z in this set, and any open ball V containing z, but lying within U'. (One such must exist; if it did not, z would be on the boundary of U', and since U' is open it excludes its boundary.) The preconditions for the identity theorem are thereby met: ζ = ζ_k on a neighborhood of a point, z, which lies within a connected open set on which both ζ and ζ_k are holomorphic — namely, S.

Thus, ζ = ζ_k on S.

Now, assume for the sake of contradiction that k ≠ 0. Then ζ(1-k) is some complex number, since ζ is defined everywhere except at 1. Consider some sequence z_n which approaches 1-k in the limit, but contains neither 1-k nor 1. (Such sequences must exist: consider the disjoint sequences (1-k)+2^-n and (1-k)-2^-n, only one of which might contain 1.). ζ is complex-differentiable and therefore Heine-continuous, so the sequence ζ(z_n) approaches ζ(1-k). Moreover, since ζ_k's singularity at 1-k is a pole, ζ_k(z_n) must approach infinity. However, this sequence is contained in S, and so ζ(z_n) = ζ_k(z_n) for all n. Since the sequences are identical, so too must be their limits; but this means that ζ(1-k) = ∞, which is a contradiction.

Therefore, k = 0.

---

Edit 2008-12-21: fixed a silly topology error — an empty interior does not imply closedness. (Specific counterexample: the set of all Gaussian rationals has an empty interior, but is not a closed set.)