wp-plugin-hostgator
domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init
action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114ol-scrapes
domain was triggered too early. This is usually an indicator for some code in the plugin or theme running too early. Translations should be loaded at the init
action or later. Please see Debugging in WordPress for more information. (This message was added in version 6.7.0.) in /home4/scienrds/scienceandnerds/wp-includes/functions.php on line 6114Source:https:\/\/www.quantamagazine.org\/an-easy-sounding-problem-yields-numbers-too-big-for-our-universe-20231204\/#comments<\/a><\/br> Most researchers thought Lipton had cooked up the most complex possible vector addition systems, meaning he\u2019d raised the lower bound as high as it could go. The only thing missing, in that case, would be an upper bound to go with it \u2014 that is, a proof that there could be no system in which determining reachability was even harder. But nobody knew how to prove that. The computer scientist Ernst Mayr came closest when he proved<\/a> in 1981 that it\u2019s always possible, in principle, to determine reachability in any vector addition system. But his proof didn\u2019t put any quantitative upper bound on how hard the problem could be. There was a floor, but no ceiling in sight.<\/p>\n \u201cI certainly thought about it on and off,\u201d Lipton said. \u201cBut after a while I gave up, and as far as I could tell no one made any progress for what was like 40 years.\u201d<\/p>\n In 2015, the computer scientists J\u00e9r\u00f4me Leroux<\/a> and Sylvain Schmitz<\/a> finally established a quantitative upper bound<\/a> \u2014 one so high that researchers assumed it was just a first step that could be pushed down to meet Lipton\u2019s lower bound.<\/p>\n But that\u2019s not what happened. In 2019, researchers discovered a lower bound far higher than Lipton\u2019s, upending decades of conventional wisdom. The VAS reachability problem was far more complex than anyone had anticipated.<\/p>\n The shocking 2019 result grew out of failure. In 2018, Czerwi\u0144ski disproved a conjecture, by Leroux and Filip Mazowiecki<\/a>, a computer scientist now at the University of Warsaw, that would have helped to make progress on a related problem. In subsequent discussions, the researchers hit upon a promising new way to construct extra-complex vector addition systems, which could imply a new lower bound on the VAS reachability problem, where progress had stalled for so long.<\/p>\n \u201cEverything connected in my mind to VAS reachability,\u201d Czerwi\u0144ski recalled. During a semester with a light teaching load, he decided to focus exclusively on that problem, together with Leroux, Mazowiecki and two other researchers \u2014 S\u0142awomir Lasota<\/a> of the University of Warsaw and Ranko Lazi\u0107<\/a> of the University of Warwick.<\/p>\n After a few months, their efforts paid off. Czerwi\u0144ski and his colleagues demonstrated<\/a> that they could construct vector addition systems in which the shortest path between two states was related to the size of the system by a mathematical operation called tetration that makes even nightmarish double exponential growth seem tame.<\/p>\n Tetration is a straightforward extension of a pattern connecting the most familiar operations in mathematics, beginning with addition. Add together n <\/em>copies of a number, and the result is equivalent to multiplying that number by n<\/em>. If you multiply together n<\/em> copies of a number, that\u2019s equivalent to exponentiation, or raising the number to the n<\/em>th power. Tetration, often represented by a pair of arrows pointing up, is the next step in this sequence: Tetrating a number by n <\/em>means exponentiating it n<\/em> times to produce a tower of powers n<\/em> stories high.<\/p>\n It\u2019s hard to wrap your head around just how quickly tetration gets out of hand: $latex 2 uparrowuparrow 3$, or $latex 2^{2^2}$, is 16, $latex 2 \u00aduparrowuparrow \u00ad 4$ is just over 65,000, and $latex 2 \u00aduparrowuparrow \u00ad5$ is a number with nearly 20,000 digits. It\u2019s physically impossible to write down all the digits of $latex 2 uparrowuparrow \u00ad\u00ad6$ \u2014 a liability of living in such a small universe.<\/p>\n In their landmark result, Czerwi\u0144ski and his colleagues proved that there exist vector addition systems of size n <\/em>where the best way to determine reachability is to map out a path involving more than $latex 2 uparrowuparrow \u00ad\u00adn$ \u00ad\u00ad transitions, implying a new lower bound that dwarfed Lipton\u2019s. But as head-spinning as tetration is, it still wasn\u2019t the final word on the complexity of the problem.<\/p>\n Just a few months after the shocking new lower bound on the complexity of VAS reachability, Leroux and Schmitz pushed down<\/a> the upper bound they\u2019d established three years earlier, but they didn\u2019t get all the way down to tetration. Instead, they proved that the complexity of the reachability problem can\u2019t grow faster than a mathematical monstrosity called the Ackermann function.<\/p>\n To understand that function, take the pattern used to define tetration to its grim conclusion. The next operation in the sequence, called pentation, represents repeated tetration; it\u2019s followed by yet another operation (hexation) for repeated pentation, and so on.<\/p>\n The Ackermann function, denoted $latex A(n)$, is what you get when you move one step up this ladder of operations with each stop on the number line: $latex A(1) = 1 + 1$, $latex A(2) = 2 \u00d7 2$, $latex A(3) = 3^3$, $latex A(4)=4 uparrowuparrow 4=4^{4^{4^4}}$, and so on. The number of digits in $latex A(4)$ is itself a colossal number approximately equal to 1 quinquagintillion \u2014 that\u2019s the whimsical and rarely needed name for a 1 followed by 153 zeros. \u201cDon\u2019t worry about Ackermann of 5,\u201d advised Javier Esparza<\/a>, a computer scientist at the Technical University of Munich.<\/p>\n<\/div>\n <\/br><\/br><\/br><\/p>\n
\nAn Easy-Sounding Problem Yields Numbers Too Big for Our Universe<\/br>
\n2023-12-05 21:58:17<\/br><\/p>\nA Tower of Powers<\/strong><\/h2>\n
To Quinquagintillion and Beyond\u00a0 <\/strong><\/h2>\n