Turing-like machine

Team Postmortem

A Google Hangout session starts. Four participants appear. The names underneath their images read "Ron", "Tony", "Leslie", and "Barb".

Ron strokes his beard, "Looks like our handler isn't here yet."

"It's no wonder, given the challenges we faced in that last outing," says Tony, as he takes off his hat, wipes his forehead, puts it back on.

Leslie removes his reading glasses and looks up. "I didn't think it was that bad. If only we had used fewer types and less time to tackle that daemon..."

Barb shakes her head. "Let's not start that argument again, Leslie!"

A new, fifth, participant begins to join the Hangout. The profile photo is unusual, insofar as it has a ghostly outline and is indistinct. It is labeled "Robin".

Robin's image appears, vague in its substance. He jumps in. "Thank you for joining me for this debriefing, everyone. I apologize for my lateness; my wifi connection is spotty in the hereafter."

Ron clears his throat as Tony chuckles at the joke.

Robin continues.

"First, thank you, one and all, for your tremendous bravery and cool-headedness last night. Our missions have become more challenging and more frequent with each passing year. Practical advances, such as CPU speeds, desktop parallelism, inexpensive large memory sizes, and commodity cloud computing mean that more and more researchers and hobbyists are encroaching on dangerous territory. In the past, we only needed to worry about a handful of top complexity theorists and programming language researchers, but today any sharp kid with an Athlon can accidentally summon a hellbeast."

"Now it is no longer a question of simply hiding the proof for P=NP and planting misdirections like Ron's excellent work."

"MD4 notwithstanding," says Ron.

Robin nods, responding, "You can't win them all, Ron." He continues, "Our new threat is the growing use of solvers and logical frameworks. It is only a matter of time before a concrete syntax design accidentally triggers an event."

Tony injects, "We had hoped that Don's excellent work, especially with Ronald and Oren, would steer most clear of those dangerous waters."

Robin raises his hand and shrugs slightly, "But now with his publication of a draft of the middle third of Volume 4B..."

"...enormously more programmers are going to begin to deeply understand satisfiability!", finishes Barb.

Leslie grunts. "We can't keep up! Our team grows only by one member every year, and we are starting to lose the old-timers... no offense, Robin."

Robin acknowledges the comment with class, as he always did, and responds, "Indeed, this is the main reason I called you here today. The Agency intends to change our recruitment policy." Many pairs of eyes grow wide in the Hangout. Robin continues, "We intend to use this year's ICFP programming contest to find new operatives. We need more sharp, brave souls with expertise in several areas, particularly cryptography, program reasoning, algorithms, and programming languages, to keep the world safe from the Old Ones and their minions."

Barb looks doubtful. "Do you really think this plan will work?"

Robin shakes his head, "Aleister believes that it is our only hope..."

Introduction

Computational Archeology, or CA for short, is the study of historical hidden digital artifacts. Miskatonic University in Arkham, Massachusetts, USA has several top CA researchers in the "Digital Division" of their Department of Archeology. No one knows their real names, as they all publish under pseudonyms for fear of being identified by Lurkers beyond the Threshold. Bourbaki, Banzai, Cocke, Hopcroft, Backus. The list goes on and on.

To the general public, as well as to many funding agencies, the Digital Division appears laughable—the ancient world clearly did not have advanced computers, and our understanding of the abacus does not require multiple professorships. However, not all findings are suitable for the general public, and many deep digs have revealed terrible truths: many ancient cultures had advanced computational capabilities, but something happened each time computer science was invented. The truth has been carefully obscured, and ancient ameliorative technologies have been carefully cataloged and stored for the day where they will again be crucial to the survival of humanity. Little does the general public know that Stross's yarns are not fiction, but are in fact... fact.

Researchers in the Digital Division have been tasked by an Other Government Agency, or OGA for short, to recruit new operatives to help keep the world safe from the dark threats that live beyond the stars. They have discovered a new representation for ancient protection schemes, called davar, that provides new hope for prolonging humanity's survival. Each davar invocation dampens the impact of a gate or summoning spell, whether generated intentionally by those who worship the Old Ones or unintentionally by those contemplating the finer points of complexity theory. Without the davar, such a spell may at best consume only a high school; at worst, tens of thousands of souls.

Moreover, their new scheme can be farmed out to many spellcasters working in parallel: a kind of computational magical Turk. If they only had a set of algorithms with which to automate the currently laborious process of crafting counter-spells of sufficient strength, they could calm the turbulent computational ether and its fractal eddies and non-Euclidean pools of flesh-eating darkness.

A New Threat

"Google's moves in AI and quantum are getting out of hand!" Director Aleister looks more agitated than he usually did before his second cup of coffee in the morning.

"Indeed, they may stumble upon a Strong AI Golem, and then we'd be in real trouble." Buckaroo looked worried. "Perhaps we should call in the Blue Blaze Irregular strike team out of Galois."

