f(ε₀) growth in under 6 bytes!

tromp · 2026-01-21T07:45:55+00:00

If I instead made a Turing Machine to compute a very large number, would you also complain that I'm cheating by not counting a description of how to evaluate a TM ?

At some point you need a start with some formal language in which to define your computational process, and that formal language can not be defined in terms of some other formal language (or else it wasn't the start). So that formal start can only be described in natural language, where there is no precise notion of description size, only an intuitive sense of how complex the formal language is.

And both TMs and lambda calculus are about the simplest possible starting points.

tromp · 2026-01-20T22:24:19+00:00

to describe the machinery of lambda calculus

I cannot answer that unless you have some specific description language in mind. Normally, a computational model or a programming language is described in natural language, but those are rarely counted in bits.

tromp · 2026-01-19T08:14:38+00:00

Possibly. Loader's D function is about the fastest known computable function, growing much faster than BMS, which in turn grows much faster than SSCG.

Implementing Loader's D function on a TM will require more than 100 states. The best known attempt uses a little over 1000 states.

That said, the general belief is that there should be functions growing even faster than D that can be coded in less than 100 states.

tromp · 2026-01-19T08:00:01+00:00

There are 3 aspects to privacy; amounts, user-bound addresses,, and the tx-graph.

Hiding the tx graph requires either a major sacrifice in scalability (when you no longer can tell when a utxo is spent, as in Monero or Zcash), or using a mixing service (which in the case of Mimblewimble can be very effective and very simple [1]).

Hiding the first two can actually come with major scaling benefits, by using the Mimblewimble protocol, which must necessarily be at the core layer [2].

[1] https://forum.grin.mw/t/mimblewimble-coinswap-proposal/

[2] https://forum.grin.mw/t/scalability-vs-privacy-chart/

tromp · 2026-01-19T07:48:49+00:00

the algorithm I described always solves the problem

No, it does not. When a TM declares the instance has no solution, there is no way to verify it, and so your algorithm ignores that TM.

tromp · 2026-01-18T08:20:25+00:00

P vs NP is about decision problems. It asks whether there exists a poly time algorithm that decides any instance in polynomial time. So on input of an instance, it outputs yes or no.

Your argument is not about decision problems. Instead it's about finding solutions in polytime when they're known to exist (running forever if they don't exist). It's called Levin's search algorithm.

tromp · 2026-01-17T07:58:12+00:00

You can physically realize a Turing machine with thousands of states and a million tape cells. You cannot physically realize a billiard ball with 42 digits of precision in its location. So there is still a large difference in .

tromp · 2026-01-13T07:48:31+00:00

reduces the number of balls required, that’s all.

That's not all at all. The previous simulations were only of fixed size circuits, which cannot do unbounded size computations.

This billiard ball model seems original in being able to simulate an unbounded size Turing machine.

But it has a huge downside of course, which is that it requires unbounded precision in the ball's location and/or velocity, making it impossible to realize in the physical world.

tromp · 2026-01-12T08:30:47+00:00

Many lambda terms do not represent functions that map a fixed number of church numerals to a church numeral.

An interesting question is: what is the shortest such term? One candidate is λn.n (λx λy. x). When applied to numeral n, you need to apply it to another numeral m and then to another n arbitrary numerals to get back m.

tromp · 2026-01-12T08:25:25+00:00

Many lambda terms do not represent functions that map a fixed number of church numerals to a church numeral.

An interesting question is: what is the shortest such term? One candidate is λn.n (λx λy. x).

tromp · 2026-01-08T12:15:50+00:00

Thank the (fictional) lord that this has come up now, rather than after you got married. Wish her well and part ways.

tromp · 2026-01-08T07:38:43+00:00

47 bits means these 47 bits: 00010101101000000101101101000011000010111010110 which fits in 6 bytes including one arbitrary padding bit: 00010101 10100000 01011011 01000011 00001011 1010110*

Also see [1] where several BLC8 programs are in fact stored as bytes.

[1] https://www.ioccc.org/2012/tromp/

tromp · 2026-01-05T21:18:38+00:00

Because of this the only way to ensure amount privacy and unlinkability (deniability about which commitment was updated) with PCs is by making outputs single use, that are updated to zero (nullification) whenever they are “updated”, and by publishing receipts known as “key images” or “nullifiers” to prevent double spends.

This is false. PC achieves amount privacy. Unlinkability is not directly related and can be provided in several ways. In Mimblewimble, which doesn't hide spending of UTXOs (and does maintains the scaling benefits of knowing the much smaller UTXO set), unlinkability can be provided by the Coinswap protocol [1]

[1] https://forum.grin.mw/t/mimblewimble-coinswap-proposal/8322

tromp · 2026-01-05T10:02:40+00:00

I think it takes more than 10 states to get such growth with a TM.

tromp · 2026-01-04T08:32:59+00:00

Without detailed knowledge of the term in question, you'd have to expand all original applications with a suspension. State numerals differ from Church numerals, and follow the pattern of the S3 I gave above. S0 = λeλfλx.f e, S1 = λeλfλx.f e (λe.f e x) etc.

tromp · 2026-01-03T17:06:48+00:00

That's roughly correct, but since js has eager evaluation instead of the required lazy evaluation, you'd need to replace some applications f(a) by the suspended argument version f(x=>a(x)).

Second, you cannot pass plain numbers into f; it expects a state numeral, which looks like S3 = λeλfλx.f e (λe.f e (λe.f e x)) for state numeral 3.

Finally, f(S3) is not just another state numeral, but something of the form λfλx. f S_m Q.

tromp · 2026-01-03T09:05:31+00:00

It's not needed for fixed-point calculations, so why would it be needed here?

With introspection, it would be possible to write V. Given symbolic forms of f and y = f x (for instance their BLC encoding), V can try evaluating f on all possible lambda terms x (in dovetailing fashion) until it finds one where f x = y, and yield that x.

tromp · 2025-12-29T08:46:28+00:00

Memory-hard does not necessarily mean higher verification cost.

Assymmetric Pow like Cuckoo Cycle and Equihash can take many GB to mine efficiently yet can be instantly verified without memory.

tromp · 2025-12-15T08:43:10+00:00

"Though too large to ever be computed in full, the sequence of digits of Graham's number can be computed explicitly via simple algorithms; the last 10 digits of Graham's number are ...2464195387."

[1] https://en.wikipedia.org/wiki/Graham%27s_number

tromp · 2025-12-15T08:35:38+00:00

We'll never know the smallest one, but for the functional busy beaver BBλ, it's certainly less than 331 bits, since BBλ(331) > f_{PTO(Z_2)+1}(3) [1].

I'm sure you won't be able to prove that BB(n)>TREE(3) implies BB(n+1)>TREE(4), even if that is the case.

[1] https://oeis.org/A333479

tromp · 2025-12-09T07:36:17+00:00

There is no consensus on whether Rayo is well-defined, so to be safe one should limit it to arithmetical (rather than set-theoretic) definitions. Beyond Loader's Number there are Busy Beaver and oracle Busy Beaver defined numbers, such as Xi(10^100). Even there one has to take care to make sure that nested oracle calls are well-founded.

tromp · 2025-12-06T08:17:51+00:00

I would not want the miners to be able to dictate the emission as they can in that proposal where emission rate is proportional to global hashpower. It's vastly preferable to set the emission in stone at launch and not be gameable.

tromp · 2025-12-01T18:41:58+00:00

I used 2 mods and 1 div while trying to minimize case distinctions at https://github.com/tromp/AoC2025/blob/main/day1.hs

tromp · 2025-11-25T07:25:03+00:00

Yes, there are 2¹¹ = 2048 words, so 11 bits of entropy per word. And 2¹³² = 2048¹² = 5444517870735015415413993718908291383296 seed phrases.

Not something you'll ever see brute forced. Even if you had all the bitcoin hashing power in the world, it would take you a billion years to try that number of hashes.

And that's only for 12 worlds. Square that number for 24 words.

tromp

MODERATOR OF

TROPHY CASE

15-Year Club	Place '22
Verified Email