Connect with us

Tech

Are computers ready to solve this notoriously unwieldy math problem?

Published

on

rules for collatz rewrite


In a sense, the computer and the Collatz conjecture are a perfect match. For one, as Jeremy Avigad, a logician and professor of philosophy at Carnegie Mellon notes, the notion of an iterative algorithm is at the foundation of computer science—and Collatz sequences are an example of an iterative algorithm, proceeding step-by-step according to a deterministic rule. Similarly, showing that a process terminates is a common problem in computer science. “Computer scientists generally want to know that their algorithms terminate, which is to say, that they always return an answer,” Avigad says. Heule and his collaborators are leveraging that technology in tackling the Collatz conjecture, which is really just a termination problem.

“The beauty of this automated method is that you can turn on the computer, and wait.”

Jeffrey Lagarias

Heule’s expertise is with a computational tool called a “SAT solver”—or a “satisfiability” solver, a computer program that determines whether there is a solution for a formula or problem given a set of constraints. Though crucially, in the case of a mathematical challenge, a SAT solver first needs the problem translated, or represented, in terms that the computer understands. And as Yolcu, a PhD student with Heule, puts it: “Representation matters, a lot.”

A longshot, but worth a try

When Heule first mentioned tackling Collatz with a SAT solver, Aaronson thought, “There is no way in hell this is going to work.” But he was easily convinced it was worth a try, since Heule saw subtle ways to transform this old problem that might make it pliable. He’d noticed that a community of computer scientists were using SAT solvers to successfully find termination proofs for an abstract representation of computation called a “rewrite system.” It was a longshot, but he suggested to Aaronson that transforming the Collatz conjecture into a rewrite system might make it possible to get a termination proof for Collatz (Aaronson had previously helped transform the Riemann hypothesis into a computational system, encoding it in a small Turing machine). That evening, Aaronson designed the system. “It was like a homework assignment, a fun exercise,” he says.

“In a very literal sense I was battling a Terminator—at least a termination theorem prover.”

Scott Aaronson

Aaronson’s system captured the Collatz problem with 11 rules. If the researchers could get a termination proof for this analogous system, applying those 11 rules in any order, that would prove the Collatz conjecture true.

Heule tried with state-of-the-art tools for proving the termination of rewrite systems, which didn’t work—it was disappointing if not so surprising. “These tools are optimized for problems that can be solved in a minute, while any approach to solve Collatz likely requires days if not years of computation,” says Heule. This provided motivation to hone their approach and implement their own tools to transform the rewrite problem into a SAT problem.

A representation of the 11-rule rewrite system for the Collatz conjecture.

MARIJN HEULE

Aaronson figured it would be much easier to solve the system minus one of the 11 rules—leaving a “Collatz-like” system, a litmus test for the larger goal. He issued a human-versus-computer challenge: The first to solve all subsystems with 10 rules wins. Aaronson tried by hand. Heule tried by SAT solver: He encoded the system as a satisfiability problem—with yet another clever layer of representation, translating the system into the computer’s lingo of variables that can be either 0s and 1s—and then let his SAT solver run on the cores, searching for evidence of termination.

collatz visualization
The system here follows the Collatz sequence for the starting value 27—27 is at the top left of the diagonal cascade, 1 is at bottom right. There are 71 steps, rather than 111, since the researchers used a different but equivalent version of the Collatz algorithm: if the number is even then divide by 2; otherwise multiply by 3, add 1, and then divide the result by 2.

MARIJN HEULE

They both succeeded in proving that the system terminates with the various sets of 10 rules. Sometimes it was a trivial undertaking, for both the human and the program. Heule’s automated approach took at most 24 hours. Aaronson’s approach required significant intellectual effort, taking a few hours or even a day—one set of 10 rules he never managed to prove, though he firmly believes he could have, with more effort. “In a very literal sense I was battling a Terminator,” Aaronson says—“at least a termination theorem prover.”

Yolcu has since fine-tuned the SAT solver, calibrating the tool to better fit the nature of the Collatz problem. These tricks made all the difference—speeding up the termination proofs for the 10-rule subsystems and reducing runtimes to mere seconds.

