> 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.
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 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.
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.
> 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).
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.
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...
reply