Turing Machine

After the bell rang for the end of the first year of high school, I lingered in the classroom for a while to finish my final assignments. By the time the duty student finished cleaning up, I had already packed my bag. It was 9:15; the number 89 bus I needed to take ran every five minutes, with the last one departing at 9:30. There was still time.

Why was the light still on in the self-study room next door? I walked over, intending to switch it off, but saw Ling Quan inside, one hand supporting her head, the other flipping through a book.

"What are you..."

"Reading for pleasure." She held up the cover to show me: *Complexity* from the *First Push* series.

"Ah... I've been wanting to read that. Can I borrow it after the midterms?"

"You can borrow it now," she said, her voice a bit raspy. She didn't seem to be in high spirits.

"Uh, maybe in a couple of days... Why aren't you in the classroom?"

"Didn't want to stay there. It's full of people." She leaned back into her chair, her hand holding the book dropping listlessly. "The carbon dioxide concentration is too high; I can't breathe. I have no energy, and I don't want to do homework. The real problem is, I've run out of chocolate."

"Oh... I have some mints here, if you'd like..." I pulled a pack of black "Midnight Storm" mints from my pocket, which I always carried to keep myself from nodding off during class.

"Ha, that’ll do. Thanks." She reached out a thin, pale hand to take the candy. "But I still want chocolate. Trace amounts of anandamide, a cannabinoid analog..."

"How did you slip out of the classroom?"

"I told the head teacher I had to go grind through math competition problems, so she let me go. I wasn't lying, either—I did do a few problems, at least. ...These mints are so spicy! I like them."

"Well... are you heading out?" I asked.

She didn't speak, just silently packed her bag and returned her books and a small blue notebook to the locker in the study room.

"Aren't you in a rush to get home?"

"I told my mom I was staying late for self-study. She doesn't really object to anything as long as it's related to school."

"Ah..."

We turned off the last light and headed downstairs, guided by the eerie green glow of the "Exit" sign. A chilly autumn breeze swirled around us. Ling Quan was still wearing her white shirt under her school track jacket, pulling the zipper tight against her collar.

"Are you cold?"

"It’s perfect. It triggers the secretion of thyroxine and increases the excitability of the nervous system."

"…Well said. I’ll try wearing less during the midterms, too." I nodded thoughtfully.

"It’s a joke!" she mimicked Sheldon from *The Big Bang Theory*, the subtext clearly implying, "What a total idiot."

"Then let's run a bit; we won't be cold anymore."

"No." She suddenly grabbed my sleeve.

"Let's walk together. Let's walk slowly." She requested softly, her voice trembling slightly. "I forgot to account for the empty set in the first big problem on the pop quiz..."

"I only just... so I spent half an hour debating it, only to realize the problem said 'positive integers'! Oh, give me another mint! It’s so infuriating!"

"…I've been doing problems all night; let's stop talking about problems." I sighed.

"Hmm... okay. But give me another mint."

We merged into the flow of second-year students leaving school. Ling Quan unwrapped a candy and crunched it between her teeth.

"If only there were a program that could automatically solve these problems..."

"Pfft, hahahahaha... If we're talking about high school math problems, maybe one day there will be, but general mathematical propositions... what a shame, it's impossible." The mint seemed to have restored some of her vitality, and she began explaining strange things to me.

"Do you know about the Hilbert problems?"

"Not really... but I've heard his famous quote: 'We must know, we will know.'"

"Right. In 1900, he proposed '23 problems to be solved at the turn of the century,' and one of them—the so-called *Entscheidungsproblem*—" she recited the long German word—"is whether there is a definite procedure that can tell us, in a finite amount of time, whether any given proposition is true or false. It would be great if that were true. Goldbach's Conjecture, the Riemann Hypothesis... we could just feed these problems into a machine and let it run. Leibniz had similar fantasies even earlier; he built adders and multipliers and believed humanity would one day build a machine capable of determining the truth or falsehood of all mathematical propositions."

