News for hackers. Stuff that matters.

A comment on How the Slowest Computer Programs Illuminate Math’s Fundamental Limits. Parent comment

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.
[ Parent | on HN ]
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.
[ Parent | on HN ]