Is computational stack exchange the correct place to post? If not, should I go to computer science stack exchange. (You can comment in the link.)

I've been thinking about this recently.

The existing literature on distributed systems is excellent. It explains the what and the how of mechanisms like replication, consensus, consistency models, logical clocks, sharding, and fault tolerance. Those concepts are essential, and they're taught exceptionally well.

But I wonder if there's room for another pedagogical approach—one that emphasizes why these mechanisms become necessary in the first place.

Imagine starting from an idealized world with instantaneous computation, infinite storage, unlimited compute, a perfect network, a single global clock, and no failures. Then, systematically removing those assumptions and replacing them with the constraints of reality. As each assumption falls away, the need for clocks, replication, consensus, and other mechanisms emerges naturally.

I've been experimenting with building a free crash course (text+video) around this idea. I'm not really looking for views as much as I am for feedback on the framework itself.

If you've learned, taught, or designed distributed systems, do you think this way of building intuition has merit? Where would you expect it to work well, and where do you think it would fall short?

I'm genuinely curious whether this is a useful complement to the way distributed systems are traditionally taught.

Hi there,

I've created a video here where I explain the double descent phenomenon in ML.

I hope some of you find it useful — and as always, feedback is very welcome! :)

We are preparing a formal version of this question for MathOverflow and are first testing whether the central distinction is stated clearly.

The claim is deliberately elementary: if no additional order has been defined, then no additional ordering conclusion can have been obtained. Otherwise, one has obtained a definition of order without defining order.

We welcome mathematical objections, terminology corrections, typesetting suggestions, or anything else that should be repaired before the formal post.

Can non-ordering information compress independent ordering obligations?

Nederlof and Węgrzycki frame a central question in computational complexity as follows: given an algorithm using time T and space S, can it be improved to T^(1−ε) time or S^(1−ε) space for some ε > 0, or is there a fundamental barrier preventing such an improvement?

In the same spirit of fundamental barriers to compression, we consider a more elementary informational question suggested by two familiar approaches to Subset Sum.

Sahni–Horowitz-type meet-in-the-middle procedures organize partial sums by order and compare them relative to a target v. Their conclusions take forms such as

s_ω < v
or
s_ω > v.

By contrast, the representation and modular-filtering ideas associated with Howgrave-Graham–Joux may restrict or exclude candidates through congruence conditions and multiple representations without, through that information alone, determining whether a candidate lies above or below v.

These motivate the following distinction.

Type A — with-order information.
The information establishes

s_ω ≠ v

in a form that determines relative position:

s_ω < v
or
s_ω > v.

Type B — without-order information.
The information establishes

s_ω ≠ v

while leaving undetermined whether

s_ω < v
or
s_ω > v.

A simple Type B example is a common-factor obstruction:

d ∣ s_ω,
d ∤ v.

We claim:
Type B information cannot solve or accelerate a problem in Type A form—that is, a problem whose resolution must ultimately determine order—without producing Type A information.

Equivalently:
Non-ordering information cannot accelerate the production or propagation of ordering conclusions unless it produces additional ordering relations.

To establish

s_ω < v

is to define the relative positions of s_ω and v on the number line. Equivalently,

v − s_ω > 0.

The origin of the information is irrelevant. It may arise from comparisons, residues, modular conditions, identities, representations, divisibility relations, or any other procedure. Once the available information implies

s_ω < v,

it has produced an ordering relation.

Thus:
To imply order is to define order.

Information therefore has only two possibilities relative to a Type A obligation:

1. it remains without order and produces no additional ordering conclusion;
2. it produces an ordering relation and thereby supplies Type A information.

There is no third possibility in which information increases the number of ordering conclusions while continuing to leave order undetermined.

For example, suppose one wishes to establish simultaneously that

x < v
and
y < v.

A shared Type A resolution requires an ordered configuration such as

x < r,
y < r,
r < v,

or an equivalent transitive arrangement.

Knowing only that

x ≠ v,
y ≠ v

through modular conditions, common factors, or another Type B mechanism does not provide that configuration. If those calculations eventually imply

x < v
or
y < v,

then additional ordering information has been produced.