"Alright, alright, I get it... so hurry up and shatter my fantasy."

"Hmm... do you want to hear the proof using a Turing machine?"

"A Turing machine... is that a computer?"

"You could say a computer is a type of universal Turing machine. A Turing machine is a hypothetical device conceived by Turing. It has a read-write head," she pulled a mechanical pencil from her pocket and poked the tip, "and a paper tape with many squares marked with zeros and ones. The read-write head moves freely along the tape." She moved the pencil back and forth along her fingers. "The machine also has internal states; it changes its state based on the current state and the 0 or 1 it reads, moves left or right, or writes and erases marks in the current square." She clicked the end of the pencil *click-click*.

"Given an input tape, some Turing machines will run for a finite number of steps and then halt. Others will run forever—for instance, I could build a machine that moves right in state 1, reads a 0 or 1, and enters state 2, then in state 2 moves left and enters state 1, getting stuck in a 'left-right-left-right' loop... By the way, through some encoding, these rules can be written as a 01 tape, so they can either be stored inside the machine's head or be used as input. This is important!" She waved the pencil.

I nodded to show I was following.

"So, now we have a Turing machine—let's call him Xiao Ming—and an input tape. We run into a problem: can we determine, in a finite amount of time, through a definite procedure, whether Xiao Ming will halt when processing this tape?"

"Let's assume the answer is 'yes.' Then we would have a special Turing machine—let's call it the 'Inspector.' If he holds Xiao Ming's tape in his left hand and the input tape in his right—or maybe they're printed on the same tape, it doesn't matter—he could determine whether Xiao Ming would halt on that input. If he held Xiao Ming's tape in both hands, he could determine if Xiao Ming would halt on its own input. Imagine, for example, a robot factory where everyone has to have the Inspector check their tape before running it to avoid infinite loops... pretty good, eh?"

"But one day, the Inspector had a bit of a breakdown—whether he drank too much, ate too much chocolate, or a bug flew into his brain—anyway, when Xiao Ming wouldn't halt on an input, the sick Inspector would finish running the two tapes as usual and conclude 'will not halt.' But when Xiao Ming would halt, the sick Inspector himself would enter an infinite loop while processing those two tapes, and other machines would have to forcibly pull him off the tape. The situation became chaotic."

"So, the sick Inspector tried to perform a check on himself. He held his own tape in both hands to see if he would halt on his own input—and that's when the contradiction appeared."

"If he determines he will halt, he enters an infinite loop; if he determines he won't halt, he stops... So what happens to the sick Inspector?"

"By proof by contradiction, such a machine cannot exist. Or, if you really must ask what happened to him—he was likely incinerated by the heat generated from the friction between his read-write head and the tape."

I let out a sigh.

"Hilbert proposed other problems, like whether mathematics is complete—whether every mathematical proposition can be proven true or false using a finite set of axioms—and whether it is consistent—whether everything that can be proven is actually true."

"—This proposition is a false proposition!"

"Ha, you're clever. Later, Gödel proved that if an arithmetic system is consistent, it cannot be complete. Hey, what time is it?"

I looked up at the large electronic clock above the school gate: 9:30. We had been standing in the autumn wind for nearly fifteen minutes.

"…Are we Turing machines?" I asked my final question.

"Who knows? But I think we are."

"But I've never heard of anyone's brain getting stuck in an unpredictable infinite loop because of some strange input..."

She gave a noncommittal grin.

We reached the intersection where we had to part ways. She went left, I went right. It was time to dash to the bus stop so I wouldn't miss the last bus.

Before turning, Ling Quan stopped. "Gödel met Turing in heaven and said, 'See? Someone was bound to poison us!'" she said, then let out a breathless, wheezing laugh.

What was wrong? I looked back at her with concern. She shook her head, stared into my eyes, and returned to her usual smile.

"Nothing. It’s a joke."

It wasn't funny at all.