The Machine That Watched Itself

Soren had been staring at the screen for eleven minutes. Maya knew because she had been counting, and because eleven minutes of Soren being quiet meant he was either stuck or about to say something worth hearing.

"It crashed again," he said.

The program on the screen was simple. They had written it together, a little loop that checked whether numbers followed a pattern. Certain numbers went in, got multiplied or divided according to rules, and the program was supposed to stop when it reached one. It always reached one. They had tested forty numbers and every single one eventually collapsed down to one.

"Try a bigger number," Maya said.

"I tried ten thousand. It stopped. I tried a million. It stopped. But watch what happens with the path." Soren scrolled up. The sequence for the number twenty-seven started small, then ballooned up to over nine thousand before slowly, chaotically tumbling back down. "Twenty-seven takes a hundred and eleven steps. Twenty-six takes ten."

"So it's unpredictable," Maya said. "The size of the number doesn't tell you how long it takes."

"Right. But here is the thing that's bothering me." Soren opened his notebook, where he had written a question in block letters and then crossed it out and written it again. Does every number reach one?

"Nobody knows," Maya said. She had looked this up last week after her aunt mentioned it. The Collatz conjecture. Tested up to numbers so enormous they would fill rooms if you wrote them out. Every single one reached one. But no one had ever proved that all of them would.

"Okay, so I had an idea," Soren said. He turned to a second window on the screen, where he had written a different program. "What if we wrote a program that checks programs? Like, a program that looks at our Collatz program and tells us: will it stop, or will it run forever?"

Maya pulled her chair closer. "A program that predicts programs."

"Exactly. If we had that, we could feed it our Collatz checker for any number and it would tell us, yes it halts, or no it runs forever. And if it ever said 'runs forever,' we would have found a number that doesn't reach one."

"Soren, that would solve the whole conjecture."

"I know." He was grinning. "So let's write it."

They tried. For forty minutes they tried. They wrote programs that watched other programs run and tried to detect loops. They wrote programs that analyzed the code itself, looking for patterns that guaranteed stopping. Every version they built worked for some cases and failed for others. The tricky programs, the ones with behavior that depended on some deep mathematical question, just sat there. Their checker didn't crash. It just ran and ran, trying to decide, becoming the very thing it was supposed to predict.

"It's doing it again," Maya said. "Our checker is stuck on the question of whether the other program gets stuck."

Soren stared at the blinking cursor. Then he said, "What if we can't build it?"

"We're eleven. Obviously we can't build it."

"No. I mean what if no one can build it. Ever."

Maya went quiet in the way she went quiet when something clicked before she could explain it.

"Think about it," Soren said, and he was writing in his notebook now, fast, a diagram with arrows. "Say someone built a perfect checker. A program called H that takes any program and its input and says halt or loop. Perfect. Never wrong. Okay?"

"Okay."

"Now we build a new program. Call it K. K takes a program, feeds it to H, and if H says it will halt, then K deliberately loops forever. And if H says it will loop forever, K deliberately halts."

Maya's eyes narrowed. "K does the opposite of whatever H predicts."

"Now feed K to itself."

Silence.

Maya said, slowly, "If H says K-running-on-K will halt, then K loops. But H said it would halt. So H was wrong."

"And if H says K-running-on-K will loop forever," Soren continued, "then K halts. And H was wrong again."

"H is wrong no matter what it says."

"Which means H can't exist. Not broken. Not hard to build. Can't. Exist."

The rain was loud on the windows. Somewhere above them, a printer hummed to life and then went quiet.

Maya stood up and walked to the window. She pressed her forehead against the cold glass. Soren watched her reflection.

"This isn't about us not being smart enough," she said.

"No."

"This is about math. About logic. There is a wall built into the structure of what programs can know about themselves. Not a technology wall. A wall in the actual rules of the universe."

"Alan Turing proved it," Soren said quietly. "In nineteen thirty-six. Before computers were even really built. He proved the machine couldn't exist before the machine existed."

Maya turned from the window. "He figured out the limits of something that hadn't been invented yet."

"By imagining it precisely enough to ask the question."

Maya came back to the desk and sat down. She looked at the Collatz program, still obediently checking numbers, still finding one at the bottom of every path.

"So maybe there's a number out there that loops forever," she said. "And our program would run on it until the sun burns out. And no program, no matter how clever, could look at it beforehand and warn us."

"Or maybe every number halts and the proof is just beyond a different kind of wall. A wall in what we've figured out so far, not a wall in logic."

"Those are two very different kinds of walls."

"I know," Soren said. And then, because he was Soren, he said, "I think that might be the most important thing. Knowing which kind of wall you're looking at."

Maya reached past him and typed in a new number. Something large. Something nobody had probably tried in exactly this form. The program began running, the sequence climbing, numbers tumbling across the screen like water over rocks, rising, rising, refusing to settle.

They watched it together. It was still climbing. It was still going.

"It'll reach one," Maya said.

"Probably," Soren said.

Neither of them looked away.

The number climbed higher, and higher, and then, all at once, it began to fall.