Fun name: seems like a reference to “Magit” both syntactically (being a portmanteau of “Magit” and “jujutsu”) and semantically (majutsu meaning “magic” in Japanese).
They're not infailable, though. For example, TeX's primitive for fractions is actually {a \over b}, LaTeX's \frac is a macro on top of that. The consequence is that while typesetting a formula, the engine does not know the current text size, since an \over further down the line may put the entire thing into a numerator. Dealing with this can be quite a pain when writing math macros.
I think a = sqrt(2), b = log(9)/log(2) with a^b = 3 is easier. To show that b is irrational, assume b = n/m for integer n, m. Then 9^m = 2^n, which can't be the case since the lhs is odd and the rhs is even.
It's not limited to 32, but afterwards search will be linear along child[0]. Using rotation would not make a difference, since you're in the collision case already, so you would effectively always branch to the same child for levels below 32.
It would. The offsets generated by the hash would repeat every 32 shifts, but the absolute addresses given in the collision cases are a random construction based on the history of the tree at that point, so despite the offsets’ repeating, the tree’s invariants along the lookup are likely to be preserved.
> Yes, I thought this was clear from my statement.
Yeah, sorry, wasn't really necessary to repeat that point. I was too focused on the "limiting the height of the tree to 32" formulation.
I have to admit that I don't quite understand what invariants along the lookup you mean. All lookups that reach a particular node on level 32 have the same hash, so regardless of how you compute the branch from the hash below level 32, they will always follow the same path starting from there (except for terminating at different levels, obviously). So nodes only ever have one child at most, and there's no loss in simply picking child 0 in all cases.
Sorry if what I'm describing is again obvious, maybe I just don't understand your point correctly.
A more advanced example of mutual recursion: it's possible to perform an exhaustive search over the "Cantor space" of all infinite sequences of bits that either finds a sequence satisfying a (total, computable) predicate or determines that such a sequence doesn't exist. That is to say, there's a function `search`,
type Cantor = Natural -> Bit
search :: (Cantor -> Bool) -> Maybe Cantor
That's a good intuition for first order PA, where the completeness theorem holds, but not the full story either. PA in second order logic only has a single model, but is still incomplete: there are statements that are true in the only model, but not provable.
Yeah but second order logic itself is incomplete. ZFC doesn't have a single model, too, btw. In the end unprovable sentences exist because there are multiple models satisfying your axioms.
What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in more general conditions.
Concerning multiple models of ZFC: I'm always confused by such statements about the foundations of set theory itself, they seem weirdly self-referential. ZFC certainly can't prove that it has multiple (or even any) models. Does such a statement need additional axioms, or is there a general theorem like "If a first order theory has any model, then it has multiple ones."?
"What I meant to say is that multiple models are not the only reason for something to be true but unprovable, the incompleteness theorem also holds in more general conditions." I can't give a clean rebuttal for this, but I believe this to be profoundly mistaken. It might be technically correct though, depending on how you'd formalize this statement.
To formalize math you need a logic that has some properties: it should be decidable whether a proof is correct, you should be able to write it down, it should not be contradictory. If you take these together the only way a statement is unprovable, is if it is independent from the axioms, i.e. there exist multiple models.
I see. Checking the formulation of the incompleteness theorem again, I noticed that I probably misunderstood something here: it indeed essentially requires proofs to be verifyable, which second order theories do not provide. So second order PA can (and in fact does) have a proof of every statement or its negation, without contradicting incompleteness, but provability is somewhat useless in this case. For theories that fit the conditions you listed, unprovability is indeed due to multiple models. Does that make sense?
Edit: however, consistent second order theories don't always have a model. In first order, if S is an undecideable statement in theory T, then both T+S and T+!S have models, both of which are models for T, so undecideable statements always come from multiple models. But that does not need to be the case in second order, so your claim "it is independent from the axioms, i.e. there exist multiple models" is not neccessarily true, i.e. there may be cases when decideability of some statement fails in a theory with a unique model. Or is there another argument for your claim?
Forgive me for spamming questions, I just try to understand how these things fit together. But maybe we should just stick to first order, since everything else is too weird anyway.
If found “TeX by Topic” a great introduction, it's less overwhelming than the TeX book. Also really helpful in wrapping your head around macro expansion is the `texdef` cli tool, which allows you to quickly evaluate a line of macro code. Finally, https://www.tug.org/utilities/plain/cseq.html is nice for reference.
There are three books that are worth looking at to get plain TeX. I’d start with Viktor Eijkhout’s TeX by Topic (which I think is free in PDF on CTAN). Then the TeXbook to really get everything (the PDFs that float around the net are illegal. Please buy your copy. DEK donated his royalties to TUG so your purchase will help support the continuation of things like CTAN and the LaTeX project). And finally, if you really want to dig deep, Stephan v. Bechtolsheim’s four-volume magnum opus, TeX in Practice will tell you more than you ever wanted to know.
It does double the residue, but modulo 19. 2 * 18 = 36 = 17 (mod 19) and 2 * 10 = 20 = 1 (mod 19). The reason is that the method consists essentially of two steps. (1) Subtract a suitable multiple of 19 to make the number a multiple of 10. (2) Divide by 10. And dividing by 10 is the same as multiplying by 2, since 2 * 10 = 20 = 1 (mod 19).
reply