On having sufficient complexity to allow for arbitrary computation
September 13, 2019 10:34 AM   Subscribe

Surprisingly Turing-Complete: A catalogue of software constructs, languages, or APIs which are unexpectedly Turing-complete; implications for security and reliability
posted by cortex (19 comments total) 34 users marked this as a favorite
Always wanted to write a C compiler in sendmail.cf.
posted by sammyo at 11:22 AM on September 13, 2019 [5 favorites]

sammyo: I'm pretty sure the "best" way to do that would be to write a c compiler that outputs sendmail.cf, and then just build it with itself.
posted by aubilenon at 11:25 AM on September 13, 2019 [5 favorites]

If I were contemplating doing that, the first path I'd investigate is writing an LLVM backend that emits Sendmail config. Because emscripten exists.
posted by flabdablet at 11:38 AM on September 13, 2019 [4 favorites]

Metafilter: Surprisingly Turing-Complete.
posted by Naberius at 11:49 AM on September 13, 2019 [7 favorites]

Once you see a one instruction computer and/or contemplate Peano arithmetic you see how frighteningly little it takes to support general-purpose computing.

I got my first introduction to this in college where we were "blessed" with a Honeywell mainframe running GCOS, hosting the time-sharing system TSS. TSS was unlike UNIX in about as many ways as you can imagine but there had been some common inspiration and the command-line interpreter, as in UNIX, was an ordinary user program. So it was possible to write your own "shell" if you desired.

A few of us got frustrated with the default command line interpreter and decided to write our own to support a few simple things like simple substitution macros and, IIRC, environment-variable substitution. It didn't go much further than that at first.

Then one of us noticed you could implement default parameters using a trick where a substituted unquoted empty parameter didn't parse as a parameter position, so the next parameter fell into that slot. You could use that, through some gymnastics, to implement default parameters.

Later one of us noticed that you could default the command position so that you could implement a form of branching by selecting one command or another depending on the presence or absence of an argument. At that point we were off to the races, implementing a lot of complex logic in marcos that the original design of the language wasn't envisioned to support. For instance, you could count using what we called "stomps." A series of, say, three "X" parameters followed by a "" parameter could represent three. We finally recognized a useful pattern that was similar to currying and that gave us a tool to program some fairly complex logic.

Eventually, it became clear that some of the things that could be done by cleverness and trickery should be directly supported in the language, so we added those things, opening up new trickery to be discovered. Wash, rinse, repeat. Soon we realized that we needed to sit with each version a while to discover what was possible and plan the best way forward. From that point we decided we'd meet on--and only on--Friday the 13th over pizza and beer to discuss and decide new features and then, IIRC, nobody slept until it was implemented and released.

You'd think such a process would evolve into a mess, but in truth it turned out about as well as csh or tcl which... well, you judge.

A very similar thing occurred years later with C++ templates when template metaprogramming was discovered (then pushed to undrempt-of frontiers by Andrei Alexandrescu, a mad genius who matured into a sane genius and whose contributions to C++ have probably saved it.) The language is now catching up to metaprogramming by adding (somewhat more) straightforward ways to do metaprogramming while also expanding the power of templates to do things you could almost but not quite do with metaprogramming alone.

You can imagine a world where the inherent power of the notations was recognized earlier and designed more consciously. But who knows? That might have lead to something more like CMake rather than, say, tcl or lambda calculus!
posted by sjswitzer at 12:21 PM on September 13, 2019 [23 favorites]

Ich finde, die Spracherkennung von Künstlicher Intelligenz sollte geprüft werden, ob sie auch ostdeutsche Dialekte versteht.

Der sogenannte Thüring-Test.
posted by Wolfdog at 12:36 PM on September 13, 2019 [10 favorites]

Surprisingly not Turing complete should also be a category. I’ve met some people I suspect belong there.

Metafilter: Surprisingly Turing-Complete

Is it?
posted by qxntpqbbbqxl at 12:37 PM on September 13, 2019 [4 favorites]

As for CSS turning machines requiring clicks... maybe not? I've seen pages where mouseover-related events changed layouts to produce new mouseover events which lead to rendering loops. Maybe that's a bug in the CSS implementation; if so it's surprisingly common. But it should be possible in those implementations to drive a CSS event cascade by placing the mouse just-so and then... no clicks needed. Any click-driven state machine should work equally well that way, I would think.
posted by sjswitzer at 12:47 PM on September 13, 2019 [1 favorite]

> Metafilter: Surprisingly Turing-Complete

Is it?

The megathreads eventually became nearly deterministic but undecidable, so... maybe? Anyway, the halting problem was never resolved.
posted by sjswitzer at 12:51 PM on September 13, 2019 [9 favorites]

Metafilter: Surprisingly Turing-Complete

Is it?

..and can it run Doom?
posted by AzraelBrown at 1:22 PM on September 13, 2019 [2 favorites]

The story of Blizzard implementing an emulation layer to preserve custom starcraft levels that exploited a buffer overflow is quite something PDF of a talk about it.
posted by vibratory manner of working at 2:16 PM on September 13, 2019 [6 favorites]

> As for CSS turning machines requiring clicks... maybe not? I've seen pages where mouseover-related events changed layouts to produce new mouseover events which lead to rendering loops.

I thought similarly but I figured the author meant "click" as a placeholder for user-instigated events generally to avoid getting derailed by the details within a survey article that barely had room for some of the far weirder shit going on.
posted by ardgedee at 3:32 PM on September 13, 2019

On the security implications, I think of every security breach as a conflict between the model of reality of the hacker and the model of the implementer. I often reflect on a philosopher I knew that described authentication as an attempt to mechanically answer the question "who are you, really?".

The question comes, what happens if we decide that everything worthwhile is complex enough to be exploitable? Do we defend the "dumb zone" where we're safe to execute untrusted code or do we place security barriers and allow anarchy within?
posted by Wrinkled Stumpskin at 4:39 PM on September 13, 2019

posted by aleph at 6:41 PM on September 13, 2019 [1 favorite]

The product I work on is surprisingly turing complete! It is absolutely not intended as a general purpose programming environment, but you can simulate all sorts of things through conditional stuff and workflows. It's a much smaller problem but I recently implemented the Snake game inside the platform, which turned out to be shockingly easy.
posted by OverlappingElvis at 7:04 PM on September 13, 2019

Baba is surprisingly Turing Complete!
posted by q*ben at 8:25 PM on September 13, 2019

From an infosec perspective, this goes into the territory of "weird machines", which the link does talk about. This paper by the always amazing halvar flake is a great attempt at formalizing what weird machines are. Also see here.
posted by destrius at 9:08 AM on September 14, 2019 [2 favorites]

Human visual illusions - huh, so that's what SCPs memetic attacks came from. Code that executes when you look at it.
posted by Old'n'Busted at 6:46 PM on September 14, 2019

Honestly I was not at all surprised when it turned out that Baba is You is Turing complete. It’s a grid-based system with a ruleset a lot more complex than Life, it would be surprising if it was Turing-incomplete.
posted by egypturnash at 8:52 PM on September 14, 2019 [3 favorites]

« Older Restrictions in Canada's assisted-dying laws...   |   Edited By: Women Film Editors Newer »

This thread has been archived and is closed to new comments