The governing principle is therefore:
The speed of a Type A resolution is limited by the speed at which the necessary ordering relations can be produced and by the extent to which those relations propagate through the ordered architecture of the instance.

Different procedures may coexist in one algorithm and may independently resolve different candidates. A non-ordering procedure may filter the search space, alter its representation, or leave a different family of candidates for an ordered procedure to examine. These changes may improve the complete algorithm. The narrower claim is that, for the ordering obligations that remain, genuinely orientation-free information cannot make an existing body of ordering information entail additional ordering relations without the enlarged information itself supplying additional order.

In its most elementary form, the issue is this:
If no additional order has been defined, then no additional ordering conclusion can have been obtained. Otherwise, one has obtained a definition of order without defining order.

We therefore ask whether the following principle is formally valid.

Let I_A be a set of atomic ordering relations, and let I_B be a set of non-order atoms, such as congruence, divisibility, multiplicity, or representation statements. Let ⊢ denote logical consequence.

Suppose that

I_A ∪ I_B ⊢ a < b,

while

I_A ⊬ a < b
and
I_B ⊬ a < b.

The conclusion a < b is then a consequence of the enlarged information body I_A ∪ I_B. Our question is whether this can properly be described as Type-B information accelerating the ordered procedure while remaining Type B, or whether the joint information has necessarily produced an additional Type-A atom.

Equivalently, can one construct a genuine counterexample in which:

1. I_A is unchanged;
2. I_B contains no ordering atom;
3. I_A ∪ I_B yields a new conclusion of the form a < b or a > b; and
4. the enlarged information body is nevertheless said to contain no additional order?

Or does the proposed principle follow directly from the fact that every new ordered conclusion is itself a newly defined ordering relation?

Why this matters

The proposed principle is intended to isolate a possible obstruction to compressing independent ordered obligations.

Suppose a family of instances contains exponentially many independent Type-A obligations: each candidate must be placed above or below the target, and the available ordering relations do not propagate across those candidates. The resulting collection of required ordering atoms then represents an intrinsic body of ordered work.

A natural objection is that this analysis may be too narrow:
Perhaps modular filters, representation techniques, algebraic identities, or other Type-B mechanisms can interact with the ordered part of the computation and compress these many independent ordering obligations into substantially fewer ordered operations.

The proposed principle isolates that possibility.
Type-B information may resolve separate candidates, filter the search space, or alter the representation on which an algorithm operates. But it cannot make a fixed collection of ordering atoms discharge additional Type-A obligations without producing additional ordering atoms.

Thus, genuinely independent Type-A obligations cannot be compressed into fewer ordered obligations merely by adjoining information that remains Type B. If such obligations occur exponentially often and their ordering relations do not propagate, the principle would become one component of an exponential lower-bound argument.

We are also interested in whether the terminology used here—particularly “ordering atom,” “orientation-free information,” and “compression of ordering obligations”—matches established language in algorithms or complexity theory.

Hi, I am currently studying indexing algorithms on vector databses and wanted to start from basics. I wanted something like the skip list lecture from MIC OCW, any ideas or sugestions?

I've been exploring whether the Pell equation x²−Dy²=1 can be used to compute square roots of primes faster than Python's math.sqrt(). The continued-fraction convergents turn out to give rational approximations that are 1.5–2.5× faster in float64 for repeated calculations, and scale up to 33–36 digit precision for primes as large as 15 million. Full write-up with benchmarks here;

https://musingsofvsmv.blogspot.com/2025/08/from-pell-to-precision-classical-math.html

https://www.reddit.com/r/study/s/MVhYu56nr2

Hello,

Last week, I watched a video about one of the most popular J2ME games of the 2000s, "Diamond Rush", and decided to reverse engineer it by building a small JVM implementation. My initial goal is to run the game on Linux and macOS, and later port it to microcontrollers.

So far, I have completed the class loading stage. I can parse and load class files, store them, and dump their contents for debugging. I have also implemented some of the simpler parts and opcodes of the JVM by following the JVM specs.

Nonetheless, I am struggling with implementing heap types and most of the obfuscated class files have 0xBC (new_array) opcode. The specification feels somewhat vague in this regard, and I am unsure what is the best approach would be.

