4 ms·

This reminds me of an essay I really like (it covers what the busy beaver numbers are, and what their utility is): http://www.scottaaronson.com/writings/bignumb

This reminds me of an essay I really like (it covers what the busy beaver numbers are, and what their utility is): http://www.scottaaronson.com/writings/bignumbers.html http://www.scottaaronson.com/writings/bignumbers.html

Torn 17y ago
Outstanding introduction to this sort of thing, thanks for sharing.
dangoldin 17y ago
You should submit this on it's own to HN. That was a great read.
pbhjpbhj 17y ago
But do people fear big numbers? Certainly they do. Apathy !== fear. comforting smallness of mysticism? In what way is mysticism small? It is bigger by most definitions than anything we're capable of being consciously aware of. On topic, excellent; but the off-the-cuff remarks could have used a little more thought IMO.
- Eliezer 17y ago
  > In what way is mysticism small? It is bigger by most definitions Saying "infinite" creates a vague sensation of bigness that isn't anywhere near as big as, say, 3^^^3 (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) to say nothing of really large numbers. The idea of the night sky as "infinite" is nowhere near as shocking as the idea of galaxies a septillion meters away. It's like the difference between Thor, versus the machine superintelligences of Iain Banks's Culture or the Powers from Vernor Vinge's A Fire Upon the Deep. You can imagine the "infinite" Jehovah demanding the worship of Israelite tribespeople, but it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so. If you think of mystics as primitive amateur philosophers and science fiction writers who demand that their work be protected from ordinary criticism, you can see there's no way they'd be able to keep up with modern science fiction writers or modern mathematicians. In this light, words like "infinite" or "unimaginable" are just words - showing instead of telling, mere adjectives, a demand that we be impressed which isn't backed up by any actual ability to conceive of impressive things.
  - pbhjpbhj 17y ago
    it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so How about a more Leibnizian idea of the Creator having designed into the primordial energy event all of the consequences of existence - some slight fluctuation or variation being ultimately responsible for this internet post ... is that a valid activity for your concept of a mystical supermind. Or consider that the realist approach to many worlds is true - is the awareness of every subatomic interaction in every one of an infinite array of possible worlds, is that enough processing for you? How about if that mystical being is responsible for an infinite number of such worlds? You have a very large concept of the infinite aleph-0^^^...^^aleph-0 (I doubt you can verily comprehend those numbers though) or whatever but some numerological mystics would say those concepts are discovered from ideas embedded in the created order or inherited from a prime movers creative mind. Your view of mysticism is narrow.
    - pwmanagerdied 17y ago
      Your view of mysticism is wrong.
      - pbhjpbhj 17y ago
        In what way?
amalcon 17y ago
Yeah, that's a good one. The only complaint I have is that it contends that the Busy Beaver numbers grow faster than any computable sequence, but what it actually shows is that no computable sequence can be proven to grow faster than the Busy Beaver numbers. If a sequence happens to grow faster than the Busy Beaver sequence, but we can't prove it, then it doesn't help us prove anything about Turing machines.
- camccann 17y ago
  Consider a Turing machine M1 of size X that, given an input value n, calculates a function f(n) such that O(f(n)) > O(BB(n)) and halts. Consider a Turing machine M2 of size Y that calculates a number A and halts, where X + Y < A. Combine the two machines, using the number calculated by M2 as the input for M1. The resulting Turing machine of size X + Y calculates a value f(A) such that f(A) > BB(A) > BB(X + Y) and then halts. This contradicts the definition of BB(X + Y), therefore no such computable function f can exist.
  - amalcon 17y ago
    Alright, this is a good proof. I therefore concede the point regarding the values themselves.
    - camccann 17y ago
      It's more of a proof sketch, really--there's a few unexamined assumptions in there. It was the best I could do off the top of my head and typing on a smart phone, but I'm reasonably confident that the overall structure is valid. I was actually kinda hoping someone who knows more than I do would chime in and clarify things...
      - gwern 17y ago
        Well, here's another approach. We can solve the halting problem for any finite TM (http://portal.acm.org/citation.cfm?id=1052796.1052798 http://portal.acm.org/citation.cfm?id=1052796.1052798), so let's imagine we're looking at a possible BB, n. All we have to do is run all the possible programs, and see whether of the halting ones, one is bigger than n.
scott_s 17y ago
Within each novel, the characters can debate the literary merits of any of the sub-novels. But, by analogy with classes of machines that can’t analyze themselves, the characters can never critique the novel that they themselves are in. Clearly he's never seen Spaceballs. (Otherwise it's an excellent article.)
- ars 17y ago
  In spaceballs the characters are not doing it - the author of spaceballs is, and is putting words in their mouth.
  - scott_s 17y ago
    I think that's an irrelevant distinction - the same is true for everything a fictional character does.

