While your approach is interesting in its own right, you'll need to charge log2(number_of_registers) for each reference to a register whether on the LHS or RHS -- either that or you'll have to get into some meta-descriptive space that starts to look like DCG of NiNOR complexity again wherein the instruction set architecture must be simulated on its own ISA to get a proper measure of the complexity. An example of a meta-description is Tromp's binary lambda calculus description of its own interpreter but this nevertheless requires a description of the lambda calculus. Once you start hiding things in the meta-description, you should be careful to admit when you're exceeding the complexity of the description of the NiNOR DCG "instruction set architecture". But, like I said, your approach is interesting.
On Tue, Sep 15, 2026 at 2:11 PM Matt Mahoney <[email protected]> wrote: > 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-Mdd099bc171799d253c554268> > ------------------------------------------ Artificial General Intelligence List: AGI Permalink: https://agi.topicbox.com/groups/agi/T3f8115622f860785-M5036d12c689200efb8f81511 Delivery options: https://agi.topicbox.com/groups/agi/subscription
