3 ms·

I'm confused by your 'additively optimal' definition. Suppose that the objects we want to describe are strings of bits, and the description method D is just "li

I'm confused by your 'additively optimal' definition. Suppose that the objects we want to describe are strings of bits, and the description method D is just "listing the bits out in a sequence". Then surely no BLC term can describe the same sequence of bits with only a constant amount of overhead.

tromp 3y ago
Then D is just identity, or λ 1, using only 4 bits of overhead?!
- LegionMammal978 3y ago
  If a 'description' of an 'object' is defined to always be a valid term or program that operates on provided input, then I don't see why Turing machines wouldn't nearly as easily be 'additively optimal' in your sense. For most universal Turing machines that represent an input bit as a constant-sized word (such as Neary & Woods' 8-state 4-symbol UTM [0], which represents each input bit as two symbols, or even their 15-state 2-symbol UTM [1], which uses a slightly trickier encoding), you could add a few states extra to expand new input on the fly, shifting any existing data to the left as necessary. The only precondition is that the existing data has a boundary recognizable by a finite-state machine; this condition can always be met with O(n) extra states by adding an extra symbol to the UTM's description to represent the boundary, then converting it back to a 2-symbol machine. Regardless, I'd still consider your 'additively optimal' to be a strange definition, given that BLT programs get to have their input bits pre-expanded as a valid sequence of boolean terms for free. If all it means is that the input format accepted by D is a subset of the input format accepted by U, then many existing small UTMs could easily meet it just by restricting D's input format. [0] https://doi.org/10.1016/j.tcs.2006.06.002 https://doi.org/10.1016/j.tcs.2006.06.002 [1] https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_2009.pdf https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_...
  - tromp 3y ago
    > I don't see why Turing machines wouldn't nearly as easily be 'additively optimal' in your sense. 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. > you could add a few states extra to expand new input on the fly, shifting any existing data to the left as necessary. That would be more than "a few" states, and could easily add thousands of bits to the UTM size. > given that BLT programs get to have their input bits pre-expanded as a valid sequence of boolean terms for free. I guess you mean BLC programs. 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. > If all it means is that the input format accepted by D is a subset of the input format accepted by U The input format for D can be all binary strings, e.g. if D is identity (assuming the delimited input model). > many existing small UTMs could easily meet it just by restricting D's input format. I don't know what this means. 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.
    - LegionMammal978 3y ago
      > 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.

tromp 3y ago

Then D is just identity, or λ 1, using only 4 bits of overhead?!

LegionMammal978 3y ago
If a 'description' of an 'object' is defined to always be a valid term or program that operates on provided input, then I don't see why Turing machines wouldn't nearly as easily be 'additively optimal' in your sense. For most universal Turing machines that represent an input bit as a constant-sized word (such as Neary & Woods' 8-state 4-symbol UTM [0], which represents each input bit as two symbols, or even their 15-state 2-symbol UTM [1], which uses a slightly trickier encoding), you could add a few states extra to expand new input on the fly, shifting any existing data to the left as necessary. The only precondition is that the existing data has a boundary recognizable by a finite-state machine; this condition can always be met with O(n) extra states by adding an extra symbol to the UTM's description to represent the boundary, then converting it back to a 2-symbol machine. Regardless, I'd still consider your 'additively optimal' to be a strange definition, given that BLT programs get to have their input bits pre-expanded as a valid sequence of boolean terms for free. If all it means is that the input format accepted by D is a subset of the input format accepted by U, then many existing small UTMs could easily meet it just by restricting D's input format. [0] https://doi.org/10.1016/j.tcs.2006.06.002 https://doi.org/10.1016/j.tcs.2006.06.002 [1] https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_2009.pdf https://mural.maynoothuniversity.ie/12416/1/Woods_FourSmall_...
- tromp 3y ago
  > I don't see why Turing machines wouldn't nearly as easily be 'additively optimal' in your sense. 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. > you could add a few states extra to expand new input on the fly, shifting any existing data to the left as necessary. That would be more than "a few" states, and could easily add thousands of bits to the UTM size. > given that BLT programs get to have their input bits pre-expanded as a valid sequence of boolean terms for free. I guess you mean BLC programs. 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. > If all it means is that the input format accepted by D is a subset of the input format accepted by U The input format for D can be all binary strings, e.g. if D is identity (assuming the delimited input model). > many existing small UTMs could easily meet it just by restricting D's input format. I don't know what this means. 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.
  - LegionMammal978 3y ago
    > 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.