News for hackers. Stuff that matters.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by cft on Thursday December 10, 2020 @11:28PM (#25382301)
I wonder how one goes about proving that such large computations as BB(27) are physically impossible in our universe?
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by cjfd on Thursday December 10, 2020 @11:54PM (#25382451)
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) 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.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by cft on Friday December 11, 2020 @12:02AM (#25382487)
But the number of states N required for BB(27) could be (much?) smaller than the number of steps of BB(27)?
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by tialaramex on Friday December 11, 2020 @12:18AM (#25382577)
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.

Re:How the Slowest Computer Programs Illuminate Math’s Funda... by JoshTriplett on Friday December 11, 2020 @12:21AM (#25382597)
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.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by cft on Friday December 11, 2020 @12:31AM (#25382660)
Yes, I should have thought more about it. So these BB(N) numbers are direct complexity bounds on various mathematical statements.
Re:How the Slowest Computer Programs Illuminate Math’s Funda... by chalst on Friday December 11, 2020 @04:48AM (#25383979)
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.