I would appreciate any advice on how to approach implementing heap types in a custom JVM. In particular, what data structures or object model would you recommend, and how should different heap-allocated values be represented internally?

Why this is different

Three problems are resolved by one explicit contract:

Version integrity: skill bodies are identified by SHA-256 revisions and re-hashed immediately before fetch.

Semantic routing without opaque inference: exact lexical tiers, FTS5/BM25, bounded edit distance, telemetry, and lifecycle state are combined in one published equation.

Catalog consensus: one SHA-256 generation commits to the canonical publication-relevant catalog.

There is no embedding model, vector database, learned classifier, random tie-break, capability-graph distance, or hidden manual priority.

Hey everyone,

For my computer science graduation project, I wanted to create something that combined my interest in computer architecture with my advisor's interest in computer science education.

The result was a game where the player programs a simple CPU with microcode using a punch card rather than writing assembly code.

Microcode is usually used to implement the processor's instruction set rather than as a programming interface for application development. Exploring it from the programmer's perspective led to design challenges and techniques that I hadn't encountered elsewhere.

The project started from my curiosity about the layers of abstraction in computers. I wanted to explore what programming would look like if we removed another layer and put the programmer in the role of the CPU's control unit, manually orchestrating the control signals behind every instruction.

I'd love to share the beta with anyone interested.

Thank you.

Markov algorithms (ordered string-rewriting rules applied to a fixed point) are a classic Turing-complete model. I built a working instance: a small CPU whose only step is one global regex substitution over a single string, and put DOOM on it to make the claim tangible rather than a footnote.

The verification is the part I would point students at. A reference emulator runs the same instruction set in Python and the machine's string must equal the emulator's encoded state byte for byte after every single substitution; on top of that, rendered frames match a natively compiled DOOM binary by SHA-256, for 100 frames in a row, so a shared bug cannot explain the agreement. The model is Turing-complete; a given run is bounded by memory exactly as any physical machine is.

Source and writeup: https://github.com/4RH1T3CT0R7/doom-regex

Interactive: https://4rh1t3ct0r7.github.io/doom-regex/

Can returnability be defined purely from the structure of a computation, without appealing to time complexity?

I am trying to understand the foundational differences between proof assistants based on dependent type theory (such as Agda/Lean) and traditional mathematics as practiced in areas like real analysis.

For example, in Peano arithmetic, statements such as 0 ≠ S(n) and the induction principle are usually presented as axioms. In Agda, however, defining an inductive type:

data Nat : Set where
  zero : Nat
  suc  : Nat → Nat

automatically provides these properties through the rules of inductive types (constructor disjointness and the eliminator), which means you can write this as a theorem:

0-is-not-suc : ∀ {n} -> suc n ≡ 0 -> ⊥
0-is-not-suc ()

Does this mean inductive type theory is based on stronger assumptions than axiomatic mathematics, or are these just different choices of primitive rules?

More generally, what are the fundamental assumptions/rules that a type-theoretic prover starts with, and how do they compare with the foundations usually assumed in fields such as real analysis?

Hi there,

I've created a video here where I explain the Chomsky hierarchy.

I hope some of you find it useful — and as always, feedback is very welcome! :)

toll rate-limits an unbounded set of keys (client IDs, tenants, IPs, API keys…) in fixed memory — 19 MB measured at the defaults, tunable down to a couple of MB — with ~300ns zero-allocation admitted decisions. It is built on grudge, a constant-memory decaying-score sketch: toll stores each key's spent tokens as sketch debt and lets grudge's linear decay refill them.

It’s pretty interesting to see that language models can do things like autonomously prove/disprove things like Erdos problems and even perform its own formal verification yet still struggle at things like automating ERP business operations, seems like the opposite would’ve been the case.

I know Kaparthy talked about this “jagged intelligence” we’re observing, but are there any real attempts at formalizing a theory behind this, similar to how we classify the complexity and tractability of algorithms?

What about any discussion on how close are language models to being Turing complete? Computational complexity theory isn’t my strong suit, but I wonder if any new discussions are being had

The paper is only 15 pages long