The Director pursed his lips and sighed. "We can't distract them. They're too busy with practical FHE to protect our assets from APTs, both foreign and extraterrestrial."

"That means we need to recruit again. We need a highly visible channel to get the best and the brightest. Our Turing Squad is thin on the ground." Banzai reflected.

"What about the ICFP programming contest?", the Director proffered.

Buckaroo's eyes lit up. "Exactly! Talent with spare time, enthusiasm for hard problems, breadth and depth of knowledge, and most are 10x-ers!" His eyes narrowed. "Kathleen and I go way back. I can charm her into having Galois run next year's contest."

"Excellent!" The Director pointed at Buckaroo's chest and ordered, "Ensure that the contest just looks like a game—we don't want to give too much away. If contestants realized that the fate of the world hung in the balance..."

Buckaroo slowly looked down at the Director's finger and raised his eyebrow. The Director blushed, mumbled something about needing to make a phone call, and slipped out of the office.

A Field Test

John Conway stood in front of a roomful of confused looking young men and women. He was facing away from the class, drawing hexagonal triads and tetrads in different configurations on the blackboard.

"Erm. Excuse me, professor?" One of the students spoke up.

Professor Conway distractedly looked up at the ceiling, then turned to face the students with a look of surprise on his face. "Oh, is it time for lecture then? Good, ok, let's go!"

"Welcome to Defence against the Digital Dark Arts, ladies and gentlemen. My name is John, and I'll be teaching you today about the most powerful means by which we can discover and cast protective spells to keep the planar peace." He turned again, wiped off the board with his already-chalk-covered shirtsleeve, and began to write.

"Russian computer scientists in the 1960s discovered a way to visually encode spells. Traditionally we had always used ancient written languages like Latin, Greek, Aramaic, and Lojban. But higher-dimensional constraints are difficult to encode textually, despite the excellent work of Frege and Dijkstra. Little did we know the encoding was hiding right under our noses... and our honey."

"Bees?", proffered one of the students.

"Bees. Indeed, the Russians discovered that certain species of bees were genetically programmed by powers unknown to encode power phrases in their honeycombs. Transliterating those honeycombs, and their cells' configurations, into digital form was straightforward enough, but they, and we, simply didn't have the computational power to reason about the resulting system."

"It didn't help that the actual problem involved hyperbolic sphere packing." Grigori entered the room with a flourish. "Until Bowen and Radin's excellent practical work in 2002, we had no way to tackle the problem." Perelman grimaced. "And now that the agro-industrial complex has begun to foolishly worship the Old Ones, apiaries are paying the price."

"Moreover," Professor Conway continued, "the Russians needed to farm out the discovery of programs and power phrases to the masses. No 8-bit gamers in the early 80s were capable of playing a video game that involved multiple dimensions. That wouldn't come until titles like Portal and Miegakure became popular."

"Thus the introduction of Tetris to the world," said Professor Perelman in accented English as he turned to the large LCD. It lit up at his command to reveal a clandestine recording of a Tetris championship match. A sign in the shot revealed that it was recorded at the Classic Tetris World Championship at the Portland Retro Gaming Expo in early 2015.

Perelman continued, "Tetris trained generations of gamers to think about computational problems in geometric ways. Now is the time to introduce a new Tetris-like game that directly connects to the multidimensional hexagonal foundations of power phrases, or what we call 'davar' ."

"Initial board configurations are encodings of threats that must be countered. They are discovered by three teams: computational archeologists at Miskatonic, NSA cryptographers decrypting secret communications among worshippers of YogSothoth and the Old Ones on social media..."

Conway snorted, "Trolls!"

Perelman glared at him, "...and, as I was saying before I was interrupted, classical archeologists who have discovered buried mosaics encoding ancient powerful curses."

Conway jumped in, "Encoding the power phrases into game play generates counter-spells. The more power phrases we can intone, and the more powerful they are, the greater our safety." He clicked a mouse attached to the machine projecting the video to reveal an over-the-shoulder closeup of an unshaven young man playing a game that was reminiscent of Tetris, but with hexagonal units marching down the display. "Human players are certainly good at solving the interlocking visual language of this game we call 'Hex' ."

Grigori gave a wry grin. "Note the double meaning, students."

"But they are notoriously bad at solving the geometric configuration challenges and spelling out the power words simultaneously.", Conway emphasized. "Consequently, we must design new algorithms... algorithms that potentially use a combination of classic techniques..."

"...such as dynamic programming, backtracking, Markov models..." injected Professor Perelman.

"...and relatively new research in a plethora of adjacent disciplines, such as genetic programming, learning systems, stochastic simulation, and more."

Professor Perelman began distributing a small stack of papers to the end of each row of students. "Here is the specification of the Hex game and your challenge, should you choose to accept it." He darkly scanned the room.

"The fate of the world is in your hands."

Fin