Posts Tagged ‘computing’
“Things that are so far removed from our daily experience… are inherently hard to understand”*…
That’s certainly true of numbers. And as the numbers grow, the cognitive challenges grow with them. (Indeed, by way of example: 1 million seconds, is roughly 11.5 days; 1 billion seconds is almost 32 years.)
We’ve looked before at the mysterious extremes of math: zero and infinity [and here]. But as Dan Falk reminds us, the numbers in between can seem pretty strange as well– especially the extremely large ones. In a review of Richard Elwes‘ Huge Numbers: A Story of Counting Ambitiously, From 4½ to Fish 7, Falk spotlights some of the largest numbers humans have ever contemplated…
… Aficionados of huge numbers are called “googologists,” a reference to the number 10100, known as a googol. Such numbers have a peculiar sort of existence. For the vast majority of us, they’re of limited everyday value. Calculations at the supermarket checkout, or at tax time in April, typically involve far more modest figures. Perhaps we’ve read that the U.S. national debt is in excess of $38 trillion — a mind-numbing figure, to be sure, but it’s not as though any one individual needs to count it up in stacks of $20 bills.
And yet, much larger numbers await those who seek them out. Consider the kinds of numbers that crop up in problems involving combinations and permutations. For example, in how many distinct ways can one shuffle a deck of cards? Elwes takes us through the calculation, and we end up with a figure of about 8×1067. Compared to that number, the odds of getting a royal flush when dealt a five-card poker hand seem pretty decent, sitting at a mere 1 in 649,740 (still rare enough that many poker players have never held such a hand). Or consider that famous 1980s cultural touchstone, the Rubik’s cube. In how many ways can one scramble the cube? It turns out that the figure is about 43 quintillion, or 4.3×1019 — but in spite of that ridiculously large figure, people do routinely solve the puzzle, and champions can do it in mere seconds. In fact, as Elwes explains, no Rubik’s cube arrangement is more than 20 moves away from any other arrangement.
Or consider the age of the universe, estimated to be about 13.8 billion years. This may seem like a lengthy span of time, but our cosmic future is where the really big numbers come up. Elwes examines the so-called heat death of the universe, in which all matter has broken down into subatomic particles. We may reach this point in [10 raised to the 10th power, raised again to the 120th power] years — this dizzying figure is 10 raised to the power of 10120 — at which point, Elwes says, the universe will have ballooned up to a diameter of 10 to the power of 10 to the power of 10120 light years. (Yes, that’s [10 raised to the 10th power, again to the 10th power, then to the 120th power] light years.) Elwes adds a footnote: “At this point, the choice of units hardly matters; the distance is so immense that whether we choose to measure it in Planck lengths or giga-light years makes little difference.” Let that sink in!
As mind numbing as such figures are, the highest numbers contemplated by humans come not from physics but from pure mathematics and computer science. Like “Graham’s number” — an immense figure put forward as the upper-bound for solutions to a problem in a branch of mathematics known as Ramsey theory. Some readers may find the ensuing discussion of multi-dimensional hypercubes a bit challenging, but one can enjoy the payoff regardless: We end up with a number that can’t even be expressed in conventional notation, and which earned a mention in the 1980 edition of the “Guinness Book of World Records” as “the highest number ever used in a mathematical proof.”
Reading this book is a little bit like sitting in the back row of an auction house where a rare Picasso (let’s say) is up for grabs: How high is this thing going to go? And indeed, Elwes keeps going. We eventually meet the so-called busy beaver numbers, a set of numbers that crop up in theoretical computer science, when one tries to deduce whether a particular computer program will eventually stop, or keep going forever — a conundrum known as the “halting problem.” As Elwes explains, it’s not at all straightforward to distinguish the two types of programs (and if it was, it would help mathematicians tackle some of the most vexing problems in their field).
The fifth busy beaver number, known as BB(5) — associated with a computer program that can access five internal states — works out to 47,176,870. And that’s as far as we’ve gotten, Elwes explains. No one has worked out the value of BB(6), but he assures us that it’s beyond the range of any physical computer; and BB(16) leaves even Graham’s number in the dust.
But wait, there’s more! “Rayo’s number,” concocted by Agustín Rayo — a dean and professor at MIT — using set theory, is bigger still (here’s a fun video about it); and “Fish 7,” mentioned in the book’s subtitle, named for a Japanese googologist who goes by the pseudonym “Fish,” builds on Rayo’s number, and … well, the details are not easily digested, but the mind-melting nature of these numbers comes across as a feature, not a bug, of Elwes’s story… the narrative is enlivened by explorations of the peculiarities of math history…
… Archimedes tried to estimate how many grains of sand would be needed to fill up the known universe, back in the third century B.C. Did he simply have too much time on his hands? Not at all, insists Elwes: The Greek thinker was articulating an important idea — that no matter how unfathomably large a quantity may be, we can describe it with precision, thanks to mathematics. “Archimedes,” he writes, “was penning a manifesto for the expressive power of large numbers.”…
… [Elwes focuses] on numbers that are ridiculously large and yet finite. In the end, perhaps this is the most mind-boggling fact of all: that these enormous numbers, from Graham’s number to Fish 7 and beyond, fall as far short of infinity as does the humble number 1…
The mysteries of the massive: “The Mind-Boggling Science of Enormous Numbers,” @danfalk.bsky.social on @richardelwes.bsky.social in @undark.org.
###
As we enumerate enormity, we might spare a thought for a seminal mathematician, Alan Turing; he died on this date in 1954. He was a foundational computer science pioneer (inventor of the Turing Machine (an influential model for the general-purpose computer), creator of the “Turing Test” (only too relevant in these AI-infected times), inspiration for “The Turing Award” (the “Nobel Prize of computing“), and cryptographer (leading member of the team that cracked the Enigma code during WWII).
“Do not fold, spindle, or mutilate”*…
Punched cards have a long history in machine control (dating back to Jacquard) and computing (starting with Babbage‘s Difference Engine), but it was Herman Hollerith who brought them into modern computation in the late 1880s… where punch cards remained for about 100 years. From the Smithsonian’s American History Museum…
In the late 1880s, American engineer Herman Hollerith saw a railroad punch card when he was trying to figure out new ways of compiling statistical information for the U.S. Census. His first punch card, like those used on railways, only had holes along the edges. The meaning of each hole was indicated on the card. By the time Hollerith tabulating equipment was used in the 1890 U.S. Census, holes were scattered across the cards, although their meaning was not indicated on it.
Hollerith and his employees at the Tabulating Machine Company in Washington, D.C. soon developed punched cards for use in compiling information for commercial enterprises such as railroads. They and staff of the U.S. Census Bureau prepared improved machines—these devices are shown in the object group on tabulating equipment. By the 1920s, the United States had two major manufacturers of punch card equipment, International Business Machines (the descendent of the Tabulating Machine Company) and Remington Rand (the descendent of Powers Accounting Machine Company established by Russian emigré and former Census Bureau employee James Powers). Each manufacturer developed a distinctive standard punch card. IBM cards had eighty columns of rectangular holes while those of Remington Rand had ninety columns of circular holes. Tabulating machines were widely used in both government and commerce, with cards designed to meet the needs of customers. For example, checks issued by the U.S. government often came on punch cards.
When IBM and Remington Rand began selling electronic computers in the years following World War II, punch cards became the preferred method of entering data and programs onto them. They also were used in later minicomputers and some early desktop calculators. Punch cards surviving in the Smithsonian collections reflect the widespread use of computers – they announced scores on standardized tests, served as a library cards, were part of the proof of mathematical theorems, and kept medical records. Some are printed with the names of users, from university computer centers and computer clubs to the Library of Congress to Bell Laboratories…
Browse the collection: “Punch Cards for Data Processing“
See also: here, here, and here.
* Ubiquitous warning on punch cards:
… in the 1950s, after the invention of the computer and its widespread business use, that everyone began to see punch cards. Companies sent punch cards out with bills: the telephone company, utility companies, and even department stores realized that they could save a step in their billing process, as well as making it easier for them to process the returned check, by using the cards themselves as the bills. By the 1960s, punch cards were familiar, everyday objects.
While company employees could be trusted to take care of the cards, the person in the street could not. Warnings were necessary. In the 1930s the University of Iowa used cards for student registration; on each card was printed “Do not fold or bend this card.” Cards reproduced in an IBM sales brochure of the 1930s read “Do not fold, tear, or mutilate this card” and “Do not fold tear or destroy.” I’m not sure when the canonical “Do not fold, spindle, or mutilate” first appeared; it’s one of those traditions whose author and origin is lost in the mists of time. Let’s consider the words one at a time, stop and take them seriously…
– “A Cultural History of the Punch Card” (from 1991; eminently worth reading in full)
###
As we contemplate chads (of which, punch cards produced a gracious plenty), we might spare a thought for Gerald Hawkins; he died on this date in 2003. An astronomer and author, he was best known for his work in archaeoastronomy— most of all, for his 1965 book, Stonehenge Decoded. In the early 1960s, Hawkins had used punch cards to load data modeling sun and moon movements onto magnetic tapes, then into an IBM 7090. The results led him to conclude, as the book argues, that the features at the monument were arranged in such a way as to predict a variety of astronomical events– that Stonehenge was a giant prehistoric observatory and computer. While some archaeologists are hesitant to accept Hawkins’ theories, many archaeoastronomers have built upon his work. More widely, scholars accept that the importance of astronomical alignment and large complexes being planned and constructed to fulfill cosmology has been demonstrated at other prehistoric sites, such as the Snake Mound and Cahokia in the U.S.
“Quantum computation is … nothing less than a distinctly new way of harnessing nature”*…
As the tools in the world around us change, the world– and we– change with them. The onslaught of AI is the change that seems to be grabbing most of our mindshare these days… and with reason. But there are, of course, other changes (in biotech, in materials science, et al.) that are also going to be hugely impactful.
Today, a look at the computing technology stalking up behind AI: quantum computing. As enthusiasts like David Deutsch (author of the quote above) argue, it can have tremendous benefits, perhaps especially in our ability to model (and thus better understand) our reality.
But quantum computing will, if/when it arrives, also present huge challenges to us as individuals and as societies– perhaps most prominently in its threat to the ways in which we protect our systems and our information: We’ve felt pretty safe for decades, secure in the knowledge that we could lose passwords to phising or hacks, but that it would take the “classical” computers we have 1 billion years to break today’s RSA-2048 encryption. A quantum computer could crack it in as little as a hundred seconds.
The technology has been “somewhere on the horizon” for 30 years… so not something that has seemed urgent to confront. But progress has accelerated; a recent Google paper reports on a programming and architectural breakthrough that greatly reduces the computing resources necessary to break classical cryptography… putting the prospect of “Q-Day” (the point at which quantum computers become powerful enough to break standard encryption methods (RSA, ECC), endangering global digital security) much closer, which would put everything from crypto-wallets to our e-banking accounts at risk.
Charlie Wood brings us up to speed…
Some 30 years ago, the mathematician Peter Shor took a niche physics project — the dream of building a computer based on the counterintuitive rules of quantum mechanics — and shook the world.
Shor worked out a way for quantum computers to swiftly solve a couple of math problems that classical computers could complete only after many billions of years. Those two math problems happened to be the ones that secured the then-emerging digital world. The trustworthiness of nearly every website, inbox, and bank account rests on the assumption that these two problems are impossible to solve. Shor’s algorithm proved that assumption wrong.
For 30 years, Shor’s algorithm has been a security threat in theory only. Physicists initially estimated that they would need a colossal quantum machine with billions of qubits — the elements used in quantum calculations — to run it. That estimate has come down drastically over the years, falling recently to a million qubits. But it has still always sat comfortably beyond the modest capabilities of existing quantum computers, which typically have just hundreds of qubits.
However, two different groups of researchers have just announced advances that notably reduce the gap between theoretical estimates and real machines. A star-studded team of quantum physicists at the California Institute of Technology went public with a design for a quantum computer that could break encryption with only tens of thousands of qubits and said that it had formed a company to build the machine. And researchers at Google announced that they had developed an implementation of Shor’s algorithm that is ten times as efficient as the best previous method.
Neither company has the hardware to break encryption today. But the results underscore what some quantum physicists had already come to suspect: that powerful quantum computers may be years away, rather than decades. “If you care about privacy or you have secrets, then you better start looking for alternatives,” said Nikolas Breuckmann, a mathematical physicist at the University of Bristol, who did not work on either of the papers.
While the new results may provide a jolt for the policymakers and corporations that guard our digital infrastructure, they also signal the rapid progress that physicists have made toward building machines that will let them more thoroughly explore the quantum world.
“We’re going to actually do this,” said Dolev Bluvstein, a Caltech physicist and CEO of the new company, Oratomic…
[Wood unpacks the history of the development of the technology and explores the challenges that remain; he concludes…]
… If any group succeeds at building a quantum computer that can realize Shor’s algorithm, it will mark the end an era — specifically, the “Noisy Intermediate Scale Quantum” era, as Preskill dubbed the pre-error-correction period in a 2018 paper. Each researcher has a vision for what to pursue first with a machine in the new “fault-tolerant” era.
[Robert] Huang said he would start by running Shor’s algorithm, just to prove that the device works. After that, he said he would try to use it to speed up machine learning — an application to be detailed in coming work.
Most of the architects building quantum computers, whether at Oratomic or other startups, are physicists at heart. They’re interested in physics, not cryptography. Specifically, they’re interested in all the things a computer fluent in the language of quantum mechanics could teach them about the quantum realm, such as what sort of materials might become superconductors even at warm temperatures. Preskill, for his part, would like to simulate the quantum nature of space-time.
The Caltech group knows it has years of work ahead before any of its dreams have a chance of coming true. But the researchers can’t wait to get started. “Pick a cooler life quest than building the world’s first quantum computer with your friends!” said a jubilant Bluvstein, reached by phone shortly before their paper went live, before rushing off to celebrate…
Eminently worth reading in full: “New Advances Bring the Era of Quantum Computers Closer Than Ever,” from @walkingthedot.bsky.social in @quantamagazine.bsky.social.
* David Deutsch, The Fabric of Reality
###
As we prepare, we might take a moment to appreciate just how vastly and deeply the legacy systems challenged by quantum computing run, recalling that on this date in 1959 Mary Hawes, a computer scientist for the Burroughs Corporation held a meeting of computers users, manufacturers, and academics at the University of Pennsylvania aimed at creating a common business oriented programming language. At the meeting, representative Grace Hopper suggested that they ask the Department of Defense to fund the effort to create such a language. Also attending was Charles Phillips who was director of the Data System Research Staff at the DoD and was excited by the possibility of a common language streamlining their operations. He agreed to sponsor the creation of such a language. This was the genesis of what would eventually become the COBOL language.
To this day COBOL is still the most common programming language used in business, finance, and administrative systems for companies and governments, primarily on mainframe systems, with around 200 billion lines of code still in production use… all of which are in question and/or at risk in a world of quantum computing.










You must be logged in to post a comment.