I like how Ken Jennings dealt with the 'Go complexity' analogy:
"Go is famously a more complex game than chess, with its larger board, longer games, and many more pieces. Google’s DeepMind artificial intelligence team likes to say that there are more possible Go boards than atoms in the known universe, but that vastly understates the computational problem. There are about 10^170 board positions in Go, and only 10^80 atoms in the universe. That means that if there were as many parallel universes as there are atoms in our universe (!), then the total number of atoms in all those universes combined would be close to the possibilities on a single Go board."
I don't think anyone believes that Go is somehow more complex than the universe it is a subset of. The point is that enumerating all cases of Go is impossible and always will be, so more sophisticated analysis is required.
Sametmax's point is that you're comparing a simple count (atoms) to a factorial (combinations of pieces). For example, it's hardly surprising that 6! is larger than 6 - factorials grow much faster than simple counts.
Compared with a googol our Universe has negligible atoms , 10^100 - 10^80 = ~10^100
Compared with a googolplex (10^(10^100)) the entire Evrettian metaverse is negligible as (10^(10^100) - 10^80^2 * (average quarks in atom) * leptons(10^200) * dark multiplier(10^2) = ~1 googolplex
Graham's number - one googolplex raised to the googolplexed power =~ Graham's number, which has been used in a proof. There have been larger numbers used in proofs but none yet as famous as Graham's number, about which Martin Gardner wrote a popular mathematics article. http://iteror.org/big/Source/Graham-Gardner/GrahamsNumber.ht...
Rayo's number is so big it is almost impossible to convey how big it is. It is certainly much much much bigger than Graham's number. (Unlike Graham's number, it appears not to serve any useful purpose beyond winning "who can name the biggest number?" games.)
That is a staggering amount of possible Go games, no wonder tree search failed to improve without the Convnet pruning.
Makes me wonder if Deepmind could learn Go without first learning from the big dataset of expert games to train the convnet to prune the tree.
Which implies that Deepmind couldn't learn to play Go without first being taught by us (the expert games).
So AlphaGo learnt Go from us. It took a human brain to crack the problem of Go and the AI learned from our solutions it did not discover them itself - still a very great breakthrough.
Would Lee Sedol have won if he could use MCTS to assist his evaluation ?
( Arguably the MCTS is a non-AI component of deepmind & does not learn ).
MCTS = Monte Carlo Tree Search, where repeated random playouts evaluate moves by randomly sampling the tree of following (googolplex) possible moves.
Don't conflate the "Observable Universe" with the actual Universe. We flat out don't know how big the actual Universe is. So, it could be 10^80, 10^800, or even A(10, 80)* Atoms.
If that is the case was the universe once finite and then went infinite during the early (big bang) expansion? I don't understand how something could have expanded if it was always infinite in size. I'm not even sure the concept of expansion even makes sense. What is infinite + 1? It's just infinite. It seems more like the expansion is a distribution of internal things.
You can see back as far as the Big Bang, approximately 14 billion years ago, so all matter in the visible Universe is within 14 billion light years of the Earth. However, the space the Universe occupies is only really finite if it's positively curved. If it's flat or negatively curved, the space it occupies is infinite, and if its density is constant, it must contain an infinite amount of matter even though we only see part of it. The Big Bang is a singularity - a point with infinite density. It's hard to get your head around intuitively, but it all makes sense mathematically. (The maths is pretty hard, and rarely covered at undergraduate level.)
Off the cuff thought: the overall universe is infinite and not expanding, and it's only the visible universe that's expanding into that infinite space.
Now try to wrap your mind around this: someone that's one light year to the left is going to see a slightly different visible universe, also expanding, into the same infinite space. But if we look in their direction, we see the edge of our visible universe expanding into the void, but from their point of view looking in the same direction our edge is one light year short of their edge. So what's our edge expanding into?
I've always wondered; is there a "last" galaxy in any direction, such that for an observer in that galaxy, no further light or radiation can be detected from that direction? (outside that galaxy)
Math includes the idea of orders of infinity. There are infinite prime numbers, there are more positive integers, even more integers (positive and negative), even more rational numbers (A/B), and even more numbers (rational + irrational {e, Pi} etc)...
In what sense are there more rational numbers than prime numbers? They can be put into bijection with each other, so we generally think of them as being same infinity. There are more real nubmers, of course, by Cantor's diagonalization, so your basic point is true.
Within a segment of numbers I understand how there are more rational numbers than integers, but I don't understand it in the context of infinity. How can there be more rational numbers than integers when in both cases there are infinite amounts? Are there mathematical operations or concepts that depend on this (in the context of infinity, not subsets)?
I don't know the answer to your question, but I can imagine how something can expand if it's infinite. Imagine an infinitelylong rubber band in front of you. Now imagine grabbing it with two hands and pulling them away from each other, causing the rubber band to stretch. If you take a sharpie, and paint dots on a spot representing planets or whatever else, they will pull away from eachother as you stretch the rubber band.
Take the set of positive integers (0, 1, 2…). Double them, so you have (0, 2, 4…). You had an infinite list of numbers, all "compact" (no room for more positive integers inbetween them), and with a simple mathematical transform, you've given yourself space for a second equally-sized infinity of integers to fit neatly inside of them.
While this comparison highlights that yes, there are very many possible Go games, it's really apples to oranges.
The real comparison would be the number of pieces on a Go board (19x19 = 361) compared to the number of atoms in the universe. And then to compare the number of possible board positions in Go, with the number of possible atom positions in the universe, and in this case I think the universe wins.....
Go is very complex, and the fact that DeepMind could tackle this complexity is a huge technical achievement. No minimax-based AI could have tackled such a large state space.
However, other problems have even larger state spaces. Imagine writing an AI which read project Euler problem descriptions (in English) and output working code (in some given programming language). Keep outputs limited to 100-line scripts, max 80 characters per line.
There's roughly 100 usable characters in ASCII, so the possible space of 100-line programs is roughly:
(10^2)^(80 * 100) = 10^16000.
You could simplify this by having the AI work with predefined tokens rather than individual characters, but it's still a vast amount of combinations. Then consider 1000-line or 10000-line programs, and you see how high a mountain AI still has to climb. Humans are able to "compress" this state space via conceptual reasoning, which is much more complex than the "pattern recognition" many deep learning researchers are chasing.
(See "Introduction to Objectivist Epistemology" for more on how humans think in concepts - I'm planning to write more at some point on how this book shows where the practical limits of AI lie).
The ratio is 10^90 which is not small. The subtractive difference rounds to 10^170. In either case, I think its fair to say that 10^170 is unimaginably larger than 10^80.
But if differences become so large we cannot imagine the differences, then we could imagine there are no differences at all, so ... psychologically/subjectively there would be no difference?
I think that the context matters. While his actual statement is now false, he was really talking about a "solution" to Go, i.e. an algorithm that can compete with any opponent (and back then, Go programs couldn't "even" beat humans). Google's algorithm is (probably) nowhere near a "solution" to Go, but an algorithm that can beat currently-living human opponents. I.e. it is quite likely that a rather simple algorithm would still beat Google's program, only that people's minds don't (or can't) employ that algorithm when they play.
Actually the Earth is nearly perfect, far more perfect than most any sphere with interact with in day to day life. The equatorial bulge is 20 miles or so, which is approximately .33% Technically an oblate spheroid, but barely.
And for comparison, the variation in surface height relative to sealevel is over 10 miles (6 miles down to the bottom of deep ocean trenches; 5 miles up to the top of mountains)
That actually makes the Earth seem small to me. I wouldn't have blinked if someone had told me the blueberries would fill up a sphere the size of the Solar System. Just shows how hard it is to visualize these numbers.
The earth is small. If you build a scale model of the solar system the size of a football field, with the sun and one end and Neptune at the other (Pluto has been laid off as a planet) then the sun will be about the size of a ping pong ball and the earth will be the size of a poppy seed (and it will be about ten feet from the sun). Jupiter is about the size of a pea at this scale. Alpha Centauri is about four miles away.
And not only do you live on a poppy seed, you live on a very thin layer on the surface of this poppy seed. Blow the poppy seed up to the size of a basketball and the habitable layer is about the thickness of a sheet of paper.
"The Integral Trees" by Larry Niven is a novel in which people live in a free-floating cloud of atmospheric gas that is gravitationally stable in a multi-star system. They live on enormous trees with canopies on each end, which are blown in opposite directions by the winds (so they look like the integral sign).
That really depends on your quality metric. If you care about computational speed (because there's only a finite amount of time before the heat death of the universe) then the speed of light starts to be a limiting factor, and concentrating all the computation in a small space makes sense.
To the goal of sustaining intelligent life. I'm being semi-facetious of course, but scifi authors and futurists have discussed dismantling the planets to build more mass-efficient structures for a long time.
I'm curious how the author found the link to this - I looked at Norvig's home page but could not find it, which made me wonder how many more goodies he's got up there that we don't know about!
Yes, sureley. In Computablilty Theory you have the famous Ackermann-function[1]. It is actually an operator-extension, like you just described. It is important, because it grows overexponentially, but is still computable (unlike e.g. the busy-beaver-function).
Given that Graham's Number is an (over-)extension of the Ackermann-function that means that it's still computable, correct?
Given the series leading up to Graham's Number, G = g_64 (g_1, g_2, ...), BB(n) will outgrow g_n, right? If so what's the smallest n such that BB(n) > g_n?
Graham's number comes from such an extension, and is about 64 such operations deeper. It's useful in the sense that it provides an upper bound for some proof that hasn't yet been proven for ALL numbers.
If 12megapixels can produce 10 to the power 86696638 images, and we came up with a way of enumerating those images, could we then build a function that given anyone of those images return the index of that image within reasonable time with current hardware. ie. "you have just taken 3999999987493th image"?
A friend of mine made a tool that did exactly this, but with Haikus instead. He had a dictionary of syllables, and then just iterated through the syllables (following the rules of a haiku). You can type in a haiku and find its index, or just iterate through the indices to see the (mostly nonsense) generated haikus.
Yes, but it wouldn't save any space. As a thought experiment, think of it this way:
How would we enumerate all these several gazillion image possibilities?
Well. Let's say number one is all black. Every pixels and every channel is all zero in its value. And let's say the last image to be enumerated is all white. 255 for each pixel and each channel.
Every conceivable image is created in between these two ends. For example, image two is all black, but the last pixel has a value of 1 instead of 0 for its value channel.
Image 1840274917 has pixel 27581 slightly reddish.
Hey, wait a minute, you've just created an image format for describing the data within the image! The only space you're saving is that (given this format) you save space on darker images, because they're likely lower in the sequence.
But that's only because this specification demands that each image be the same exact size and can make assumptions based on that. A lossless format like PNG would be able to perform much better over a wider range of images. (Eg all white will be huge in our system, but cheap in PNG)
not only could you enumerate all images, you can also enumerate all books. the library of babel does this and youre looking at the particular page where this exact paragraph is written, for hacker news by dackerman, no less.
The electron goes forward and backward in time and interacts with itself. (In quantum field theory you can replace a positron with an electron going backwards in time). Regrettably the theory does not work, since it would predict the same number of electrons and positrons in the universe.
Feynman later proposed this interpretation of the positron as an electron moving backward in time in his 1949 paper "The Theory of Positrons".[2] Yoichiro Nambu later applied it to all production and annihilation of particle-antiparticle pairs, stating that "the eventual creation and annihilation of pairs that may occur now and then is no creation or annihilation, but only a change of direction of moving particles, from past to future, or from future to past."[3]
Physics is sufficiently weird that I can't tell if this is just spitballing or an actual theory I haven't heard of before.
Edit: holy crap, these people think nucleons are made of muons that are made of electrons and positrons: http://wlsprojects.com/structure-inside-proton.html . Solves the matter vs antimatter problem, I guess.
It would be cool if there were more talk about properties we have observed of these configurations/which are more probable at any given instance, and efficient ways of computing such.
Reading this made me think how can you know the number of atoms in the universe (observable, smellable, touchable, whatever ). So I go and check on Wikipedia and of course its just a guesstimation based on assumptions and hypothesuses.
This again reminds me how science today is no different than religion. Of course there is nothing wrong with having the number based on assumptions , but take it out of the field of study and suddenly it is a fact :)
Like in this article and the discussion in HN where its just the number and its name, and the fact that this him be is just somebody's wild guess is totally ignored. Same with Jesus , he exists and he loves you and the fact that it was just somebody's idea is totally left out.
Assuming space is quantized at the Planck scale, the numbers of atoms in the universe is tiny compared to the number of space points.
Assuming the many worlds interpretation of quantum physics is true, then the number of atoms includes all combinations of locations, momentum, etc., and the real number of atoms is vastly vastly greater than combinations of just about anything else you might imagine. (Except for combinations of configurations of quantized spacial points!)
I'd argue the natural scale for thinking about the number of combinations is the log scale - in other words, the entropy. Entropy, like the number of atoms, is an additive property of a system.
From this point of view this article is inappropriately comparing two scales. It's nothing more than saying "e^x >> x for big x".
It is an axiom, it is not something that you believe in. You assume it and you prove stuff with it. You do not and you prove stuff without it. If you are really good, you show what theorems require it.
You can believe or not in some physical reality to math (I happen to), and then the axioms do become somewhat more than just logic statements, but that is different.
> You can believe or not in some physical reality to math (I happen to)
I'm not so sure. Is there any evidence that the value of any physical quantity is an irrational number?
Math was originally inspired by physical reality, but I'm not sure it's so closely related that the concept of the Axiom of Choice being "true" even means anything.
Well, I think the example with 12-pixel image is a bit misleading, because the picture focuses reader's attention on those 12 pixels, while skipping over the fact that each pixel can have ~17 million colors. More appropriate representation would be a cuboid made of 3x4x24 blocks.
"Go is famously a more complex game than chess, with its larger board, longer games, and many more pieces. Google’s DeepMind artificial intelligence team likes to say that there are more possible Go boards than atoms in the known universe, but that vastly understates the computational problem. There are about 10^170 board positions in Go, and only 10^80 atoms in the universe. That means that if there were as many parallel universes as there are atoms in our universe (!), then the total number of atoms in all those universes combined would be close to the possibilities on a single Go board."
http://www.slate.com/articles/technology/technology/2016/03/...