The Halting Problem: Free Fiction for Fyretober, October 3, 2023

The good folks at Fyrecon have declared this to be Fyretober: a month of creative prompts, encouraging writers, poets, and artists to share their explorations. Today’s prompt: No exit.

The Halting Problem

“Mr. Hudson.” I sank down in my auditorium seat and tried to hide behind the tall blonde hair of the woman in front of me. I should’ve remembered her name, I’d seen her before, but it just eluded me.

And hiding didn’t help. Professor Moorehead looked right past her. “Mr. Hudson, you will now come to the board and present the proof of the Halting Problem.”

I looked down at my lap. At least I was wearing pants this time. But my feet… They were taloned lizard feet. I knew better than to try to figure that out. It just was.

As always, there was nothing to do but to play it out. I got up from my chair and squeezed myself around the knees of the other students toward the aisle. At least all of them had lizard feet, too. I wouldn’t stand out.

And Professor Moorehead… Well, he was a full-on Sleestak, the lizard monsters from The Land of the Lost. Thanks, mom, I thought, for polluting my memories with your trash TV.

I reached the aisle and headed toward the front of the auditorium where Professor Moorehead stood waiting. He held out a piece of chalk. “You’ll need this.”

I reached out my hand, and that’s when I knew that I was a Sleestak, too. And not just any Sleestak: where Professor Moorehead’s scales were green, my two-clawed hands were sheathed in iridescent gold. I was the genius Sleestak. What was his name? Enos?

I shook my head. No, Enos was a deputy. Different show. And it didn’t matter either way. I was still myself, Wayne Hudson, whatever my body might be here in this…

Dream? No, I still hadn’t worked that out. This scene, played out in one variation after another, wasn’t a dream. I was too lucid. The scene had dream logic, but it also had all the crisp detail of 4K TV. Or even better. Damn it, this entire place was real… even if it was all in my head.

And the scene kept playing. It was important, somehow, but I couldn’t figure out why. Over and over, I tried to prove the Halting Problem. I took the long stick of chalk between my claws, and I looked at the board. I lifted the chalk.

Professor Moorehead said, “Ah, ah, ah… State your premise before you delve into the mathematical logic.”

I sighed, and I turned back to the auditorium. I now faced an entire room full of Sleestaks, save for the blonde woman who had become one of the furry monkey people. I forgot entirely what those had been called.

Had I ever seen a Sleestak giggle? Some of them couldn’t contain their mirth at my expense. Big green heads with huge round eyes bobbed in amusement, emitting hissing chuckles. Hck-hck-hck…

Explaining the Halting Problem wasn’t the hard part, that was proving it – or proving it was impossible. But I would explain just to buy some time. “The Halting Problem is an early achievement in computational logic, first solved by Alan Turing. Their idea of algorithms back then was nearly unrecognizable by modern standards, but mathematically rigorous beyond the standards of mere engineering. That simple code was closer to a logical proof than to a program. When an algorithm was done, you knew what it did beyond any question.

“Except for a few hypothetical cases. Emil Post proposed this thought experiment: Can you write a program such that it can examine another program and its inputs and determine without error whether the second program will run to completion or will cycle forever?”

The monkey woman raised her hand. “And did he write this program?”

I shook my head. “He couldn’t. You can’t, and I can’t. Instead, he proved that the problem cannot be solved.”

Professor Moorehead tapped his claws on his desktop. “And how, Mr. Hudson, did he do that? That’s your task for today. Show us how it’s done.”

So much for stalling for time. I turned back to the board; and for just a brief instant, the proof was right there! Already chalked on the board for me. I had only to read it off!

But before I could, a gust of cold wind blew through the auditorium, and the chalk dust whisped away in a cloud.

I raised my claws and smashed the blackboard, cracking the ancient slate in defeat. “I can’t do it! I just… I can’t remember!” In despair, I leaned my forehead against the board.

That hurt! That… hurt! I realized once again that this wasn’t a dream, not in any ordinary sense. Never had I felt that much pain in a dream. Memories of pain, yes, but nothing…

Nothing like what? Something was missing.

I twisted my head to the side, and I saw that my fists were human once more. I looked down, and I was barefoot – but my feet were human.

I turned around. Professor Moorehead was human. So were all of the students, save for the blonde-haired woman. What was her name? Whoever she was, she wasn’t in the auditorium anymore.

Moorehead looked over his glasses and gave me a pitying look. “You have failed, Mr. Hudson.”

I shook my head, and an echo of the pain jolted me. “I know this! I. Know. This!”

“You do not, Mr. Hudson.” Now Moorehead’s look was stern. “You have failed. Take your books and go see Dr. Walchek.”

