4 ms·

The article discusses different encodings of numbers to give non-dense representations of numbers exceeding (2^64)-1. (These representations are inherently non-

by addaon 3y ago

The article discusses different encodings of numbers to give non-dense representations of numbers exceeding (2^64)-1. (These representations are inherently non-dense by the pigeonhole principle.) But I feel like this is missing a key point. A 64-bit string that we agree represents only numbers can represent 18446744073709551616 different numbers. The choice of what numbers are represented is completely up to us. If we want certain properties (dense integers) we end up with the highest being 18446744073709551615. If we want other properties (nearly logarithmic distribution, signedness, and good mapping to hardware for arithmetic) we might end up with FP64 with a maximum value around 10^308. And if we want no interesting property constraints except being dual to a program on a Turing machine, we end up with a busy beaver number. But... remember, we can choose any 18446744073709551616 values we want to be representable. There's no restriction on the interpretation of these strings; or, equivalently, the amount of external information required to explain the interpretation of these strings is unbounded. As a result, we can choose any computable number to be encoded by the string 64'b1, or by any other string, and exceed any desired bounds.

tromp 3y ago
> we can choose any computable number to be encoded by the string 64'b1 First of all, every finite number is computable by definition. And second, your encodings will, unlike those in the lambda calculus, be completely arbitrary. PS: in my self-delimiting encoding of the lambda calculus, there are only 1058720968043859 < 2^50 closed lambda terms of size up to 64 [1]. [1] https://oeis.org/A114852 https://oeis.org/A114852
- Kranar 3y ago
  >First of all, every finite number is computable by definition. You likely mean every integer or rational is computable (although not by definition). There are finite real numbers that are not computable, in fact most of them are not.
  - tromp 3y ago
    Right; I meant finite integer.
    - TheNewAndy 3y ago
      What is the 100th busy beaver number? I believe this is an integer, and I also believe it is not computable
      - tromp 3y ago
        As a number, N=BB(100) is trivially computable by the program "output N". What you really mean is that the function BB(.) itself is uncomputable.
        TheNewAndy 3y ago
        I believe you are correct, however I am struggling to see how. If you have the time to help me with my understanding then I would appreciate it. I'm looking at wikipedia's formal definition, which says that for x to be computable, you need to provide a function from naturals to integers such that if you pick a denominator of a fraction (n), this function can give the numerator such that (f(n)-1)/n and (f(n)+1)/n end up straddling the value which is computable. So, for an integer N, you make f(x) = xN then (f(n)-1)/n = N-(1/n) and (f(n)+1)/n = N+(1/n). Therefore, for any integer N, it is computable. Now, what is stopping me from doing something similar with a real? If I say: f(x) = floor(xN) Now (f(n)-1)/n = floor(n*N)-(1/n) It is at this point where I realise I need to go to bed and sleep. If you see this and have the time to explain to me where it falls apart with reals, then I will be most happy. To be clear - I'm quite sure I am wrong, and this isn't me being passive aggressive about it.
        tromp 3y ago
        You were looking at the definition of a computable real number [1]. The issue there is whether you can approximate the number arbitrarily well. An issue that is nonexistent in integers, as you note in > Therefore, for any integer N, it is computable. > If I say: f(x) = floor(xN) For many definitions of a real, it's not at all clear whether you can compute this f(x). The ability to compute f already amounts to being able to approximate f arbitrarily well. For example, for Chaitin's number, you cannot compute your f() except for a few small values of N. [1] https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
- tshaddox 3y ago
  It's interesting that you are counting how many lambda calculus terms can fit into 64 bits given a particular encoding, but you're not making room in the 64 bits for an explanation of how your encoding works (let alone how lambda calculus works!). Of course, any encoding you used to include an "explanation" in the 64 bits would itself require some explanation. I guess what I'm getting at is that I'm not sure that your approach is any less arbitrary than any other approach.
  - tromp 3y ago
    Before I can understand your comment, could you please add an explanation about how the English language works? And for whatever language you use to explain that (obviously not English), please provide an explanation for that language as well... sorry; couldn't resist /s
    - tshaddox 3y ago
      I don’t think it’s possible to provide an infinite chain of such explanations, nor am I attempting to define a problem like “find the largest number representable in English with n characters.”
    - MadnessASAP 3y ago
      I think I got this one, just let me finish reading Vol 4 of Principia and I'll type it up.
- addaon 3y ago
  > every finite number is computable by definition Every finite integer is computable. We often represent non-integer numbers. > your encodings will, unlike those in the lambda calculus, be completely arbitrary Well, they /may/ be completely arbitrary. They may not be. The key is to choose encodings that are useful for the problem domain. Admittedly if the problem domain is "winning at the schoolyard game of saying a bigger number," those encodings may look arbitrary for most other purposes. But there's actually an intent to my original comment besides being pedantic. The most general way to think of a 64-bit numeric representation is as a list of 2^64 numbers, feeding into a 2^64:1 mux, with the 64-bit string being the select bits of the mux. (Or, equivalently, a 2^64 entry x arbitrary width ROM with one number per entry, with the 64-bit string being the address input of the ROM. Same thing.) The two questions you must answer, then, are (a) which 2^64 numbers are most useful in your problem domain; and (b) are there hardware optimizations to reduce the (ridiculous) scale of the mux/ROM model that are so valuable that you're willing to make compromises on which numbers you select?
pmayrgundter 3y ago
came here and searched for "busy". good job :) To the sibling comment about arbitrariness, we could use a hybrid where we trade off some bits from IEEE FP to introduce far reaches and also some precision there.. so like, keep 32 bits or 54 bits for IEEE compatibility, then switch to "extended" ranges for e.g. BB numbers, higher alephs, etc.. There was this one system for calculation with infinities that avoided the Hilbert Hotel problem.. can't find it but was called smth like Infinioid or some other play on the name. Would be neat to bolt those on too :) Edit: "grossone" is the calculus for infinities.. love this work! https://www.theinfinitycomputer.com/ https://www.theinfinitycomputer.com/
- chriswarbo 3y ago
  > To the sibling comment about arbitrariness, we could use a hybrid where we trade off some bits from IEEE FP to introduce far reaches and also some precision there.. so like, keep 32 bits or 54 bits for IEEE compatibility, then switch to "extended" ranges for e.g. BB numbers, higher alephs, etc. This sort of trick/hack is the reason why theorems in (algorithmic) information theory involve constant factors. For example, we can define an image compressor which outputs a single `1` when given the Lenna test image[0], and otherwise acts exactly like PNG except prefixing its output with a `0`. To decode: a `1` decodes to the Lenna image, and anything starting with `0` gets decoded as PNG without the leading `0`. This gives perfect compression with no loss of quality, when tested on that Lenna image ;) [0] https://en.wikipedia.org/wiki/Lenna https://en.wikipedia.org/wiki/Lenna
  - ithkuil 3y ago
    Furthermore this method can be scaled up to cover more and more test images, with a modest increase of prefix bits
- pmayrgundter 3y ago
  anyone really interested, i'm just rereading an earlyish (2010) paper by Sergeyev.. it's amazing https://www.theinfinitycomputer.com/wp-content/uploads/2020/11/First.pdf https://www.theinfinitycomputer.com/wp-content/uploads/2020/...
teknopaul 3y ago
Came here to say that. People sometimes mistakenly think that numbers or data in computers exist in some meaningful way. Everything in a computer is a model or record or representation that serves a purpose. All bugs and limits are features.
- chriswarbo 3y ago
  > People sometimes mistakenly think that numbers or data in computers exist in some meaningful way. That's basically Platonism. I think it's a reasonable position for some things, e.g. Booleans (two-valued logic), natural/integer/rational numbers, tuples, lists, binary trees, etc. I think it's meaningful to talk about, say, the number 2, separately from the way it may be encoded in RAM as a model of e.g. the number of items in a user's shopping cart. This position gets less reasonable/interesting/useful as we consider data whose properties are more arbitrary and less "natural"; e.g. there's not much point separating the "essence" of an IEEE754 double-precision float from its representation in RAM; or pontificating about the fundamental nature of a InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState[0] The question in the article is whether lambda calculus is "natural" enough to be usefully Platonic. It's certainly a better candidate than, say, Javascript; although I have a soft spot for combinatory logic (which the author has also created a binary encoding for; although its self-interpreter is slightly larger), and alternatives like concatenative languages, linear combinators (which seem closer to physics), etc. [0] https://web.archive.org/web/20160818035145/http://www.javafind.net/gate.jsp?q=%2Flibrary%2F36%2Fjava6_full_apidocs%2Fcom%2Fsun%2Fjava%2Fswing%2Fplaf%2Fnimbus%2FInternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState.html https://web.archive.org/web/20160818035145/http://www.javafi...
  - addaon 3y ago
    > InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState In Plato's allegory of the cave, this was the true monster casting shadows on the wall.
Sharlin 3y ago
The lower bound on the information content of a string is the length of the shortest program that can output the string (and halt), this is called its Kolmogoroff complexity. Lambda calculus is (one of) the most compact ways to encode programs and requires the least context to interpret. Thus it’s totally fair to say that the largest number encoded in LC in some number of bits is much more fundamental and less arbitrary a candidate than just randomly deciding that "1" now refers to some externally defined large number.
- eru 3y ago
  Something like SKI calculus seems a lot less arbitrary than lambda calculus in terms of representation, perhaps.
  - chriswarbo 3y ago
    The author has also implemented Binary Combinatory Logic. I also find combinators more "natural" than lambda calculus (although the latter is certainly more useful day-to-day!); however, I still find lambda calculus a reasonable foundation since the Binary Lambda Calculus self-interpreter is shorter than the Binary Combinatory Logic self-interpreter (e.g. see the author's page at http://tromp.github.io/cl/cl.html http://tromp.github.io/cl/cl.html )
    - eru 3y ago
      Writing programs in lambda calculus is definitely more enjoyable than in eg SKI calculus. I think if you express your lambda calculus bindings in terms of De Bruijn indices, it might seem less arbitrary, too.
    - MadnessASAP 3y ago
      I don't think your day and my day are quite the same.
      - chriswarbo 3y ago
        Lambda calculus is present in most "modern" programming languages, i.e. those which use lexical scope rather than global or dynamic scope; and those which call functions to return results (especially first-class functions) rather than jumping to subroutines for their effects. It's why Python functions are written with the keyword `lambda`, and it's why Amazon's function-as-a-service product is called Lambda. For example, say you're refactoring some code and come across: def foo(x): return bar(x) You decide to simplify this definition to: foo = bar Congratulations, you've just performed η-reduction! https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reduction https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reducti...

by addaon 3y ago

tromp 3y ago

> we can choose any computable number to be encoded by the string 64'b1 First of all, every finite number is computable by definition. And second, your encodings will, unlike those in the lambda calculus, be completely arbitrary. PS: in my self-delimiting encoding of the lambda calculus, there are only 1058720968043859 < 2^50 closed lambda terms of size up to 64 [1]. [1] https://oeis.org/A114852 https://oeis.org/A114852

Kranar 3y ago
>First of all, every finite number is computable by definition. You likely mean every integer or rational is computable (although not by definition). There are finite real numbers that are not computable, in fact most of them are not.
- tromp 3y ago
  Right; I meant finite integer.
  - TheNewAndy 3y ago
    What is the 100th busy beaver number? I believe this is an integer, and I also believe it is not computable
    - tromp 3y ago
      As a number, N=BB(100) is trivially computable by the program "output N". What you really mean is that the function BB(.) itself is uncomputable.
      - TheNewAndy 3y ago
        I believe you are correct, however I am struggling to see how. If you have the time to help me with my understanding then I would appreciate it. I'm looking at wikipedia's formal definition, which says that for x to be computable, you need to provide a function from naturals to integers such that if you pick a denominator of a fraction (n), this function can give the numerator such that (f(n)-1)/n and (f(n)+1)/n end up straddling the value which is computable. So, for an integer N, you make f(x) = xN then (f(n)-1)/n = N-(1/n) and (f(n)+1)/n = N+(1/n). Therefore, for any integer N, it is computable. Now, what is stopping me from doing something similar with a real? If I say: f(x) = floor(xN) Now (f(n)-1)/n = floor(n*N)-(1/n) It is at this point where I realise I need to go to bed and sleep. If you see this and have the time to explain to me where it falls apart with reals, then I will be most happy. To be clear - I'm quite sure I am wrong, and this isn't me being passive aggressive about it.
        tromp 3y ago
        You were looking at the definition of a computable real number [1]. The issue there is whether you can approximate the number arbitrarily well. An issue that is nonexistent in integers, as you note in > Therefore, for any integer N, it is computable. > If I say: f(x) = floor(xN) For many definitions of a real, it's not at all clear whether you can compute this f(x). The ability to compute f already amounts to being able to approximate f arbitrarily well. For example, for Chaitin's number, you cannot compute your f() except for a few small values of N. [1] https://en.wikipedia.org/wiki/Computable_number https://en.wikipedia.org/wiki/Computable_number
tshaddox 3y ago
It's interesting that you are counting how many lambda calculus terms can fit into 64 bits given a particular encoding, but you're not making room in the 64 bits for an explanation of how your encoding works (let alone how lambda calculus works!). Of course, any encoding you used to include an "explanation" in the 64 bits would itself require some explanation. I guess what I'm getting at is that I'm not sure that your approach is any less arbitrary than any other approach.
- tromp 3y ago
  Before I can understand your comment, could you please add an explanation about how the English language works? And for whatever language you use to explain that (obviously not English), please provide an explanation for that language as well... sorry; couldn't resist /s
  - tshaddox 3y ago
    I don’t think it’s possible to provide an infinite chain of such explanations, nor am I attempting to define a problem like “find the largest number representable in English with n characters.”
  - MadnessASAP 3y ago
    I think I got this one, just let me finish reading Vol 4 of Principia and I'll type it up.
addaon 3y ago
> every finite number is computable by definition Every finite integer is computable. We often represent non-integer numbers. > your encodings will, unlike those in the lambda calculus, be completely arbitrary Well, they /may/ be completely arbitrary. They may not be. The key is to choose encodings that are useful for the problem domain. Admittedly if the problem domain is "winning at the schoolyard game of saying a bigger number," those encodings may look arbitrary for most other purposes. But there's actually an intent to my original comment besides being pedantic. The most general way to think of a 64-bit numeric representation is as a list of 2^64 numbers, feeding into a 2^64:1 mux, with the 64-bit string being the select bits of the mux. (Or, equivalently, a 2^64 entry x arbitrary width ROM with one number per entry, with the 64-bit string being the address input of the ROM. Same thing.) The two questions you must answer, then, are (a) which 2^64 numbers are most useful in your problem domain; and (b) are there hardware optimizations to reduce the (ridiculous) scale of the mux/ROM model that are so valuable that you're willing to make compromises on which numbers you select?

pmayrgundter 3y ago

came here and searched for "busy". good job :) To the sibling comment about arbitrariness, we could use a hybrid where we trade off some bits from IEEE FP to introduce far reaches and also some precision there.. so like, keep 32 bits or 54 bits for IEEE compatibility, then switch to "extended" ranges for e.g. BB numbers, higher alephs, etc.. There was this one system for calculation with infinities that avoided the Hilbert Hotel problem.. can't find it but was called smth like Infinioid or some other play on the name. Would be neat to bolt those on too :) Edit: "grossone" is the calculus for infinities.. love this work! https://www.theinfinitycomputer.com/ https://www.theinfinitycomputer.com/

chriswarbo 3y ago
> To the sibling comment about arbitrariness, we could use a hybrid where we trade off some bits from IEEE FP to introduce far reaches and also some precision there.. so like, keep 32 bits or 54 bits for IEEE compatibility, then switch to "extended" ranges for e.g. BB numbers, higher alephs, etc. This sort of trick/hack is the reason why theorems in (algorithmic) information theory involve constant factors. For example, we can define an image compressor which outputs a single `1` when given the Lenna test image[0], and otherwise acts exactly like PNG except prefixing its output with a `0`. To decode: a `1` decodes to the Lenna image, and anything starting with `0` gets decoded as PNG without the leading `0`. This gives perfect compression with no loss of quality, when tested on that Lenna image ;) [0] https://en.wikipedia.org/wiki/Lenna https://en.wikipedia.org/wiki/Lenna
- ithkuil 3y ago
  Furthermore this method can be scaled up to cover more and more test images, with a modest increase of prefix bits
pmayrgundter 3y ago
anyone really interested, i'm just rereading an earlyish (2010) paper by Sergeyev.. it's amazing https://www.theinfinitycomputer.com/wp-content/uploads/2020/11/First.pdf https://www.theinfinitycomputer.com/wp-content/uploads/2020/...

teknopaul 3y ago

Came here to say that. People sometimes mistakenly think that numbers or data in computers exist in some meaningful way. Everything in a computer is a model or record or representation that serves a purpose. All bugs and limits are features.

chriswarbo 3y ago
> People sometimes mistakenly think that numbers or data in computers exist in some meaningful way. That's basically Platonism. I think it's a reasonable position for some things, e.g. Booleans (two-valued logic), natural/integer/rational numbers, tuples, lists, binary trees, etc. I think it's meaningful to talk about, say, the number 2, separately from the way it may be encoded in RAM as a model of e.g. the number of items in a user's shopping cart. This position gets less reasonable/interesting/useful as we consider data whose properties are more arbitrary and less "natural"; e.g. there's not much point separating the "essence" of an IEEE754 double-precision float from its representation in RAM; or pontificating about the fundamental nature of a InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState[0] The question in the article is whether lambda calculus is "natural" enough to be usefully Platonic. It's certainly a better candidate than, say, Javascript; although I have a soft spot for combinatory logic (which the author has also created a binary encoding for; although its self-interpreter is slightly larger), and alternatives like concatenative languages, linear combinators (which seem closer to physics), etc. [0] https://web.archive.org/web/20160818035145/http://www.javafind.net/gate.jsp?q=%2Flibrary%2F36%2Fjava6_full_apidocs%2Fcom%2Fsun%2Fjava%2Fswing%2Fplaf%2Fnimbus%2FInternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState.html https://web.archive.org/web/20160818035145/http://www.javafi...
- addaon 3y ago
  > InternalFrameInternalFrameTitlePaneInternalFrameTitlePaneMaximizeButtonWindowNotFocusedState In Plato's allegory of the cave, this was the true monster casting shadows on the wall.

Sharlin 3y ago

The lower bound on the information content of a string is the length of the shortest program that can output the string (and halt), this is called its Kolmogoroff complexity. Lambda calculus is (one of) the most compact ways to encode programs and requires the least context to interpret. Thus it’s totally fair to say that the largest number encoded in LC in some number of bits is much more fundamental and less arbitrary a candidate than just randomly deciding that "1" now refers to some externally defined large number.

eru 3y ago
Something like SKI calculus seems a lot less arbitrary than lambda calculus in terms of representation, perhaps.
- chriswarbo 3y ago
  The author has also implemented Binary Combinatory Logic. I also find combinators more "natural" than lambda calculus (although the latter is certainly more useful day-to-day!); however, I still find lambda calculus a reasonable foundation since the Binary Lambda Calculus self-interpreter is shorter than the Binary Combinatory Logic self-interpreter (e.g. see the author's page at http://tromp.github.io/cl/cl.html http://tromp.github.io/cl/cl.html )
  - eru 3y ago
    Writing programs in lambda calculus is definitely more enjoyable than in eg SKI calculus. I think if you express your lambda calculus bindings in terms of De Bruijn indices, it might seem less arbitrary, too.
  - MadnessASAP 3y ago
    I don't think your day and my day are quite the same.
    - chriswarbo 3y ago
      Lambda calculus is present in most "modern" programming languages, i.e. those which use lexical scope rather than global or dynamic scope; and those which call functions to return results (especially first-class functions) rather than jumping to subroutines for their effects. It's why Python functions are written with the keyword `lambda`, and it's why Amazon's function-as-a-service product is called Lambda. For example, say you're refactoring some code and come across: def foo(x): return bar(x) You decide to simplify this definition to: foo = bar Congratulations, you've just performed η-reduction! https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reduction https://en.wikipedia.org/wiki/Lambda_calculus#%CE%B7-reducti...