Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Galactic Algorithm

en.wikipedia.org

Post reply on HN
Print view View original

51–60 of 74 posts

Re: Galactic Algorithm

#51

Post by asdaddasdad »

lonelappde wrote: post #49
asdaddasdad wrote: post #27

I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.

It's not states, it's logarithmic of states (# of dimensions of finite size) . Think about writing down a number. One atom per digit is a pretty natural heuristic for the optimal spatial cost of information. Yes you can get clever, but there's no point, were already at astronomical levels of imprecision.

As I said, one atom per digit is not really natural. Just two atoms could encode an infinite number of numbers, by measuring their distance. Well except quantum physics might get in the way, not allowing us to measure with arbitrary precision. But that would be another argument.

Another argument would perhaps be the energy required to do the computation. Maybe that relates more directly to the number of atoms in the universe, via Einstein's equation?

Re: Galactic Algorithm

#52

Post by marcosdumay »

function_seven wrote: post #18
saagarjha wrote: post #13

Earlier quoted context omitted.

You could say so: > As with these, it is so large that the observable universe is far too small to contain an ordinary digital representation of Graham's number, assuming that each digit occupies one Planck volume, possibly the smallest measurable space. But even the number of digits in this digital representation of Graham's number would itself be a number so large that its digital representation cannot be represent…

> for a number of times far exceeding the total number of Planck volumes in the observable universe. Just so I'm clear. They're saying that not only can I not fit Graham's Number in all the Planck volumes of the universe; and I can't even count the digits of GN and write that in the Planck volume of the universe (and so on), but the number of "indirections" is itself so large as to not fit in the universe? Like: 1. G…

It shouldn't be surprising, because the Graham's Number is all about applying those indirections recursively into more indirections.

Re: Galactic Algorithm

#53

Post by asdaddasdad »

marcosdumay wrote: post #50
comboy wrote: post #33

Earlier quoted context omitted.

It's just there for a reference, maybe a better one would be Kurzweil's ultimate laptop (made from the whole universe). But the interesting part is that I don't think the ultimate laptop takes into account interactions and state between atoms. AFAIR it assumes computation is done on every available dimension (like electron spin) but not on how atoms move and interact with each other. Intuitively it shouldn't make muc…

The number of digits of the possible interactions between the atoms is still proportional to the number of atoms.

What counts as an interaction? It seems to me there can be an infinite number of interactions between just two atoms.

Re: Galactic Algorithm

#54

Post by MaxBarraclough »

carlmr wrote: post #31
gmoot wrote: post #7

Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time: "It's very complex. I don't think anyone has actually implemented it". It shocked me at the time that there were algorithms like this. https://en.wikipedia.org/wiki/Polygon_triangulation#Computat...

They mention O(n log* n) being quasi linear time, I had to look up log * n because I never saw this before.

Wikipedia link: https://en.wikipedia.org/wiki/Log-star

Re: Galactic Algorithm

#55

Post by platz »

asdaddasdad wrote: post #53
marcosdumay wrote: post #50

Earlier quoted context omitted.

The number of digits of the possible interactions between the atoms is still proportional to the number of atoms.

What counts as an interaction? It seems to me there can be an infinite number of interactions between just two atoms.

Number of states of the universe is a quantum value, not a classical one.

Re: Galactic Algorithm

#57

Post by IshKebab »

gmoot wrote: post #7

Ah. I still remember my computational geometry professor telling us about an algorithm to do triangulation (composing a polygon into triangles) in linear time: "It's very complex. I don't think anyone has actually implemented it". It shocked me at the time that there were algorithms like this. https://en.wikipedia.org/wiki/Polygon_triangulation#Computat...

Yeah I discovered a fast algorithm for the travelling salesman problem with neighbourhoods (i.e. cities are shapes not points). Emailed the author to inquire about code, turns out they never wrote any.

Re: Galactic Algorithm

#58

Post by marzell »

asdaddasdad wrote: post #27

I've never understood the "number of the atoms in the universe" argument. The number of states the universe can be in doesn't seem to be equal to the number of atoms. For example, just two atoms could encode lots of numbers simply by using their distance. Quantum physics would affect it, but I mean in principle: we are not switching atoms on and off to encode state.

How would you read that? (Distance between two distinct atoms) doesn't seem practical

Re: Galactic Algorithm

#59

Post by angel_j »

If all that is required is a super large constant (as in some cases), why not assume the large constant, do the calculation, then factor out the large constant?

Re: Galactic Algorithm

#60

Post by saalweachter »

Gunax wrote: post #28
function_seven wrote: post #18

Earlier quoted context omitted.

> for a number of times far exceeding the total number of Planck volumes in the observable universe. Just so I'm clear. They're saying that not only can I not fit Graham's Number in all the Planck volumes of the universe; and I can't even count the digits of GN and write that in the Planck volume of the universe (and so on), but the number of "indirections" is itself so large as to not fit in the universe? Like: 1. G…

Yes. log(log(log... GN))) applied X times (where X is the number of planck volumes in the universe) is still greater than X. Where log = base 10 logarithm. Hofstadter talks a bit about this abstraction in his article 'On Number Numbness' > If, perchance, you were to start dealing with numbers having millions or billions of digits, the numerals themselves (the colossal strings of digits) would cease to be visualizable…

And despite that, Graham's Number is still in the countable set. :-)
Post reply on HN