“But –”

“Dr. Walchek will see to you.” Moorehead stepped aside, and the hallway door gaped open behind him. I stood motionless. I just needed another chance…

The students started chanting. “Walchek! Walchek! Walchek!” One in the front row got up. This was… This was Bill Laimbeer, an original Sleestak, in his Pistons uniform. The man was more than a foot taller than me, and a lot stronger. He grabbed my arm, dragged me to the door, and slammed it behind me. The bang made my head throb.

The corridor wasn’t familiar. I thought I knew every hall in the computer science department. But this… It didn’t have the soft beige paneling of the department, nor the short-pile brown carpeting. The floor was tiled in shades of blue and gray, which matched the blue frames around the doors. The walls were darker blue, and the doors were pale blonde wood, each with a long metal latch.

I didn’t know where I was, but I knew where I didn’t want to be: the end of that corridor, the room where Dr. Walchek waited. Instead I grabbed the first latch that I saw, and I tried to turn it. But it was locked. And so was the next one, and the next. Worse, I heard things through the doors: sobbing and gurgling, beeping, and something that might be hushed voices muffled by the wood.

I didn’t want to go to the end of the corridor, so I turned the other way. But that room lay that way as well. Whichever way I turned, the same destination waited.

I planted my feet. “I’m not going.”

But my feet had other ideas. Despite my determination, my bare feet shambled forward. I looked down, and now I saw remnants of shoes on them, as if my favorite old Converse had been ripped off my feet. The tile was cold, a concrete sensation that I tried to fixate upon. If I could just stop and feel the tile… But I kept walking.

When I reached the end of the corridor, there was only one more door on the left. To the right was a lounge filled with soft-cushioned chairs and a TV playing 80s music videos. No one seemed to be watching it. I tried to sit; but the door across the corridor opened, and I was pulled in.

There was no mistaking it: it was a patient room in a hospital. There was a wide door near the entrance, no doubt leading to a bathroom. There was a sink across from that door, with cupboards above and below. A white rabbit sat in the sink, chewing on cabbage.

Beyond these was the massive hospital bed. A… a still, bandaged form lay in the bed. Beside the bed stood a medium-height balding man in a white lab coat, carrying a stethoscope. His face was serious and frowning as he spoke to the blonde-haired woman who stood next to him. She looked down at the figure in the bed as she listened.

“I’m sorry, Mrs. Hudson,” Dr. Walchek said. “His frontal lobes have collapsed again.”

The woman choked back sobs and said, “What do you mean, collapsed?”

The doctor shrugged. “There’s so much that we still don’t understand, even with all these new fMRI tools. We still can’t explain how consciousness happens, so we can’t stimulate it. We can maintain the fundamental wave patterns, but consciousness itself… It’s an emergent property.”

Wanda looked up at that –

Wanda! Yes! I had a name. And a memory. This was Wanda… Wanda…

I couldn’t come up with a name. All I had was a memory of this beautiful woman on a beach chair by a pool, looking up at the sky and laughing at something I’d said. I wasn’t sure what it was now, but I wanted to say it again just to hear that laugh. Say it to…

Her name was gone.

As if no time had passed for her and the doctor, she said, “An emergent property? Wayne used to speak of those in his research.”

Dr, Walchek nodded. “It’s a very scientific way to say: We don’t know. This thing just happens in complex system, but we can’t say why. But whatever the cause, he doesn’t have it.”

“You’re telling me he’s gone?”

“No! No, no, no. He’s in there. His dreams are in there. We can pick up telltales, and we know that there’s deeper cognition going on. We can keep that going, sort of like a brain pacemaker. That inner self we can keep going, but only he can pull his consciousness out.”

“How?”

Dr. Walchek sighed. “That’s the emergent part. We have a theory which is that consciousness asserts itself when it has a problem to solve.”

“That’s why you had me play that lecture?”

“Yes. I’m sorry, the neurobiologist should’ve explained this. We thought that Dr. Hudson’s lecture notes could reawaken that part of his brain, causing him to focus on a problem that he knows.”

“But it did!”

“You have to understand, Mrs. Hudson, this approach is still in its infancy. We saw glimmers of forebrain activity, as if he was trying to solve a problem; but then he lost it. Every time.”

“Then try again!”

“It’s not that simple. We tried five times. And his… his level of conscious activity declined each time, rather than rising. As if frustration is undermining his confidence.”

No! I shouted. Give me another chance.

They didn’t respond. I could hear them, but they weren’t hearing me. I wasn’t really talking. Somehow I was hovering just between dream and consciousness, enough to comprehend them, but not conscious enough to find my way out of this trap.

