1. 14
norvig.com
1.

2. 3

For info the number of legal position were computed exactly it is 208 168 199 381 979 984 699 478 633 344 862 770 286 522 453 884 530 548 425 639 456 820 927 419 612 738 015 378 525 648 451 698 519 643 907 259 916 015 628 128 546 089 888 314 427 129 715 319 317 557 736 620 397 247 064 840 935 (I took it from https://en.wikipedia.org/wiki/Go_and_mathematics)

1. 1

This really gave me a new perspective on unique combinations of things and large numbers.

1. 1

When I first encountered set theory, it confused me that people would use sets of all things (as opposed to the more traditional choice of numbers) as the foundations of mathematics. I think it makes sense in terms of the fact that sets can be just very, very big. For example, P(X), the set of all subsets of X, is always a much bigger set– even when X is infinite (that’s where uncountable infinities come from.

Even when restricting oneself to finiteness, there’s a lot of fast growth or bigness. For example, the Von Neumann universe:

`Union(V_n) where V_-1 = {} and V_k = P(V_(k-1))`

So `V_-1` is empty and `V_0` just has one element (`{}`) and `V_1` only has two, but `V_6` has 2^65536 elements (more than there are atoms in the universe) and `V_7` is probably bigger than the number of discernible states of the universe. And yet that’s only the smallest contingent of the Von Neumann universe (which embeds all of standard mathematics). `V_7` doesn’t even include the canonical representation of the number 8 (defined as S^8({}) where S(x) = x ∪ {x}.

The Von Neumann set sizes (1, 2, 4, 16, 65536, 2^65536, 2^(2^65536), …) grow fast, but that’s not even the limit of fast growth. That’s “tetration” (faster than any exponential) but there are faster-growing functions like the Busy Beaver function, which grows faster than any computable function. BB(n) is the (analogous to) the maximum amount of work that an n-state, halting, 2-symbol Turing machine can do, and while BB(4) is 13, BB(5) is believed to be 4098, BB(6) is over 10^1000.

Anyway, it’s cool stuff.

1. 1

Ha - “So saying that there are more Go positions than the number of atoms in the universe is a bigger understatement than saying the national debt is more than a penny.”