Author Archives: gentzen

About gentzen

Logic, Logic, and Logic

Incredibly awesome, but with overlength

Joel David Hamkins answering Daniel Rubin’s questions is incredible. I just had to write this post. Both are great, Joel is friendly and explains extremely well, and Daniel is direct, honest, and engaging in a funny way. And they really … Continue reading

Posted in Uncategorized | Leave a comment

Fields and total orders are the prime objects of nice categories

A field is also a commutative ring, so it is an object in the category of commutative rings. A total order is also a partial order, so it is an object in the category of partially ordered sets. Neither are … Continue reading

Posted in inverse semigroups | Tagged , | Leave a comment

Prefix-free codes and ordinals

Originally posted on What Immanuel Kant teach you:
Consider the problem of representing a number in computer memory, which is idealized as a sequence of zeros and ones. The binary number system is a well-known solution to this problem —…

Posted in Uncategorized | Leave a comment

Isomorphism of labeled uniqueness trees

The paper Deep Weisfeiler Leman by Martin Grohe, Pascal Schweitzer, Daniel Wiebking introduces a framework that allows the design of purely combinatorial graph isomorphism tests that are more powerful than the well-known Weisfeiler-Leman algorithm. This is a major achievement, see … Continue reading

Posted in isomorphism | Tagged | Leave a comment

Defining a natural number as a finite string of digits is circular

The length of a finite string is a natural number. If a given Turing machine halts on the empty input, then the number of steps it performs before halting is a natural number. (A Turing machine halts if it reaches … Continue reading

Posted in Uncategorized | 3 Comments

Theory and practice of signed-digit representations

The integers are sometimes formally constructed as the equivalence classes of ordered pairs of natural numbers . The equivalence relation is defined via iff so that gets interpreted as . This motivates the signed-digit representation. To avoid storing two numbers … Continue reading

Posted in Uncategorized | 4 Comments

A list of books for understanding the non-relativistic QM — Ajit R. Jadhav’s Weblog

I really like that this post points out that QM is vast, and that it takes a prolonged, sustained effort to learn it. I also like that it explicitly recommends chemistry books. My own first exposure to the photoelectric effect … Continue reading

Posted in Uncategorized | 1 Comment

I’m not a physicist

Background At the end of 2016, I decided to focus on working through an introductory textbook in quantum mechanics, instead of trying to make progress on my paper(s) to be published. I finished that textbook, which taught me things like … Continue reading

Posted in physics | 1 Comment

ALogTime, LogCFL, and threshold circuits: dreams of fast solutions

Our protagonists are the following (DLogTime-) uniform circuit classes NC1 (ALogTime) SAC1 (LogCFL) TC0 (threshold circuits) Interesting things can be said about those classes. Things like Barrington’s theorem (NC1), closure under complementation by inductive counting (SAC1), or circuits for division … Continue reading

Posted in automata | 5 Comments

A subset interpretation (with context morphisms) of the sequent calculus for predicate logic

The previous two posts used the sequent calculus with a subset interpretation: We work with sequents , and interpret the propositions (and ) as subsets of some universe set . We interpret the sequent itself as . While writing the … Continue reading

Posted in logic, partial functions | Tagged , | Leave a comment