But then, as if she had heard me, Wanda – Wanda! – echoed me. “No, I believe in him. Give him another chance.”

Dr. Walchek nodded and made a note on his tablet. “You’re his wife. His next of kin. Sign here.”

The blonde woman signed, and Dr. Walchek signed as well. Then he reached over to a big metal box next to the bed, and he pushed a button.

#

My vision swirled and spun as I felt myself pulled backwards into the corridor and back to the open auditorium door. As soon as I was through it, though, I was back in my seat. This time I wore only a hospital gown, with nothing underneath. I felt the cold plastic chair on my ass.

Professor Moorehead was once again looking at me, this time pointing a long, bony finger. “Mr. Hudson.”

The blonde in front of me turned, and Wanda said, “Come on, Wayne! You know this. You’ve taught this for ten years.”

“I’ve taught this,” I agreed as I stood before the board. This time I had crossed straight to the front of the room without ever noticing my passage. This time it was a whiteboard, and I had a dry erase marker in my hand. I turned back and looked, and Wanda smiled at me. She held up the white rabbit and waved its paw.

I turned back to the board, uncapped the marker, and started to write.

But the marker… Like half the dry erase markers I had ever used, this one was more dry thananything. The fine ink faded faster than I could write. By the time I had finished five lines of proof, the first line was already gone.

“You can do it, Wayne!” Wanda called. “It’s just logic. You know this.”

Just logic… I should know this… Damn it, if I were conscious, I would know this!

But I didn’t. I wasn’t conscious. Logic had left me. “It’s impossible,” I said.

To my right, someone cleared his throat. I turned and looked. A short little man in a great big hat sat on a low stool. “Only if you believe it is.”

I stared at the little man, the big bushy eyebrows, and the tufts of hair sticking out from under the hat. “Who are you?”

“I am the one who is telling you that you are conscious. You. Are. Conscious. You just have to decide that you are.”

“This isn’t conscious!” I objected. “This isn’t what consciousness means.”

A tall egg with a face in its middle stood on its spindly legs behind the man in the hat. “When I use a word, it means just what I want choose it to mean – neither more nor less. And the same goes for you. Can’t you understand that you’re conscious?”

“I’m not! At this rate, I can never be.”

“You can,” Wanda said. I looked up, and the big screen TV from the visitor lounge was right behind her. She was… dancing in front of it, like when we’d gone to the… I couldn’t remember, but… She was dancing?

She was. The Police were just finishing a video behind her, something about… dadaism, wasn’t it? I couldn’t remember, but it was a catchy tune.

Then the Police ended, and Supertramp began, with a strange, ripping rhythm like a stick on stair posts. Wanda danced her way forward through the crowd and took my hands. “Remember this, Wayne? You’re more than your research. Remember all the times you sang this to me in the middle of the night? This was your song, your battle cry: you’re not just the logical man, you’re more.”

More. I couldn’t remember the words, and I couldn’t make them out from the music, but I remembered the feeling. There was more to my life than logic.

I took Wanda’s hands, and we started to dance, with the white rabbit bouncing up and down around our feet. It sang, “You’re late, you’re late! You’re going to be late! If you don’t solve this problem, you’re going to be the late Doctor Hudson.”

I paused, and I picked up the rabbit. “No.” I stroked its ears. “There’s more than to the world than mathematics. The Halting Problem is like spherical cows, an abstraction that can’t happen in the real world. It gives us a way to think about problems, but it’s not a problem you solve yourself. It’s unsolvable, and it’s also immaterial. I don’t need to solve it to be conscious. I can leave the logic behind, and embrace the life. As Yogi said…”

#

I lay in the bed, eyes fluttering open. My forehead ached just as bad as I remembered it, but I didn’t care. Wanda was –

“Doctor! He’s awake!”

Dr. Walchek laughed. “I can see that on my instruments.”

“Screw your instruments, he spoke! Look at his eyes! Wayne –”

“Carefully, Mrs. Hudson. He still has a lot of injuries.” Then Dr. Walchek turned to me. “So did you solve your problem?”

I tried to smile, but my face felt taped into place. I could barely move enough to talk. “I solved… a more important problem. All programs halt eventually. It’s not a practical problem. Yogi…”

Wanda nodded. “You said something about Yogi Bear.”

“No, Yogi Berra,” I corrected. “And it wasn’t really him who said it. It was van de Snepscheut: ‘In theory, there is no difference between theory and practice. In practice, there is.’ The Halting Problem is just an exercise in theory.” I looked into Wanda’s eyes. “This is my reality.”