Tag: quanta magazine

The Quest to Find the Longest-Running Simple Computer Program

Posted on by faz_business


But just how much harder? In 1962, the mathematician Tibor Radó invented a new way to explore this question through what he called the busy beaver game. To play, start by choosing a specific number of rules—call that number n. Your goal is to find the n-rule Turing machine that runs the longest before eventually halting. This machine is called the busy beaver, and the corresponding busy beaver number, BB(n), is the number of steps that it takes.

In principle, if you want to find the busy beaver for any given n, you just need to do a few things. First, list out all the possible n-rule Turing machines. Next, use a computer program to simulate running each machine. Look for telltale signs that machines will never halt—for example, many machines will fall into infinite repeating loops. Discard all these non-halting machines. Finally, record how many steps every other machine took before halting. The one with the longest runtime is your busy beaver.

In practice, this gets tricky. For starters, the number of possible machines grows rapidly with each new rule. Analyzing them all individually would be hopeless, so you’ll need to write a custom computer program to classify and discard machines. Some machines are easy to classify: They either halt quickly or fall into easily identifiable infinite loops. But others run for a long time without displaying any obvious pattern. For these machines, the halting problem deserves its fearsome reputation.

The more rules you add, the more computing power you need. But brute force isn’t enough. Some machines run for so long before halting that simulating them step by step is impossible. You need clever mathematical tricks to measure their runtimes.

“Technology improvements definitely help,” said Shawn Ligocki, a software engineer and longtime busy beaver hunter. “But they only help so far.”

End of an Era

Busy beaver hunters started chipping away at the BB(6) problem in earnest in the 1990s and 2000s, during an impasse in the BB(5) hunt. Among them were Shawn Ligocki and his father, Terry, an applied mathematician who ran their search program in the off hours on powerful computers at Lawrence Berkeley National Laboratory. In 2007, they found a six-rule Turing machine that broke the record for the longest runtime: The number of steps it took before halting had nearly 3,000 digits. That’s a colossal number by any ordinary measure. But it’s not too big to write down. In 12-point font, those 3,000 digits will just about cover a single sheet of paper.

In 2022 Shawn Ligocki discovered a sixrule Turing machine whose runtime has more digits than the number of atoms in the...

In 2022, Shawn Ligocki discovered a six-rule Turing machine whose runtime has more digits than the number of atoms in the universe.

Photograph: Kira Treibergs

Three years later, a Slovakian undergraduate computer science student named Pavel Kropitz decided to tackle the BB(6) hunt as a senior thesis project. He wrote his own search program and set it up to run in the background on a network of 30 computers in a university lab. After a month he found a machine that ran far longer than the one discovered by the Ligockis—a new “champion,” in the lingo of busy beaver hunters.

“I was lucky, because people in the lab were already complaining about my CPU usage and I had to scale back a bit,” Kropitz wrote in a direct message exchange on the Busy Beaver Challenge Discord server. After another month of searching, he broke his own record with a machine whose runtime had over 30,000 digits—enough to fill about 10 pages.

How the Binding of Two Brain Molecules Creates Memories That Last a Lifetime

Posted on by faz_business


The original version of this story appeared in Quanta Magazine.

When Todd Sacktor was about to turn 3, his 4-year-old sister died of leukemia. “An empty bedroom next to mine. A swing set with two seats instead of one,” he said, recalling the lingering traces of her presence in the house. “There was this missing person—never spoken of—for which I had only one memory.” That memory, faint but enduring, was set in the downstairs den of their home. A young Sacktor asked his sister to read him a book, and she brushed him off: “Go ask your mother.” Sacktor glumly trudged up the stairs to the kitchen.

It’s remarkable that, more than 60 years later, Sacktor remembers this fleeting childhood moment at all. The astonishing nature of memory is that every recollection is a physical trace, imprinted into brain tissue by the molecular machinery of neurons. How the essence of a lived moment is encoded and later retrieved remains one of the central unanswered questions in neuroscience.

Sacktor became a neuroscientist in pursuit of an answer. At the State University of New York Downstate in Brooklyn, he studies the molecules involved in maintaining the neuronal connections underlying memory. The question that has always held his attention was first articulated in 1984 by the famed biologist Francis Crick: How can memories persist for years, even decades, when the body’s molecules degrade and are replaced in a matter of days, weeks or, at most, months?

In 2024, working alongside a team that included his longtime collaborator André Fenton, a neuroscientist at New York University, Sacktor offered a potential explanation in a paper published in Science Advances. The researchers discovered that a persistent bond between two proteins is associated with the strengthening of synapses, which are the connections between neurons. Synaptic strengthening is thought to be fundamental to memory formation. As these proteins degrade, new ones take their place in a connected molecular swap that maintains the bond’s integrity and, therefore, the memory.

Image may contain Francis Crick Face Head Person Photography Portrait Cup Accessories Formal Wear Tie and Adult

In 1984, Francis Crick described a biological conundrum: Memories last years, while most molecules degrade in days or weeks. “How then is memory stored in the brain so that its trace is relatively immune to molecular turnover?” he wrote in Nature.

Photograph: National Library of Medicine/Science Source

The researchers present “a very convincing case” that “the interaction between these two molecules is needed for memory storage,” said Karl Peter Giese, a neurobiologist at King’s College London who was not involved with the work. The findings offer a compelling response to Crick’s dilemma, reconciling the discordant timescales to explain how ephemeral molecules maintain memories that last a lifetime.

Molecular Memory

Early in his career, Sacktor made a discovery that would shape the rest of his life. After studying under the molecular memory pioneer James Schwartz at Columbia University, he opened his own lab at SUNY Downstate to search for a molecule that might help explain how long-term memories persist.

The molecule he was looking for would be in the brain’s synapses. In 1949, the psychologist Donald Hebb proposed that repeatedly activating neurons strengthens the connections between them, or, as the neurobiologist Carla Shatz later put it: “Cells that fire together, wire together.” In the decades since, many studies have suggested that the stronger the connection between neurons that hold memories, the better the memories persist.

In the early 1990s, in a dish in his lab, Sacktor stimulated a slice of a rat’s hippocampus—a small region of the brain linked to memories of events and places, such as the interaction Sacktor had with his sister in the den—to activate neural pathways in a way that mimicked memory encoding and storage. Then he searched for any molecular changes that had taken place. Every time he repeated the experiment, he saw elevated levels of a certain protein within the synapses. “By the fourth time, I was like, this is it,” he said.