Torn 17y ago

Outstanding introduction to this sort of thing, thanks for sharing.

dangoldin 17y ago

You should submit this on it's own to HN. That was a great read.

pbhjpbhj 17y ago

But do people fear big numbers? Certainly they do. Apathy !== fear. comforting smallness of mysticism? In what way is mysticism small? It is bigger by most definitions than anything we're capable of being consciously aware of. On topic, excellent; but the off-the-cuff remarks could have used a little more thought IMO.

Eliezer 17y ago
> In what way is mysticism small? It is bigger by most definitions Saying "infinite" creates a vague sensation of bigness that isn't anywhere near as big as, say, 3^^^3 (http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation http://en.wikipedia.org/wiki/Knuth%27s_up-arrow_notation) to say nothing of really large numbers. The idea of the night sky as "infinite" is nowhere near as shocking as the idea of galaxies a septillion meters away. It's like the difference between Thor, versus the machine superintelligences of Iain Banks's Culture or the Powers from Vernor Vinge's A Fire Upon the Deep. You can imagine the "infinite" Jehovah demanding the worship of Israelite tribespeople, but it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so. If you think of mystics as primitive amateur philosophers and science fiction writers who demand that their work be protected from ordinary criticism, you can see there's no way they'd be able to keep up with modern science fiction writers or modern mathematicians. In this light, words like "infinite" or "unimaginable" are just words - showing instead of telling, mere adjectives, a demand that we be impressed which isn't backed up by any actual ability to conceive of impressive things.
- pbhjpbhj 17y ago
  it's rather harder to visualize a mind 10^50 ops/sec large bothering to do so How about a more Leibnizian idea of the Creator having designed into the primordial energy event all of the consequences of existence - some slight fluctuation or variation being ultimately responsible for this internet post ... is that a valid activity for your concept of a mystical supermind. Or consider that the realist approach to many worlds is true - is the awareness of every subatomic interaction in every one of an infinite array of possible worlds, is that enough processing for you? How about if that mystical being is responsible for an infinite number of such worlds? You have a very large concept of the infinite aleph-0^^^...^^aleph-0 (I doubt you can verily comprehend those numbers though) or whatever but some numerological mystics would say those concepts are discovered from ideas embedded in the created order or inherited from a prime movers creative mind. Your view of mysticism is narrow.
  - pwmanagerdied 17y ago
    Your view of mysticism is wrong.
    - pbhjpbhj 17y ago
      In what way?

amalcon 17y ago

Yeah, that's a good one. The only complaint I have is that it contends that the Busy Beaver numbers grow faster than any computable sequence, but what it actually shows is that no computable sequence can be proven to grow faster than the Busy Beaver numbers. If a sequence happens to grow faster than the Busy Beaver sequence, but we can't prove it, then it doesn't help us prove anything about Turing machines.

camccann 17y ago
Consider a Turing machine M1 of size X that, given an input value n, calculates a function f(n) such that O(f(n)) > O(BB(n)) and halts. Consider a Turing machine M2 of size Y that calculates a number A and halts, where X + Y < A. Combine the two machines, using the number calculated by M2 as the input for M1. The resulting Turing machine of size X + Y calculates a value f(A) such that f(A) > BB(A) > BB(X + Y) and then halts. This contradicts the definition of BB(X + Y), therefore no such computable function f can exist.
- amalcon 17y ago
  Alright, this is a good proof. I therefore concede the point regarding the values themselves.
  - camccann 17y ago
    It's more of a proof sketch, really--there's a few unexamined assumptions in there. It was the best I could do off the top of my head and typing on a smart phone, but I'm reasonably confident that the overall structure is valid. I was actually kinda hoping someone who knows more than I do would chime in and clarify things...
    - gwern 17y ago
      Well, here's another approach. We can solve the halting problem for any finite TM (http://portal.acm.org/citation.cfm?id=1052796.1052798 http://portal.acm.org/citation.cfm?id=1052796.1052798), so let's imagine we're looking at a possible BB, n. All we have to do is run all the possible programs, and see whether of the halting ones, one is bigger than n.

scott_s 17y ago

Within each novel, the characters can debate the literary merits of any of the sub-novels. But, by analogy with classes of machines that can’t analyze themselves, the characters can never critique the novel that they themselves are in. Clearly he's never seen Spaceballs. (Otherwise it's an excellent article.)

ars 17y ago
In spaceballs the characters are not doing it - the author of spaceballs is, and is putting words in their mouth.
- scott_s 17y ago
  I think that's an irrelevant distinction - the same is true for everything a fictional character does.