> Could you construct a 2-symbol UTM whose own encoding is under, say, 10,000 bits in size? If it takes 10,000 bits then it would not seem as easy as the 232 bi

> Could you construct a 2-symbol UTM whose own encoding is under, say, 10,000 bits in size? If it takes 10,000 bits then it would not seem as easy as the 232 bit universal lambda machine. Ah, if you're specifically talking about self-encoding size as a yardstick, then you've got me: I spent yesterday afternoon adapting an existing UTM construction to take a look at this. While I managed to get most of the way there within ~40 states, it would take ~4 megabits to encode itself, by my estimation. Though it's difficult to tell just what the lower bound is, since the more states you allow in the UTM, the shorter you can make the encoding. I still suspect that 5 kilobits should be more than enough for someone actually good at TM golfing. > That criticism seems unfair, since the lambda machine model has no primitive notion of bits. Thus there is no expansion, only representation of bits in the lambda calculus. > The input format for D can be all binary strings, e.g. if D is identity (assuming the delimited input model). > A UTM should parse the description of a TM from its input, and simulate that TM on the remainder of input. If it does that, then it would be additively optimal. It cannot assume any restriction on that remainder of input. Having played with the UTM problem, I have a better understanding of the point I was trying to make. Consider a thought experiment, where you try to construct a UTM by making a TM that simply evaluates a BLC term on the tape. This TM by itself would still not be 'additively optimal' by your rules! It would also need an incremental input encoder to convert packed bits into BLC terms, as well as a lazy evaluation model to trigger it only when needed. Thus, I think your UTM rules are a bit unfairly strict. A UTM that abides by those rules, as well as being additively optimal, must further be 'concatenatively optimal', in that for any description D, bit string s, and bit stream t, there must exist an encoding <D, s>, no longer than <D> + s, such that <D, s> + t is equivalent to <D> + s + t. (That is, adding a fixed prefix before the input cannot extend the encoding by more than the length of the prefix.) But by itself, the language of BLC programs is not and cannot be concatenatively optimal! This is the expansion I was talking about: a given bitstring can't be represented as efficiently inside the BLC encoding as it can outside the encoding. To get a concatenatively optimal language, you'd have to formulate it as a (term, input) pair, where the input is a raw binary string that must be encoded before feeding it into the actual program. (This isn't an issue entirely unique to BLC: a TM model mandating an empty initial tape also couldn't be concatenatively optimal.) So then, one might ask, where is the implementation of this input encoding within your 232-bit BLC term? Nowhere! Its only task is to 'interrogate' the first several input bits (as already encoded) to parse the description D. And when it finishes constructing the term corresponding to D, its job is done, since the remaining input bits are already encoded in a form it can use. So if we try to trace the point where the encoding actually happens, we can only conclude that it occurs wholly outside the lambda calculus. But the encoding step is entirely necessary for concatenative optimality to hold. That is all to say, self-encoding size is an easily gameable metric (in the trivial case, you could make a universal machine that's also a quine, so that it can encode itself in 1 bit), and your idea of additive optimality is tied very closely to the power of the input model defined outside the system. (The input model can also be easily gamed: imagine that each cons term of the input, alongside the head and tail, also supplied a universal program. Under that input model, the program within the system would be trivial.) By saying that a UTM only gets 2 symbols and has to accept dense input, you mandate a very weak input model, so of course it will be tough to get it to accept arbitrary data. --- But in the bigger picture, I'd like to note that I'm not trying to dunk on BLC here, nor on the lambda calculus in general: clearly, it's very efficient at representing and simulating itself, and no simple TM model can simulate itself nearly as easily. And that's all well and good if you want a model where you can treat code as data and do other stuff like that. But I maintain that this self-representation doesn't make it more universal, or otherwise more fundamental, than the TM model, which aims to use as simple a rule as possible for transitioning from one configuration to the next, at the cost of having heterogeneous code and data. (Imperatively speaking, lambda-calculus reductions would seem closer in power to a random-access machine, or perhaps a TM on a branching tape.) So being generous, I'd say that both are equally as fundamental, they're just trying to excel at two different goals.