Posts Tagged ‘Turing Machine’
“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).
“Simplicity, carried to the extreme, becomes elegance”*…
Jordana Cepelewicz on a very different approach to computing…
In 1936, the British mathematician Alan Turing came up with an idea for a universal computer. It was a simple device: an infinite strip of tape covered in zeros and ones, together with a machine that could move back and forth along the tape, changing zeros to ones and vice versa according to some set of rules. He showed that such a device could be used to perform any computation.
Turing did not intend for his idea to be practical for solving problems. Rather, it offered an invaluable way to explore the nature of computation and its limits. In the decades since that seminal idea, mathematicians have racked up a list of even less practical computing schemes. Games like Minesweeper or Magic: The Gathering could, in principle, be used as general-purpose computers. So could so-called cellular automata like John Conway’s Game of Life, a set of rules for evolving black and white squares on a two-dimensional grid.
In September 2023, Inna Zakharevich of Cornell University and Thomas Hull of Franklin & Marshall College showed that anything that can be computed can be computed by folding paper. They proved that origami is “Turing complete” — meaning that, like a Turing machine, it can solve any tractable computational problem, given enough time…
Read on for more on how folding paper can, in principle, be used to perform any possible computation: “How to Build an Origami Computer” from @jordanacep in @QuantaMagazine.
* Jon Franklin
###
As we contemplate calculation, we might send entropic birthday greeting to Rolf Landauer; he was born on this date in 1927. A physicist, we made important contributions made important contributions in several areas of the thermodynamics of information processing, condensed matter physics, and the conductivity of disordered media… most of which important to the development of computing (of the electronic variety).
He is best known for his discovery and formulation of what’s known as Landauer’s principle: that in any logically irreversible operation that manipulates information, such as erasing a bit of memory, entropy increases and an associated amount of energy is dissipated as heat– a “thermodynamic cost of forgetting,” relevant to chip design (how closely packed elements can be on a chip and still handle the heat), reversible computing, quantum information, and quantum computing… but not an issue for origami.)
“If everybody contemplates the infinite instead of fixing the drains, many of us will die of cholera”*…
A talk from Maciej Cegłowski that provides helpful context for thinking about A.I…
In 1945, as American physicists were preparing to test the atomic bomb, it occurred to someone to ask if such a test could set the atmosphere on fire.
This was a legitimate concern. Nitrogen, which makes up most of the atmosphere, is not energetically stable. Smush two nitrogen atoms together hard enough and they will combine into an atom of magnesium, an alpha particle, and release a whole lot of energy:
N14 + N14 ⇒ Mg24 + α + 17.7 MeV
The vital question was whether this reaction could be self-sustaining. The temperature inside the nuclear fireball would be hotter than any event in the Earth’s history. Were we throwing a match into a bunch of dry leaves?
Los Alamos physicists performed the analysis and decided there was a satisfactory margin of safety. Since we’re all attending this conference today, we know they were right. They had confidence in their predictions because the laws governing nuclear reactions were straightforward and fairly well understood.
Today we’re building another world-changing technology, machine intelligence. We know that it will affect the world in profound ways, change how the economy works, and have knock-on effects we can’t predict.
But there’s also the risk of a runaway reaction, where a machine intelligence reaches and exceeds human levels of intelligence in a very short span of time.
At that point, social and economic problems would be the least of our worries. Any hyperintelligent machine (the argument goes) would have its own hypergoals, and would work to achieve them by manipulating humans, or simply using their bodies as a handy source of raw materials.
… the philosopher Nick Bostrom published Superintelligence, a book that synthesizes the alarmist view of AI and makes a case that such an intelligence explosion is both dangerous and inevitable given a set of modest assumptions.
[Ceglowski unpacks those assumptions…]
If you accept all these premises, what you get is disaster!
Because at some point, as computers get faster, and we program them to be more intelligent, there’s going to be a runaway effect like an explosion.
As soon as a computer reaches human levels of intelligence, it will no longer need help from people to design better versions of itself. Instead, it will start doing on a much faster time scale, and it’s not going to stop until it hits a natural limit that might be very many times greater than human intelligence.
At that point this monstrous intellectual creature, through devious modeling of what our emotions and intellect are like, will be able to persuade us to do things like give it access to factories, synthesize custom DNA, or simply let it connect to the Internet, where it can hack its way into anything it likes and completely obliterate everyone in arguments on message boards.
From there things get very sci-fi very quickly.
[Ceglowski unspools a scenario in whihc Bostrom’s worst nightmare comes true…]
This scenario is a caricature of Bostrom’s argument, because I am not trying to convince you of it, but vaccinate you against it.
…
People who believe in superintelligence present an interesting case, because many of them are freakishly smart. They can argue you into the ground. But are their arguments right, or is there just something about very smart minds that leaves them vulnerable to religious conversion about AI risk, and makes them particularly persuasive?
Is the idea of “superintelligence” just a memetic hazard?
When you’re evaluating persuasive arguments about something strange, there are two perspectives you can choose, the inside one or the outside one.
Say that some people show up at your front door one day wearing funny robes, asking you if you will join their movement. They believe that a UFO is going to visit Earth two years from now, and it is our task to prepare humanity for the Great Upbeaming.
The inside view requires you to engage with these arguments on their merits. You ask your visitors how they learned about the UFO, why they think it’s coming to get us—all the normal questions a skeptic would ask in this situation.
Imagine you talk to them for an hour, and come away utterly persuaded. They make an ironclad case that the UFO is coming, that humanity needs to be prepared, and you have never believed something as hard in your life as you now believe in the importance of preparing humanity for this great event.
But the outside view tells you something different. These people are wearing funny robes and beads, they live in a remote compound, and they speak in unison in a really creepy way. Even though their arguments are irrefutable, everything in your experience tells you you’re dealing with a cult.
Of course, they have a brilliant argument for why you should ignore those instincts, but that’s the inside view talking.
The outside view doesn’t care about content, it sees the form and the context, and it doesn’t look good.
[Ceglowski then engages the question of AI risk from both of those perspectives; he comes down on the side of the “outside”…]
The most harmful social effect of AI anxiety is something I call AI cosplay. People who are genuinely persuaded that AI is real and imminent begin behaving like their fantasy of what a hyperintelligent AI would do.
In his book, Bostrom lists six things an AI would have to master to take over the world:
- Intelligence Amplification
- Strategizing
- Social manipulation
- Hacking
- Technology research
- Economic productivity
If you look at AI believers in Silicon Valley, this is the quasi-sociopathic checklist they themselves seem to be working from.
Sam Altman, the man who runs YCombinator, is my favorite example of this archetype. He seems entranced by the idea of reinventing the world from scratch, maximizing impact and personal productivity. He has assigned teams to work on reinventing cities, and is doing secret behind-the-scenes political work to swing the election.
Such skull-and-dagger behavior by the tech elite is going to provoke a backlash by non-technical people who don’t like to be manipulated. You can’t tug on the levers of power indefinitely before it starts to annoy other people in your democratic society.
I’ve even seen people in the so-called rationalist community refer to people who they don’t think are effective as ‘Non Player Characters’, or NPCs, a term borrowed from video games. This is a horrible way to look at the world.
So I work in an industry where the self-professed rationalists are the craziest ones of all. It’s getting me down… Really it’s a distorted image of themselves that they’re reacting to. There’s a feedback loop between how intelligent people imagine a God-like intelligence would behave, and how they choose to behave themselves.
So what’s the answer? What’s the fix?
We need better scifi! And like so many things, we already have the technology…
[Ceglowski eaxplains– and demostrates– what he means…]
In the near future, the kind of AI and machine learning we have to face is much different than the phantasmagorical AI in Bostrom’s book, and poses its own serious problems.
It’s like if those Alamogordo scientists had decided to completely focus on whether they were going to blow up the atmosphere, and forgot that they were also making nuclear weapons, and had to figure out how to cope with that.
The pressing ethical questions in machine learning are not about machines becoming self-aware and taking over the world, but about how people can exploit other people, or through carelessness introduce immoral behavior into automated systems.
And of course there’s the question of how AI and machine learning affect power relationships. We’ve watched surveillance become a de facto part of our lives, in an unexpected way. We never thought it would look quite like this.
So we’ve created a very powerful system of social control, and unfortunately put it in the hands of people who run it are distracted by a crazy idea.
What I hope I’ve done today is shown you the dangers of being too smart. Hopefully you’ll leave this talk a little dumber than you started it, and be more immune to the seductions of AI that seem to bedevil smarter people…
In the absence of effective leadership from those at the top of our industry, it’s up to us to make an effort, and to think through all of the ethical issues that AI—as it actually exists—is bringing into the world…
Eminently worth reading in full: “Superintelligence- the idea that eats smart people,” from @baconmeteor.
* John Rich
###
As we find balance, we might recall that it was on thsi date in 1936 that Alan Turing‘s paper, “On Computable Numbers, with an Application to the Entscheidungsproblem,” in which he unpacked the concept of what we now call the Turing Machine, was received by the London Mathematical Society, which published it several months later. It was, as (Roughly) Daily reported a few days ago, the start of all of this…
“Machines take me by surprise with great frequency”*…
In search of universals in the 17th century, Gottfried Leibniz imagined the calculus ratiocinator, a theoretical logical calculation framework aimed at universal application, that led Norbert Wiener to suggest that Leibniz should be considered the patron saint of cybernetics. In the 19th century, Charles Babbage and Ada Lovelace took a pair of whacks at making it real.
Ironically, it was confronting the impossibility of a universal calculator that led to modern computing. In 1936 (the same year that Charlie Chaplin released Modern Times) Alan Turing (following on Godel’s demonstration that mathematics is incomplete and addressing Hilbert‘s “decision problem,” querying the limits of computation) published the (notional) design of a “machine” that elegantly demonstrated those limits– and, as Sheon Han explains, birthed computing as we know it…
… [Hilbert’s] question would lead to a formal definition of computability, one that allowed mathematicians to answer a host of new problems and laid the foundation for theoretical computer science.
The definition came from a 23-year-old grad student named Alan Turing, who in 1936 wrote a seminal paper that not only formalized the concept of computation, but also proved a fundamental question in mathematics and created the intellectual foundation for the invention of the electronic computer. Turing’s great insight was to provide a concrete answer to the computation question in the form of an abstract machine, later named the Turing machine by his doctoral adviser, Alonzo Church. It’s abstract because it doesn’t (and can’t) physically exist as a tangible device. Instead, it’s a conceptual model of computation: If the machine can calculate a function, then the function is computable.
…
With his abstract machine, Turing established a model of computation to answer the Entscheidungsproblem, which formally asks: Given a set of mathematical axioms, is there a mechanical process — a set of instructions, which today we’d call an algorithm — that can always determine whether a given statement is true?…
… in 1936, Church and Turing — using different methods — independently proved that there is no general way of solving every instance of the Entscheidungsproblem. For example, some games, such as John Conway’s Game of Life, are undecidable: No algorithm can determine whether a certain pattern will appear from an initial pattern.
…
Beyond answering these fundamental questions, Turing’s machine also led directly to the development of modern computers, through a variant known as the universal Turing machine. This is a special kind of Turing machine that can simulate any other Turing machine on any input. It can read a description of other Turing machines (their rules and input tapes) and simulate their behaviors on its own input tape, producing the same output that the simulated machine would produce, just as today’s computers can read any program and execute it. In 1945, John von Neumann proposed a computer architecture — called the von Neumann architecture — that made the universal Turing machine concept possible in a real-life machine…
As Turing said, “if a machine is expected to be infallible, it cannot also be intelligent.” On the importance of thought experiments: “The Most Important Machine That Was Never Built,” from @sheonhan in @QuantaMagazine.
* Alan Turing
###
As we sum it up, we might spare a thought for Martin Gardner; he died on this date in 2010. Though not an academic, nor ever a formal student of math or science, he wrote widely and prolifically on both subjects in such popular books as The Ambidextrous Universe and The Relativity Explosion and as the “Mathematical Games” columnist for Scientific American. Indeed, his elegant– and understandable– puzzles delighted professional and amateur readers alike, and helped inspire a generation of young mathematicians.
Gardner’s interests were wide; in addition to the math and science that were his power alley, he studied and wrote on topics that included magic, philosophy, religion, and literature (c.f., especially his work on Lewis Carroll– including the delightful Annotated Alice— and on G.K. Chesterton). And he was a fierce debunker of pseudoscience: a founding member of CSICOP, and contributor of a monthly column (“Notes of a Fringe Watcher,” from 1983 to 2002) in Skeptical Inquirer, that organization’s monthly magazine.
“If you are confused by the underlying principles of quantum technology – you get it!”*…
A tour through the map above– a helpful primer on the origins, development, and possible futures of quantum computing…
From Dominic Walliman (@DominicWalliman) on @DomainOfScience.
* Kevin Coleman
###
As we embrace uncertainty, we might spare a thought for
Alan Turing; he died on this date in 1954. A British mathematician, he was a foundational computer science pioneer (inventor of the Turing Machine, creator of the “Turing Test” (perhaps to b made more relevant by quantum computing :), and inspiration for “The Turing Award“) and cryptographer (leading member of the team that cracked the Enigma code during WWII).
You must be logged in to post a comment.