Here is my proposed NINOR programming language. The program state is an n bit register R = R1, R2, ... Rn initialized to the program input and that contains the output when the program halts. The program is written as n+1 assignment statements to R0...Rn executed in parallel at each step. A statement has the form Ri = expression. Each expression is a Boolean function of R1...Rn using only NOR gates, each written as (expr1, expr2,...). A NOR gate with 0 inputs, written (), evaluates to 1. The program halts when R0 is assigned a 1.
For example: R0=(); // halt after first step R1=(()); // 0 R2=((R1),(R2)); // R1 and R2 R3=((R1,R2),((R1),(R2))); // R1 xor R2 Then the challenge is to find the smallest NINOR program that takes an input of all zeros and halts with enwik9 in R1...R8000000000. The question is how do you compress the program to give the same answer as Kolmogorov complexity? We can add syntactic sugar like: define output=R[1:96]; output="Hello world\n"; And test some use cases. 1. Output n random bits with a program of length n + C, where C is a constant that does not depend on n. 2. Output n identical bits with a program of length log n + C. 3. Output a random sequence of m bits repeated n times with a program of length m + log n + C. 4. Output n groups of m bits whose probably distribution is P with a program of length nH(P) + C, where H(P) is the entropy of P. And continue for more complicated cases of known Kolmogorov complexity. But this is not a proof. You need a Turing complete language to compress the NINOR program, and that language will have a language dependent constant, which was the part you were trying to avoid. -- Matt Mahoney, [email protected] On Mon, Sep 14, 2026, 2:35 PM James Bowery <[email protected]> wrote: > > > On Sun, Sep 13, 2026 at 6:48 PM Matt Mahoney <[email protected]> > wrote: > >> On Sat, Sep 12, 2026 at 9:44 AM James Bowery <[email protected]> wrote: >> > From the NiNOR essay: >> > > Now we still have a free parameter but is it a choice of Turing >> machine? No. It's an integer, the size of which goes up only as the log2 >> of the amount of memory required to expand the executable archive. >> > >> > The point is that if you can reduce the data-dependent prior to an >> integer "tape" size, you may have made some progress in defining >> algorithmic information. >> >> I suppose that would work, but all this does is fix the language used >> to estimate Kolmogorov complexity. It needs more specification. How do >> you represent the description of the gate logic? > > > Shannon's 1938 switching-circuits paper generalized De Morgan theorem > <https://www.cs.virginia.edu/~evans/greatworks/shannon38.pdf> > <https://www.cs.virginia.edu/~evans/greatworks/shannon38.pdf>: NOR and > NAND are not only universal but also equivalent in circuit complexity > consequences, so take your pick. > > Additional choices are available creating a very limited taxonomy of > cyclic logics compared to the literally infinite range of UTMs.One can get > lost in a sea of choices if one wishes of course but realistically speaking > the range of interesting choices is quite limited. For example Turing > chose 2 inputs rather than what I prefer which is n-Inputs. In terms of > network stability the most interesting choice is 0 gate day in which case a > circuit like X=NAND(X,X) is, from within its temporal frame a square wave > and from outside its temporal frame a source of random bits. > > Is it a list of gates >> in numerical order, each followed by a list of inputs? How do you >> represent the numbers? Can you compress it, like to use macros to >> describe repeated logic like adders or registers? >> > > These are all choices captured by the emulator. > > >> I expect to see even further improvements by growing the transformer >> from 6M parameters to maybe 50M. >> > >> > And that will be interesting in itself for two reasons: 1) Why would >> 50M be the optimum? 2) Is there nothing to be learned here regarding the >> role evolution plays in establishing priors? of >> >> From information theory, a neural network should have one parameter >> per compressed bit of training data, the minimum needed to reproduce >> the data without overfitting. > > > Cite? Are you referring to Shannon's empirical measure of bits per > character based on human prediction? > > > >> The top LLMs use 5-10 trillion >> parameters on 20-30 TB of text, which is in the same ballpark. >> > > That doesn't really answer #1. 50M duplicated between compressor and > decompressor is a lot of prior to saddle the compressor with in a 100MB > compressed 1GB Wikipedia executable archive. > > >> BTW the LTCB has a new leader. https://mattmahoney.net/dc/text.html >> RATA-CMIX is a derivation of fx2-cmix-transformer that follows Hutter >> prize limits but is not a submission because the improvement is less >> than 1%. It uses the same transformer weights but improves their >> compression. It also adds some interesting modeling improvements. >> >> Also, tufazip is an open source derivation of nncp, which is closed >> source and held the top spot for 2 years. >> >> The top 5 entries all use transformers. I still believe that there are >> better algorithms, because we know that the human brain learns in a >> single pass. Or maybe it doesn't. I hope that the LTCB or Hutter prize >> will either motivate its discovery or explain why the brain needs >> 10^14 to 10^15 synapses to represent 10^9 bits of long term memory and >> LLMs don't have this limitation. >> > > I think if we closely analyze Vladimir's compressor prior it will reveal > something more interesting than other pre-processing approaches thus far > involving curriculum design (ordering articles, vocabulary, etc). I > suspect it will reveal something like a hierarchical transition grammar > specialized for enwik9. The distinction being that such a grammar is a > "Zero To One" gain which pays for its duplication in the excutable archive > as an "instruction set" for "UTM Choice". > > >> -- >> -- Matt Mahoney, [email protected] > *Artificial General Intelligence List <https://agi.topicbox.com/latest>* > / AGI / see discussions <https://agi.topicbox.com/groups/agi> + > participants <https://agi.topicbox.com/groups/agi/members> + > delivery options <https://agi.topicbox.com/groups/agi/subscription> > Permalink > <https://agi.topicbox.com/groups/agi/T3f8115622f860785-M0d88c653a816635519af6877> > ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T3f8115622f860785-Mdd099bc171799d253c554268 Delivery options: https://agi.topicbox.com/groups/agi/subscription
