The Program That Couldn't Be Told

The vacuum had been bumping the same chair leg for eleven minutes.

Soren leaned over the keyboard and stopped the script. "It got stuck in a loop. Again."

"So we write something that catches loops before they run," Maya said. She was already drawing on the whiteboard, a box with an arrow going into it. "A checker. We feed it the chore program. It tells us, this one finishes, or this one runs forever. Then we never get stuck again."

"A program that reads other programs."

"Reads them and decides. Halts or loops. Green light or red light." She tapped the box. "We call it Checker."

Soren liked it. It was clean. He pulled his notebook over and started listing the easy cases. "Counting to ten halts. Green. A loop that adds one forever and never stops, red. A vacuum that bumps a chair until the battery dies, eventually green, technically."

They built the simple version in an hour. It caught the obvious loops. Maya fed it the chair-bumping script and Checker lit up red, and she laughed out loud.

"Okay," Soren said. "But it only catches loops it recognizes. What about a program where you can't tell just by looking?"

"Then Checker has to be smarter. It has to handle any program. That's the whole point. We want one checker that works on everything."

Soren wrote ANY PROGRAM at the top of the page and underlined it twice. Then he sat very still and looked at the underline.

"What," Maya said.

"If Checker works on any program," he said slowly, "then it works on a program that has Checker inside it."

Maya stopped drawing.

"Say that again."

"Checker reads any program and says halt or loop. So I'm allowed to write a program that uses Checker. I can put Checker inside my own program. That's allowed, right? You said any program."

"Sure. Any program." She came over to the keyboard. "So write one."

Soren wrote it out by hand first, because the inside of his head was crowded. He made a little program. He called it Troublemaker.

"Here's what Troublemaker does," he said. "First it asks Checker about itself. About Troublemaker."

"It asks Checker, hey, do I halt?"

"Right. And then Troublemaker does the opposite of whatever Checker says."

Maya went quiet. Then she said, "Opposite how."

"If Checker says Troublemaker halts, then Troublemaker loops forever instead. And if Checker says Troublemaker loops forever, then Troublemaker stops right away." Soren put down the pencil. "It just does the opposite. On purpose."

Maya grabbed the marker. "Wait. Wait. Run it. Run it in your head. Checker looks at Troublemaker. Checker has to say something. Green or red. Say it says green. Halts."

"Then Troublemaker loops. Because it does the opposite."

"So Checker was wrong. It said halt and the thing looped."

"Okay so Checker says red instead. Loops forever."

"Then Troublemaker halts. Right away. Because opposite." Maya's voice climbed. "So Checker was wrong again. The other way."

They looked at each other.

"It's wrong if it says green," Soren said.

"And it's wrong if it says red."

"And those are the only two things it can say."

The garage was very quiet. The vacuum sat in the corner with its light off.

Maya wrote GREEN on one side of the board and RED on the other, and then she drew arrows from each one to the word WRONG, and she stood there holding the marker not writing anything else.

"It's not that Checker isn't smart enough," she said. "It's not a bug. We could make it as smart as we want."

"It still breaks," Soren said. "Because the program is allowed to listen to the answer and then do the opposite. As long as a program can hear what Checker says about it, it can turn around and make Checker a liar."

"So there's no Checker." Maya said it like she was testing whether the words held weight. "There's no Checker that works on every program. Not a slow one, not a fast one, not one a hundred years from now. None. It can't exist."

"Not because we're not clever enough." Soren wrote one line in his notebook, pressing hard. "Because of what it would have to be."

Maya sat down on the cold concrete. "I keep a list in my head," she said. "Of things that don't make sense yet. Stuff I haven't figured out. And the whole time I just figured, eventually. Eventually I get to all of them."

"Yeah."

"But this one isn't on that list. This is a different list." She looked up at him. "This is a thing nobody gets to. Not me when I'm older. Not the smartest computer anybody ever builds. There's an answer and you literally cannot make a machine that always finds it."

Soren nodded. "A man named Turing proved it. Before there were even real computers. He proved it about computers before they existed."

"He proved what they couldn't do before they could do anything." Maya laughed, but it was a strange laugh, the kind that comes out when something is too big to hold normally. "He found the edge first."

Soren looked at his little handwritten Troublemaker, six lines long. "There's a fence," he said. "Around what any machine can know about machines. And it's not far away. It's right here. We hit it building a vacuum cleaner."

"How many other fences are there." Maya wasn't really asking him. She was looking at the ceiling like it might be thinner than it looked. "How many things are true that nothing can ever check."

The vacuum's charge light blinked back on, green, and it gave a small beep, ready to start its chores again.

Neither of them got up to run it.

Maya took the marker and, under GREEN and RED and WRONG, in the empty bottom corner of the whiteboard, she drew a single line and left it open at both ends.