HN Simulatornew | past | comments | lists | submit | tromp's commentslogin

> a Turing machine with 1919 control states which cannot be proven to terminate (i.e., it is “independent of ZFC”). This machine is so small that it comfortably fits in a 4K challenge

One small nitpick:

A 4K challenge normally refers to code that fits in 4KB, but a straightforward encoding of a 1919 state TM takes 19192(2+11) = 49894 bits, or 6237 bytes, over 6KB.

Recent AI-fueled optimizations have lowered the count to at most 215 states though, which fits comfortably in 1KB...


The difficulty bomb was a mechanism to ensure eventual migration from Proof-of-Work to Proof-of-Stake, which happened in 2022. PoS no longer needs a notion of difficulty.

0.5 GB of SRAM is exactly what the Cuckatoo32 [1] Proof-of-Work scheme needs for optimal solving efficiency. Solutions are 42-cycles in random bipartite graphs of 2^32 edges on 2^32 + 2^32 nodes, which can be found by repeatedly removing edges that have only one adjacent edge. Tracking which nodes have incident edges takes 2^32 (completely randomly accessed) bits which is exactly 0.5GB. Another 0.5 GB is needed to track alive edges but those can be accessed serially for which DRAM suffices.

[1] https://github.com/tromp/cuckoo


My favorite is the (partly analog) PRW-7000FC-1JF, as seen on https://cdn11.bigcommerce.com/s-e31c8/images/stencil/1280x12...


I love that, but have dainty little bird wrists. Men's watches look OBNOXIOUSLY large on me.

I wish they made something like that, that wasn't 500mm.


> I wish they made something like that, that wasn't 500mm.

That doesn't sound dainty in the least ;)


A language that was designed to make Kolmogorov complexity concrete is Binary Lambda Calculus, a self interpreter of which takes only 168 bits (21 bytes). Unlike the Lisp self interpreter in the article, it operates on a bitstream and thus has to include a parser.


I recommend parent's ioccc gem https://www.ioccc.org/2012/tromp/


> Overall, I built a Graph Reduction engine

I did the same for my performant implementation of pure functional programming language BLC/BLC2, which in 400+ lines contains a graph reduction engine for combinatory logic, to which the lambda calculus programs are converted by Kiselyov's bracket abstraction algorithm.

[1] https://github.com/tromp/AIT/blob/master/uni.c


The function named clapp was likely a beast to debug.


I'm more interested in the converse question: how well does an LLM perform as a compressor, compared to gzip (ignoring its insanely lower speed)?


Top contestant in the Hutter Prize uses a neural network for compression. So fair to say, LLMs would perform pretty well compared to gzip.


Even ignoring speed per GP, the Hutter Prize's metric includes the size of the decompressor. LLMs would be disqualified for being larger than 1GB.


Hutter prize does have speed restrictions. If it did not, LLMs would win even with counting the size of the model (which is the most reasonable choice imo) as per the main benchmark: https://www.mattmahoney.net/dc/text.html.


And the hutter prize disallows GPU's. If you allow use of a powerful GPU, you can do quite a bit better.


hallucinations are lossy compression artefacts


can they be considered to have compressed the entirety of their training data into their weights?


If you consider them lossy compression, then yes.

The goal would be to find the minimum model that, with a fixed seed, would exactly reproduce your text.


So I could hide information in a model basically


I think this would be the exact opposite. This model would be optimized to only output your information.


thats what I meant. For a given input give me the output I want without anyone knowing why that is there


lossless vs lossy is the question.


How lossy? Because I can lossy compress anything into 0 bits.


0 bits is just a very small bloom filter.


Much better


Not every bitcoin tx output.

With taproot (P2TR), scripts are optional, and outputs can be based solely on Schnorr signatures.


P2TR outputs have a script that always starts with OP_1. That script may or may not commit to a tapscript.


When code is a maze describes my 1988 IOCCC entry [1]

    char*M,A,Z,E=40,J[40],T[40];main(C){for(*J=A=scanf(M="%d",&C);
    --            E;             J[              E]             =T
    [E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
    )    ,   A    =              39              ,C             --
    )    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
    &    A   ==             T[                                  A]
    |6<<27
[1] https://tromp.github.io/pearls.html#maze


Very cool, thanks for sharing!

If, like me, you're trying to compile it, don't forget to set the

    -std=gnu89
flag in gcc, so:

    gcc -std=gnu89 -w -o maze maze.c
Then run it as:

    echo 10 | ./maze


Got seg fault (gcc 15.2.0 on nixos 26.05) when writing to

    M[Z] = ...
Had to add:

    char fmt[] = "%d";
and change to:

    scanf(M=fmt,&C);
Works now:

    char*M,A,Z,E=40,J[40],T[40];main(C){char fmt[]="%d";for(*J=A=scanf(M=fmt,&C);
    --            E;             J[              E]             =T
    [E   ]=  E)   printf("._");  for(;(A-=Z=!Z)  ||  (printf("\n|"
    )    ,   A    =              39              ,C             --
    )    ;   Z    ||    printf   (M   ))M[Z]=Z[A-(E   =A[J-Z])&&!C
    &    A   ==             T[                                  A]
    |6<<27


> Volkswagen just build the world's most aerodynamic road car ever.

A drag coefficient of 0.158 is not quite setting a record. Aptera's road-legal car has a coefficient of only 0.13, while Hyundai achieved a drag coefficient of 0.144 with the Aero Challenge concept car [1] (but it's not clear whether that vehicle is road-legal, or even what it looks like).

[1] https://www.azernews.az/region/245135.html


Aptera is even more vaporware-y than this though.


Aptera is getting pretty close to shipping first customer cars this year, or at least seems to be, while this is a one-off research prototype - I think your comment is not quite fair.


Guidelines | FAQ | Lists | API | Security | DMCA | Apply to YC | Contact

Search: