5 ms·

Please no more comments to the extent of "i can define a much larger number in only 1 bit". What makes my blog post (hopefully) interesting is that I consider t

by tromp 8mo ago

Please no more comments to the extent of "i can define a much larger number in only 1 bit". What makes my blog post (hopefully) interesting is that I consider tiny programs for computing huge numbers in non-cheating languages, that are not specifically equipped for doing so.

hcs 8mo ago
Surely you've been on HN long enough to know people just read the headline. Not that it would stop all sniping, but that headline doesn't even include "program" (or "compute").
- tromp 8mo ago
  > that headline doesn't even include "program" (or "compute"). Neither does Scott's article titled "Who Can Name the Bigger Number?" [1] The title is just a way to invite the reader to find out why the answer isn't simply 2^64-1. [1] https://news.ycombinator.com/item?id=9058986 https://news.ycombinator.com/item?id=9058986
alecco 8mo ago
I think "representable" is misleading. Nice post, though.
orlp 8mo ago
An interesting follow-up question is, what is the smallest number unable to be encoded in 64 bits of binary lambda calculus?
- tromp 8mo ago
  BLC can output any literal 60 bit string x as the 64-bit (delimited) program 0010 x, so in that sense it would be some 61 bit number. But if ask about just lambda calculus terms without the binary input, then I think it would be some small number of at most 10 bits. BBλ looks at the normal form size so it cannot even reach numbers 0,1,2,3, and 5.
petalmind 8mo ago
Question: but how many different numbers can you fit in 64 bits using your encoding (sorry I understand the general approach but I have no idea how that fast hierarchy works). I guess it's still 2^64 different numbers? So basically you have a very low density of representable numbers (2^64 / w218), I wonder how quickly it grows as you use more and more 1-bits, and is there even a correlation between the bit pattern and the corresponding number value?
tdb7893 8mo ago
So HN can't do this because I don't think it tracks all clicks but I've been of the opinion for a while that most social media should have the option for posts to not allow people to comment unless they've actually clicked on the link.
- b65e8bee43c2ed0 8mo ago
  like the rest of simple solutions to complex problems suggested by otherwise (seemingly) intelligent people on HN, it simply wouldn't work. do you really not see why?
  - tdb7893 8mo ago
    Are you talking about that people could just click on the link then not actually read it? The thing is that clicking on the link then closing is serves as both a slight barrier to entry targeted at the people who comment without reading and also a reminder that there is an actual article to comment on. It's not going to fix discourse but the theory behind it is to be a slight nudge to get people who don't click to at least consider reading the article (or just not comment) while being an invisible change to people who actually read the article. It's not meant to be a magic fix, it's just some something I would want (though I'm biased since I click on links so there's no downside to me).
    - ShroudedNight 8mo ago
      Wouldn't browser prefetching subvert these small frictions to entry?
      - tdb7893 8mo ago
        I think I've seen sites trying to track outbound clicks recently, has prefetching made that impossible? I don't know the implementation but I've seen the browser sending requests that track clicks while investigating other stuff (idk whether it's working accurately though). Edit: to be clear, it's not like I've researched this proposal since I don't work for social media companies. It's just a feature I wish I could have on my posts.
deathanatos 8mo ago
Which is what makes the headline bait. We start with "The largest number representable in 64 bits" (which obviously depends on the representation, and as the baited comments point out, if that's freely settable, we can just set it arbitrarily high). But the body then moves the goalposts to "using a Turning machine", "using a Turing machine with specific parameters fixed", to "lambda calculus", etc. This is now (at least) "The largest number representable by a Turning machine of fixed parameters that can then be squeezed into 64 bit." (I don't remember my lambda calc, so … eh.)
deleted 8mo ago
[deleted]
omoikane 8mo ago
A better title might have been "fastest growing function with 64bit arguments". The main value of this article is really the various functions that take larger strides to cover a finite range that's significantly larger than 2^64-1.
- tromp 8mo ago
  If it were about coding fast growing functions, then it would have had to mention the incredible 47-bit lambda calculus term λn. n n (λe λx. x e x) (λm. m (λe. m e m)) that achieves f_ε₀ growth. But it expects its argument to be a so-called state numeral n, rather than a Church numeral, and even state numeral 2, which is \e\f\x.f e (\e.f e x) is already 32 bits long, making the application take 2+47+32=81 bits, more than the required 64.
LanceH 8mo ago
I found the problem itself to be poorly defined. > What if we allow representations beyond plain data types? Since we want representations to remain computable, the most general kind of representation would be a program in some programming language. But the program must be small enough to fit in 64 bits. If you bring in a whole programming language, you bring in a lot more than 64 bits. This all seems to be the math equivalent of saying you wrote a program in 2k when the first line is "import 'megalibrary'".

by tromp 8mo ago

hcs 8mo ago

Surely you've been on HN long enough to know people just read the headline. Not that it would stop all sniping, but that headline doesn't even include "program" (or "compute").

tromp 8mo ago
> that headline doesn't even include "program" (or "compute"). Neither does Scott's article titled "Who Can Name the Bigger Number?" [1] The title is just a way to invite the reader to find out why the answer isn't simply 2^64-1. [1] https://news.ycombinator.com/item?id=9058986 https://news.ycombinator.com/item?id=9058986

alecco 8mo ago

I think "representable" is misleading. Nice post, though.

orlp 8mo ago

An interesting follow-up question is, what is the smallest number unable to be encoded in 64 bits of binary lambda calculus?

tromp 8mo ago
BLC can output any literal 60 bit string x as the 64-bit (delimited) program 0010 x, so in that sense it would be some 61 bit number. But if ask about just lambda calculus terms without the binary input, then I think it would be some small number of at most 10 bits. BBλ looks at the normal form size so it cannot even reach numbers 0,1,2,3, and 5.

petalmind 8mo ago

Question: but how many different numbers can you fit in 64 bits using your encoding (sorry I understand the general approach but I have no idea how that fast hierarchy works). I guess it's still 2^64 different numbers? So basically you have a very low density of representable numbers (2^64 / w218), I wonder how quickly it grows as you use more and more 1-bits, and is there even a correlation between the bit pattern and the corresponding number value?

tdb7893 8mo ago

So HN can't do this because I don't think it tracks all clicks but I've been of the opinion for a while that most social media should have the option for posts to not allow people to comment unless they've actually clicked on the link.

b65e8bee43c2ed0 8mo ago
like the rest of simple solutions to complex problems suggested by otherwise (seemingly) intelligent people on HN, it simply wouldn't work. do you really not see why?
- tdb7893 8mo ago
  Are you talking about that people could just click on the link then not actually read it? The thing is that clicking on the link then closing is serves as both a slight barrier to entry targeted at the people who comment without reading and also a reminder that there is an actual article to comment on. It's not going to fix discourse but the theory behind it is to be a slight nudge to get people who don't click to at least consider reading the article (or just not comment) while being an invisible change to people who actually read the article. It's not meant to be a magic fix, it's just some something I would want (though I'm biased since I click on links so there's no downside to me).
  - ShroudedNight 8mo ago
    Wouldn't browser prefetching subvert these small frictions to entry?
    - tdb7893 8mo ago
      I think I've seen sites trying to track outbound clicks recently, has prefetching made that impossible? I don't know the implementation but I've seen the browser sending requests that track clicks while investigating other stuff (idk whether it's working accurately though). Edit: to be clear, it's not like I've researched this proposal since I don't work for social media companies. It's just a feature I wish I could have on my posts.

deathanatos 8mo ago

Which is what makes the headline bait. We start with "The largest number representable in 64 bits" (which obviously depends on the representation, and as the baited comments point out, if that's freely settable, we can just set it arbitrarily high). But the body then moves the goalposts to "using a Turning machine", "using a Turing machine with specific parameters fixed", to "lambda calculus", etc. This is now (at least) "The largest number representable by a Turning machine of fixed parameters that can then be squeezed into 64 bit." (I don't remember my lambda calc, so … eh.)

deleted 8mo ago

[deleted]

omoikane 8mo ago

A better title might have been "fastest growing function with 64bit arguments". The main value of this article is really the various functions that take larger strides to cover a finite range that's significantly larger than 2^64-1.

tromp 8mo ago
If it were about coding fast growing functions, then it would have had to mention the incredible 47-bit lambda calculus term λn. n n (λe λx. x e x) (λm. m (λe. m e m)) that achieves f_ε₀ growth. But it expects its argument to be a so-called state numeral n, rather than a Church numeral, and even state numeral 2, which is \e\f\x.f e (\e.f e x) is already 32 bits long, making the application take 2+47+32=81 bits, more than the required 64.

LanceH 8mo ago

I found the problem itself to be poorly defined. > What if we allow representations beyond plain data types? Since we want representations to remain computable, the most general kind of representation would be a program in some programming language. But the program must be small enough to fit in 64 bits. If you bring in a whole programming language, you bring in a lot more than 64 bits. This all seems to be the math equivalent of saying you wrote a program in 2k when the first line is "import 'megalibrary'".