On the (Small) Number of Atoms in the Universe(norvig.com) |
On the (Small) Number of Atoms in the Universe(norvig.com) |
"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/...
In Go, the number of items is the number of pieces, and it's very small.
In the universe, the number of combinations of positions of all the atoms is, well, wonderful.
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
Has anyone ever used a googolplex for anything ?
[For ~ read approximately]
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.....
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).
Close?? Wouldn't it still be roughly 10 billion times smaller...?
> And in Go even an amateur human can still rout the world’s top-ranked computer programs
However, I think I found a mistake:
"For example, ‘5 tetrated to the 3’ means 5 raised to its own power 3 times, or 5^5^5"
(I am paraphrasing slightly here because the essay uses an image to show 5^5^5 in normal notation (http://www.scottaaronson.com/cgi-bin/mimetex.cgi?5^{5^5}))
However, shouldn't this be 5^5^5^5, if we're raising 5 to its own power three times?
5 x 3 = 5 + 5 + 5
5 ^ 3 = 5 x 5 x 5
5 t 3 = 5 ^ 5 ^ 5
Where t is tetration. Each one counts 3 fives.
"..the number of atoms in a grapefruit is about equal to the number of blueberries you would need to fill up the entire sphere of planet Earth." [https://capitolhillscience8.wordpress.com/2012/10/03/just-ho...]
Edit: well, except that the Earth is shaped more like an oblate spheroid [https://en.wikipedia.org/wiki/Figure_of_the_Earth]
There's a few interesting things on there!
+ applied N times becomes ×N
× applied N times becomes ^N
^ applied N times becomes ...?
etcetera
And would such a theory have any practical use?
As for practicalities, the mathematician in me will let the scientists deal with that.
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).
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)
The 'Everything' Formula - http://youtu.be/_s5RFgd59ao
Disclaimer: I am not a physicist, but I love this theory
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.
This is a fun, thought-provoking story about a large combination of things.
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!)
From this point of view this article is inappropriately comparing two scales. It's nothing more than saying "e^x >> x for big x".
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.
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.
Interesting POV.
59! =~ 1.38 × 10^80
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.
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?
[0]: "A Lower Bound on Rado's Sigma Function for Binary Turing Machines" by Milton Green (1964)
[1]: https://en.wikipedia.org/wiki/Busy_beaver#Known_values_for_....
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?
208168199381979984699478633344862770286522453884530548425 639456820927419612738015378525648451698519643907259916015 628128546089888314427129715319317557736620397247064840935
positions in Go is impossible.
http://tromp.github.io/go/legal.html
for the method used, which is a form of dynamic programming.
2/ Each digit represents an intersection on the goban, assuming the following mapping: 0 = no stone, 1 = black stone, 2 = white stone.
Does that count:-?
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.
This sounds like SciFi material.
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.
The count above is for legal positions only, i.e. those where every connected group of stones is adjacent to an empty point.
Actually, around 500 miles.
Distance to Alpha Centauri: 4.37 light years = 276,364 astronomical units.
In your diagram, the Earth is 10 feet from the Sun. Multiply by 276,364 to get 2,763,640 feet, or 523 miles.
The scale jump from distances around the Solar System to the next closest star is mind boggling.
The simplest model in rough agreement with observations is called the Einstein-de Sitter Model, and it's flat with a zero cosmological constant. See http://www.britannica.com/science/cosmology-astronomy/Relati...
More general models are covered here: https://en.wikipedia.org/wiki/Friedmann%E2%80%93Lema%C3%AEtr...
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?
That, must be a terrifying place to live in......
http://www.scientificamerican.com/article/are-we-living-in-a...
Walraet paper has 10^10^103, so 1000 googolplexes - this is very large.
Monte Carlo methods are specifically for guess-timating intractably big searches.
MCTS is close to the human heuristic for evaluating Go positions - counting who currently controls what, multiplied by the strength of each position (in Go 2 'eyes' make a block impervious to harm). Early on this is very subtle to discern - which makes Go a subtle art.
The human heuristic is complex, the MCTS random playout is overly simple but uses gigaflops of random sampling. MCTS was the basis of the best computer (the new innovation is the convnets that prunes the tree before MCTS).
The convnets are trained on a big database of expert games which is why I wonder if the MCTS is the differenting factor & Lee Sedol with an MCTS would beat the Convnet & MCTS.
This is important because: does AlphaGo plan ?
If not, the implication is planning is a poorer heuristic compared with whatever AlphaGo actually does.
The convnet provably doesn't plan, it estimates what a human expert would do and performs tne same whether playing game or just predicting next move from random configurations.
AI research has always held planning in high regard.
If you think of dynamic programming as counting the number of paths in a directed graph (in this case, from skimming the paper, the nodes correspond to border states), then given a path number, you can trace the path backwards through the graph, as long as you remember the number of paths ending in every vertex.
Did you mean reals here? There _is_ a (bijection) mapping between integers and rationals.
https://en.wikipedia.org/wiki/Cantor_pairing_function#Cantor...
But most people would disagree with you when you say "how can there be more rational numbers than integers..." because while we don't have a firm grasp of how many, we definitely would say that having the same cardinality means that there isn't some notion of "more".
I'm not sure what you mean by mathematical operations or concepts that depend on this.
> I'm not sure what you mean by mathematical operations or concepts that depend on this.
I suppose I meant to ask if there was any practical application of the concepts you described.
Cantor's diagonalization is simply demonstrating that same inequality by showing a number in set A is not in set B.
Just because you can map two infinity's to each other does not mean they are of the same size consider: Limit(0->inifinity) of (x - (x/2)) algebraically that's clearly Limit(0->inifinity) of X/2 which is infinity.
PS: What makes Cantor's diagonalization interesting is you can repeat it recursively an infinite number of times. This is more obvious in base 2.
The reals, on the other hand, cannot be placed in a bijection with the natural numbers, and there are therefore "more" reals than naturals (i.e. there is an injection from the naturals to the reals, but not from the reals to the naturals -- any function from reals to naturals must have some pair x ≠ y with f(x) = f(y)).
Is the set of Real Numbers larger, smaller, or the same size as the set of points in a finite 2d object? Can you setup a bijection in either direction?
If that were true, why go to all the trouble, just show 1/2 which is not a natural number, or sqrt(2) which is not a rational number.
Cantor's diagonalization is proving that no mapping exists between the natural numbers and the real numbers in [0, 1]; that no matter what mapping you (try to) come up, there will be a number you would miss.
The primes and rationals have the same size (cardinality) as the natural numbers, namely countably infinite. See https://en.wikipedia.org/wiki/Countable_set#Formal_overview_...
There are an infant number of points between 0 and 1 and an infinite number of points between 0 and 2. The distance between 0 and 2 is larger. The number of points between 0 and 1 is smaller than the number of points on the unit circle AND they are a different class of infinity.
Diagonalization isn't showing that a number in set A isn't in set B - that's obviously true for reals and integers, but it's also true for rationals and integers. It's showing that there does not exist a mapping from B to A where there's an element in B for each element in A.
We're obviously not using the same definition of "size". I generally think in terms of cardinality, what are you thinking of?
If every element in set A is in set B, and there are elements in set A left over it's larger because that's what larger means. {A,B} < {A,B,C}
There are countable and uncountable infinite set's. All countable set's have a bijection with N. However, there are more than two sizes of infinite sets. Real numbers < Imaginary numbers.
The answer is no, as illustrated by the Hotel paradox[0], in which we have a infinitely many rooms and want to accommodate a (possibly infinite) number of guests.. To summarize: For any finite number of guests, you can always find an even-numbered room to correspond to that guest (assume the guests are numbered sequentially, then double their number and put them in the room that has that number.). This creates a one-to-one correspondence, which means that the sets are the same size.
You might say, 'well, that only works because we're dealing with a finite number of guests. But we're talking about infinity'. There are a few different ways of answering that question. In my opinion, the easiest way to look at it is to remember that there is no such number as 'infinity' - when we say 'infinity', we're really trying to express the concept of growing without bound. So, the above strategy (double the person's number) works for any arbitrarily large group. At no point does it stop working, even as the group size grows larger and larger, so we can say that the two sets have the same size.
On the other hand, we have no such strategy for putting every irrational number in one-to-one correspondence with the counting numbers. That proof is a little harder, and the analogy with the hotel guests breaks down, unfortunately, so it's a bit tougher to explain.
[0] https://en.wikipedia.org/wiki/Hilbert's_paradox_of_the_Grand...
In short, infinities are complicated and intuition doesn't work well.
In slightly longer, you're talking about the difference of the rate of growth of two functions rather than actually about the cardinalities of the sets.
We define two sets as having the same cardinality when we can create a bijection between them. We can list the primes in order from smallest to largest and number them with the natural numbers. So we'll have 2 match up with 0, 3 with 1, 5 with 2, 7 with 3, etc. Every single prime number will correspond with a natural number AND every single natural number will correspond with a prime number, no exceptions. So they must be the same size. They are also the same size as the integers and the rational numbers but the set of real numbers is a bigger infinity.
What about looking "up" and "down?" i.e. into the inside of balloon or away from its surface?
I have a hard time wrapping my head around the balloon surface analogy, because galaxies seem to be in all directions of each other..
Or, alternatively, if you think of time as a dimension, then we can call "up" the future and "down" the past. In that case, if you look down inside the past, you'll see that in that analogy the center of the universe corresponds with the big bang! And all the galaxies are equidistant from that point/moment in spacetime.
That's why gravitational waves are such a big deal: they allow us to look further. (Not further than the limit imposed by the speed of light, though.)
- normalise x and y coordinates in the shape into the interval (0, 1)
- interleave the bits of the normalised x and y coordinates
This gives you a bijection between points in (a) 2-dimensional space and a segment of the real line (which, in turn, has a bijection with the whole real line if you want to specify that).
Once again, cardinality in set theory is based on injections and bijections. If there is an injection from X into Y, then Y is at least as big as X. If there is a bijection between them (i.e. injections in both directions), then they are the same size.
(Also, bijections are inherently bidirectional.)
Try to make arguments from axioms and definitions rather than asserting things from intuition. Intuition is often a useful tool, but (1) it's not an argument, and (2) it's not very helpful once you step into the infinite realm. Incidentally, that's why I went for programming: it's like math, but with no infinity (unless you're using floats, but that's a much easier infinity).
There are more than two sizes of infinite sets, but there are just as many real numbers as imaginary numbers for the same reason there's just as many integers as rational numbers.
Try reading this: https://en.wikipedia.org/wiki/Cardinality#Infinite_sets
Now, feel free to try and map the set of Real numbers to the set of irrational numbers. ex: e + ei.
For a your mapping, see: http://math.stackexchange.com/questions/512397/is-there-a-si...
2. f(x) = x + sqrt(2) if there exists an integer k>=0 such that x - k * sqrt(2) is rational; f(x) = x otherwise.
This function maps all real numbers to irrational numbers, 1-to-1.
But please, continue to argue with mathematical definitions that have been established for over a century.
[1]: https://en.wikipedia.org/wiki/Aleph_number#Aleph-naught
This is correct. However, the number of real-valued points between 0 and 1 is the same as the number of real-valued points between 0 and 2.
> The number of points between 0 and 1 is larger than the number of rational numbers.
This is also true because there are uncountably many real-valued points between 0 and 1 and countably many rational numbers.
So, after you define x+1 and x+i, now what? Also please bear in mind that "infinity" is neither real nor complex: if you have a well-defined mapping into complex numbers, then by definition, it never maps to infinity.
(Yes, there are some "functions" like y = 1/x that "maps to infinity", but it's simply mathematicians being lazy and abusing notations because everybody around them understands what's going on.)
There is a basic contradiction in set theory. Called Russell's paradox, there are two ways around it. First is ignoring it, aka everything builds from it's self nothing can become recursive. Or Zer's something or other that basically removed membership and equality and hides in the corner crying.
As such infinity is generally assumed not to exit in R. And causes all this all infinite set's map able to each other are equivalent size crap. It's also why real mathematicians laugh at the set guys.
But, sorry the way R was initially defined it included infinity and you only get to put it into 1 place on your mapping. Or as a math professor said, what angle is the highest number in R mapping to.
If you are interested, please read an actual math textbook. (Yes, they can be a giant time sink, but at least you'll learn the correct meanings of sets and functions.)
But, the absurd results are not generalizable outside of their assumptions sorry Axioms. Set theory being one of the most obvious cases.
It's sadly like a religion in many ways, follow enough false statements and you can prove anything. Yet, if you find a contradiction then don't actually accept at least one of your assumptions are false.