Author Archives: gentzen

About gentzen

Logic, Logic, and Logic

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 | Leave a 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 | 3 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

Logic without negation and falsehood

In the last post, consideration related to partial functions lead us to present a logic without truth and implication, using the binary minus operation as a dual of implication and substitute for unary negation. But logic without implication and equivalence … Continue reading

Posted in logic | Tagged | 3 Comments

Logic without truth

Pi is wrong! But so what? It is neither new, nor complicated enough to count as real math! And suggestions that  or  might be even better show that it not clear-cut either. I recently invested sufficient energy into some logical questions to … Continue reading

Posted in logic, partial functions | Tagged , | 6 Comments

Learning category theory: a necessary evil?

The end of my last blog post (about isomorphism testing of reversible deterministic finite automata) explained how category theory gave me the idea that the simplified variant of my question about permutation group isomorphism should be easy to solve: The idea to consider … Continue reading

Posted in isomorphism | Tagged | Leave a comment

A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata

A deterministic finite automaton (DFA) is a 5-tuple, , consisting of a finite set of states a finite set of input symbols a (partial) transition function an initial state a set of accept states An isomorphism between two DFAs and … Continue reading

Posted in automata, inverse semigroups, isomorphism, partial functions | 4 Comments