Comment by LegionMammal978
3 years ago
It's interesting, trying to figure out the conceptual basis for the greater power-per-bit of BLC compared to classical TMs. I wonder if it simply has to do with how β-reduction can pack so many more copy-and-pastes into a byte than TM states can, especially relative to the normal form that we use to define BB_λ. At small sizes, classical TMs are forced to do weird Collatz-like tricks, whereas BLC gets nearly-instant exponentiation. Do you have any thoughts on this?
(Also, I've been thinking of how that BB_λ conjecture might be proven. One strategy I'm thinking of for sufficiently large n would be to create a compression scheme for TMs which omits many copies of machines and trivial machines that cannot contribute to BB_TM, to get past the naive 2n(2+log₂(n+1))-bit bound. Then, we create a BLC program with a decompressor and a TM interpreter, to which a compressed TM can be appended. But the compression would have to be good enough to get around the overhead of bit sequences not being natively expressible in BLM.)
Binary Lambda Calculus seems to spend its bits much more wisely than a Turing Machine encoding, working at a much higher level of abstraction. Defining and applying functions performs more useful work than moving a tape head around and jumping from state to state. The Turing Machine is also severely hampered by the pure sequential nature of the tape, where lambda calculus has access to all kinds of easily defined data structures.
> One strategy I'm thinking of for sufficiently large n would be to create a compression scheme for TMs
The universal variant https://oeis.org/A361211 of the lambda busy beaver can easily simulate any binary encoded TM with fixed overhead.
> Binary Lambda Calculus seems to spend its bits much more wisely than a Turing Machine encoding, working at a much higher level of abstraction. Defining and applying functions performs more useful work than moving a tape head around and jumping from state to state.
That's what I mean by β-reduction being a more powerful operation: it can copy a term into arbitrary points in the program. (In the BB context, I like to think of BLC in terms of substitution rather than functions.) So I wonder if the comparison is somewhat biased, since applying a TM transition is logically simpler than applying a BTC β-reduction, which involves recursively parsing the current state, substituting, and reindexing.
> The Turing Machine is also severely hampered by the pure sequential nature of the tape, where lambda calculus has access to all kinds of easily defined data structures.
I'd say TMs have plenty of data structures, but most of the useful ones are weird and alien since the the control flow has to be encoded on the tape alongside the data, vs. BLC which can precisely direct where a term should be substituted. The real hamper IMO is the locality of the tape: a TM can't move a block of data across another block of data on the tape without wasting valuable states.
> The universal variant https://oeis.org/A361211 of the lambda busy beaver can easily simulate any binary encoded TM with fixed overhead.
Of course; the trick is to go from n + c bits to n bits.
One thing that comes to mind is function application, which begets recursion. This is the last quarter of the example program's encoding, while the example TM has enough space for 6 states and no concept of a "goto" or "jmp" that would simulate recursion.
On the contrary, 36 of its 60 bits are dedicated to goto labels. Although you're right that TMs cannot "call" a state then "return" to the caller, as would be expected from a reusable function. Regardless, for busy beaver purposes, most of TMs' state tends to be encoded in the tape rather than the state graph, so I suspect it's the differences in the means of data manipulation that create such a gap. (E.g., with substitution, you can easily move a term across an arbitrary amount of garbage.)