3 ms·

I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?

by cft 6y ago

cjfd 6y ago
If a computation goes through N states before completing the universe in which it takes place has to have at least N possible states. One theory (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) would state that the possible number of bits of information in a universe with radius R is the surface of the sphere 4 * pi * R^2 expressed in Planck units. This gives a limit to how many states this universe can have.
- cft 6y ago
  But the number of states N required for BB(27) could be (much?) smaller than the number of steps of BB(27)?
  - tialaramex 6y ago
    Nope. Suppose that say, state #16 and state #416 are in fact identical. Well then this machine does not halt, as of course being in this state leads back to the same state again in just four hundred moves, state #17 and #417 and so on will be the same too. The notional paper tape might have identical states, but if this happens in a machine that does eventually halt the rest of the machine state must be different, and these are both state that a universe must keep in order to instantiate the machine.
  - JoshTriplett 6y ago
    Different senses of the word "state". Such a machine could have fewer state-machine states than steps, but the overall state of the machine (including all its auxiliary storage) must never repeat, or it's in a loop and will never terminate. And BB machines must terminate, by definition.
    - cft 6y ago
      Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.
  - chalst 6y ago
    Smaller, yes: if a TM uses n bits of space, its execution time can exceed any polynomial of n in steps. But any such space-bounded deterministic computation that takes 2^n steps will not terminate, by exhaustion of possible state transitions, and nontermination would mean it does not compute a function over all inputs. This constraint is small in terms of the kind of growth functions this kind of maths deals with.

I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?

by cft 6y ago

I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?

cjfd 6y ago

If a computation goes through N states before completing the universe in which it takes place has to have at least N possible states. One theory (https://en.wikipedia.org/wiki/Bekenstein_bound https://en.wikipedia.org/wiki/Bekenstein_bound) would state that the possible number of bits of information in a universe with radius R is the surface of the sphere 4 * pi * R^2 expressed in Planck units. This gives a limit to how many states this universe can have.

cft 6y ago
But the number of states N required for BB(27) could be (much?) smaller than the number of steps of BB(27)?
- tialaramex 6y ago
  Nope. Suppose that say, state #16 and state #416 are in fact identical. Well then this machine does not halt, as of course being in this state leads back to the same state again in just four hundred moves, state #17 and #417 and so on will be the same too. The notional paper tape might have identical states, but if this happens in a machine that does eventually halt the rest of the machine state must be different, and these are both state that a universe must keep in order to instantiate the machine.
- JoshTriplett 6y ago
  Different senses of the word "state". Such a machine could have fewer state-machine states than steps, but the overall state of the machine (including all its auxiliary storage) must never repeat, or it's in a loop and will never terminate. And BB machines must terminate, by definition.
  - cft 6y ago
    Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.
- chalst 6y ago
  Smaller, yes: if a TM uses n bits of space, its execution time can exceed any polynomial of n in steps. But any such space-bounded deterministic computation that takes 2^n steps will not terminate, by exhaustion of possible state transitions, and nontermination would mean it does not compute a function over all inputs. This constraint is small in terms of the kind of growth functions this kind of maths deals with.