Blogs I Follow
- Not Even Wrong
- More Quantum
- Shtetl-Optimized
- Mathematics without Apologies, by Michael Harris
- Windows On Theory
- Thoughts
- ThatsMaths
- Tobias J. Osborne's research notes
- What Immanuel Kant teach you
- Quantum Frontiers
- MyCQstate
- Neil Barton
- Computational Semigroup Theory
- Math ∩ Programming
- ErdosNinth
- in theory
- Anurag's Math Blog
- Annoying Precision
- njwildberger: tangential thoughts
- Combinatorics and more
- What's new
- Bits of DNA
- Turing Machine
- My Brain is Open
- Gödel's Lost Letter and P=NP
- Mathematical Formalities
-
Recent Posts
- Blackbox oracles and function classes December 23, 2025
- Am I an engineer? December 23, 2024
- Proving formal definitions of informal concepts November 4, 2023
- Getting started without a pre-existing understanding of non-standard natural numbers September 9, 2022
- True randomness and ontological commitments February 28, 2022
- Why mathematics? February 19, 2022
- Incredibly awesome, but with overlength September 3, 2021
- Fields and total orders are the prime objects of nice categories January 30, 2021
- Prefix-free codes and ordinals May 11, 2020
- Isomorphism of labeled uniqueness trees April 20, 2020
- Defining a natural number as a finite string of digits is circular August 17, 2019
- Theory and practice of signed-digit representations April 16, 2019
- A list of books for understanding the non-relativistic QM — Ajit R. Jadhav’s Weblog November 25, 2018
- I’m not a physicist April 29, 2018
- ALogTime, LogCFL, and threshold circuits: dreams of fast solutions November 2, 2017
- A subset interpretation (with context morphisms) of the sequent calculus for predicate logic September 24, 2017
- Logic without negation and falsehood December 11, 2016
- Logic without truth September 3, 2016
- Learning category theory: a necessary evil? April 3, 2016
- A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata November 15, 2015
- On Zeros of a Polynomial in a Finite Grid: the Alon-Furedi bound September 19, 2015
- Groupoids August 3, 2015
- Reversibility of binary relations, substochastic matrices, and partial functions March 22, 2015
- Algebraic characterizations of inverse semigroups and strongly regular rings December 6, 2014
- Gentzen’s consistency proof is more impressive than you expect December 5, 2013
Recent Comments
- gentzen on Am I an engineer?
- gentzen on Am I an engineer?
- Peter Morgan on I’m not a physicist
- Peter Morgan on True randomness and ontological commitments
- gentzen on Fields and total orders are the prime objects of nice categories
- Proving formal definitions of informal concepts | Gentzen translated on Incredibly awesome, but with overlength
- gentzen on Getting started without a pre-existing understanding of non-standard natural numbers
- vegafrank on Getting started without a pre-existing understanding of non-standard natural numbers
- Christopher on Getting started without a pre-existing understanding of non-standard natural numbers
- gentzen on True randomness and ontological commitments
- none on True randomness and ontological commitments
- True randomness and ontological commitments | Gentzen translated on Why mathematics?
- Fields and total orders are the prime objects of nice categories | Gentzen translated on Defining a natural number as a finite string of digits is circular
- Fields and total orders are the prime objects of nice categories | Gentzen translated on Algebraic characterizations of inverse semigroups and strongly regular rings
- gentzen on ALogTime, LogCFL, and threshold circuits: dreams of fast solutions
Category Archives: complexity
Blackbox oracles and function classes
After spending a long time to work out the function classes for bounded alternating Turing machines, I felt stupid that it took me so long to see the obvious: They are the functions computable by deterministic machines (with appropriate resource … Continue reading
Posted in complexity, computability, partial functions
Leave a comment
Gentzen translated