“The main question that remains,” says Aaronson, “is, What about the full set of 11? You try running the system on the full set and it just runs forever, which maybe shouldn’t shock us, because that is the Collatz problem.”

As Heule sees it, most research in automated reasoning has a blind eye for problems that require lots of computation. But based on his previous breakthroughs he believes these problems can be solved. Others have transformed Collatz as a rewrite system, but it’s the strategy of wielding a fine-tuned SAT solver at scale with formidable compute power that might gain traction toward a proof.

So far, Heule has run the Collatz investigation using about 5,000 cores (the processing units powering computers; consumer computers have four or eight cores). As an Amazon Scholar, he has an open invitation from Amazon Web Services to access “practically unlimited” resources—as many as one million cores. But he’s reluctant to use significantly more.

“I want some indication that this is a realistic attempt,” he says. Otherwise, Heule feels he’d be wasting resources and trust. “I don’t need 100% confidence, but I really would like to have some evidence that there’s a reasonable chance that it’s going to succeed.”

Supercharging a transformation

“The beauty of this automated method is that you can turn on the computer, and wait,” says the mathematician Jeffrey Lagarias, of the University of Michigan. He’s toyed with Collatz for about fifty years and become keeper of the knowledge, compiling annotated bibliographies and editing a book on the subject, “The Ultimate Challenge.” For Lagarias, the automated approach brought to mind a 2013 paper by the Princeton mathematician John Horton Conway, who mused that the Collatz problem might be among an elusive class of problems that are true and “undecidable”—but at once not provably undecidable. As Conway noted: “… it might even be that the assertion that they are not provable is not itself provable, and so on.”

“If Conway is right,” Lagarias says, “there will be no proof, automated or not, and we will never know the answer.”

Tech

The US Supreme Court just gutted the EPA’s power to regulate emissions

Published

on

The US Supreme Court just gutted the EPA’s power to regulate emissions


What was the ruling?

The decision states that the EPA’s actions in a 2015 rule, which included caps on emissions from power plants, overstepped the agency’s authority.

“Capping carbon dioxide emissions at a level that will force a nationwide transition away from the use of coal to generate electricity may be a sensible ‘solution to the crisis of the day,’” the decision reads. “But it is not plausible that Congress gave EPA the authority to adopt on its own such a regulatory scheme.”

Only Congress has the power to make “a decision of such magnitude and consequence,” it continues. 

This decision is likely to have “broad implications,” says Deborah Sivas, an environmental law professor at Stanford University. The court is not only constraining what the EPA can do on climate policy going forward, she adds; this opinion “seems to be a major blow for agency deference,” meaning that other agencies could face limitations in the future as well.

The ruling, which is the latest in a string of bombshell cases from the court, fell largely along ideological lines. Chief Justice John Roberts authored the majority opinion, and he was joined by his fellow conservatives: Justices Samuel Alito, Amy Coney Barrett, Neil Gorsuch, Brett Kavanaugh, and Clarence Thomas. Justices Stephen Breyer, Elena Kagan, and Sonia Sotomayor dissented.

What is the decision all about?

The main question in the case was how much power the EPA should have to regulate carbon emissions and what it should be allowed to do to accomplish that job. That question was occcasioned by a 2015 EPA rule called the Clean Power Plan.

The Clean Power Plan targeted greenhouse-gas emissions from power plants, requiring each state to make a plan to cut emissions and submit it to the federal government.

Several states and private groups immediately challenged the Clean Power Plan when it was released, calling it an overreach on the part of the agency, and the Supreme Court put it on hold in 2016. After a repeal of the plan during Donald Trump’s presidency and some legal back-and-forth, a Washington, DC, district court ruled in January 2021 that the Clean Power Plan did fall within the EPA’s authority.

Continue Reading

Tech

How to track your period safely post-Roe

Published

on

How to track your period safely post-Roe


3. After you delete your app, ask the app provider to delete your data. Just because you removed the app from your phone does not mean the company has gotten rid of your records. In fact, California is the only state where they are legally required to delete your data. Still, many companies are willing to delete it upon request. Here’s a helpful guide from the Washington Post that walks you through how you can do this.

Here’s how to safely track your period without an app.

1. Use a spreadsheet. It’s relatively easy to re-create the functions of a period tracker in a spreadsheet by listing out the dates of your past periods and figuring out the average length of time from the first day of one to the first day of the next. You can turn to one of the many templates already available online, like the period tracker created by Aufrichtig and the Menstrual Cycle Calendar and Period Tracker created by Laura Cutler. If you enjoy the science-y aspect of period apps, templates offer the ability to send yourself reminders about upcoming periods, record symptoms, and track blood flow.

2. Use a digital calendar. If spreadsheets make you dizzy and your entire life is on a digital calendar already, try making your period a recurring event, suggests Emory University student Alexa Mohsenzadeh, who made a TikTok video demonstrating the process

Mohsenzadeh says that she doesn’t miss apps. “I can tailor this to my needs and add notes about how I’m feeling and see if it’s correlated to my period,” she says. “You just have to input it once.” 

3. Go analog and use a notebook or paper planner. We’re a technology publication, but the fact is that the safest way to keep your menstrual data from being accessible to others is to take it offline. You can invest in a paper planner or just use a notebook to keep track of your period and how you’re feeling. 

If that sounds like too much work, and you’re looking for a simple, no-nonsense template, try the free, printable Menstrual Cycle Diary available from the University of British Columbia’s Centre for Menstrual Cycle and Ovulation Research.

4. If your state is unlikely to ban abortion, you might still be able to safely use a period-tracking app. The crucial thing will be to choose one that has clear privacy settings and has publicly promised not to share user data with authorities. Quintin says Clue is a good option because it’s beholden to EU privacy laws and has gone on the record with its promise not to share information with authorities. 

Continue Reading

Tech

Composable enterprise spurs innovation

Published

on

Composable enterprise spurs innovation


Overall, 74% of companies accelerated plans to move to the cloud by more than a year, jettisoning legacy technologies and operating models to embrace data and applications, according to business analysis firm ZK Research.

A key part of that transformation relied on using applications, usually in the cloud, that integrated apps and data with low-code functionality to create more efficient workflows, more quickly than ever. Low-code is a software development approach for building processes and functionality with little or no code, which allows non-software developers to create applications.

Companies that structure daily workflows around these so-called “composable applications”—often called composable enterprises—have a much tighter relationship between technology and business units and can quickly assemble new applications and services at a fraction of the historical cost.

Composable applications provide a way to build on or add to applications in an easy way—think of building blocks: the work has already been done and additional functionality can be added to the foundational ability.

That flexibility is necessary for the variability of the current workplace and economy, says Zeus Kerravala, founder and principal analyst at ZK Research. “We’re moving to an era where in any given moment, you could have everyone in the office, no one in the office, or every reasonable combination in between,” Kerravala says. “You could have all your shoppers online, only a few, or—depending on your industry—no shoppers online and every possible combination between. The pandemic has created these dramatic shifts in the way we learn, the way we live, and the way we work, based on forces that are outside of anyone’s control.”

When it comes to cloud infrastructure, companies have often pursued half measures—adopting it in such a way as to reinforce old business models, creating private clouds that mimic their on-premises infrastructure. But composability gives enterprises the ability to adapt to changes in operations and in their markets by creating new applications to support needed workflows without hiring additional or outside software developers to implement the changes.

Composable cloud services further liberate companies from relying on running their own software instances solely to customize the code to their needs. Composable applications bring together cloud, customization, integration, and workflow management, allowing companies to be flexible and innovate quickly.

When businesses suffered pandemic disruptions to critical business functions—such as call centers, IT support, and medical administration—composable applications allowed firms to adapt and continue. In one case, a company needed to extend its call-center system, which was hosted in a controlled environment, to allow access to employees through web browsers running on an Amazon virtual machine, says David Lee, vice president of products at RingCentral, an enterprise communications platform that has focused on composability. “They had to make these changes work overnight at employees’ homes, and that was a great challenge for a lot of organizations,” Lee says. “Companies well-adapted to potential change actually made these transitions very easy by composing new applications and workflows.”

Continue Reading

Copyright © 2021 Seminole Press.