The Escalating Absurdity of Turing Completeness

Description

A four-panel meme using the Vince McMahon reaction format to escalate the concept of Turing completeness in programming tools. The first panel shows the cover of the book 'The C Programming Language' with the text 'Not Turing Complete,' paired with an unimpressed Vince McMahon. The second panel displays the C++ logo with 'Turing-Complete Templates,' and McMahon appears intrigued. The third panel features the Rust language logo with 'Turing-Complete Type System,' showing a much more excited McMahon. The final panel, the punchline, shows the Vim editor logo with 'Turing-Complete Keybindings,' and McMahon's eyes are glowing red with ecstatic energy. The humor comes from the escalating absurdity of where Turing completeness - the ability for a system to perform any computation - is found. It starts with a (jokingly incorrect) baseline for C, moves to the known-but-esoteric feature of C++ templates, then to the powerful Rust type system, and culminates in the hyperbolic joke that even Vim's complex keybinding system is a computational environment, a nod to the editor's legendary power and complexity

Common Tags

Cpp Rust CSFundamentals CFamilyLanguages LanguageComparison TextEditors EditorWars

Comments

Anonymous ★ Top Pick C++ templates let you compute at compile time. Rust's type system lets you prove theorems at compile time. Vim keybindings let you accidentally summon a demon at edit time

Anonymous ★ Top Pick

C++ templates let you compute at compile time. Rust's type system lets you prove theorems at compile time. Vim keybindings let you accidentally summon a demon at edit time
Anonymous

We’ve made templates, type systems, and even keybindings Turing-complete - now the only thing that never halts is the cloud bill for the compile farm trying to prove it
Anonymous

We've gone from "undefined behavior is a feature" to "my text editor can compute the halting problem if I just remember the right chord progression."
Anonymous

The real plot twist? Discovering your build system's YAML configuration is also Turing-complete, which explains why your CI pipeline can solve the halting problem but still can't figure out why it randomly fails on Tuesdays
Anonymous

Modern stack: compute in C++ templates, prove it in Rust’s types, and deploy via Vim keystrokes - the only undecidable part is the requirements
Anonymous

C++ templates were the warning shot; VSCode keybindings prove even your keyboard needs dependent types to halt
Anonymous

Turing completeness always migrates to wherever code review can’t see it - first templates, then trait bounds, and eventually your vimrc; at this point :q! is basically undecidable
@mxkrsv 2y

How the hell C can be Turing incomplete, go have a sleep
@lord_desecrator 2y

This is an argument about the specification of C, not any particular implementation. The fact that no real machine has unbounded memory is totally irrelevant
1. @chupasaurus 2y
  
  The reason why ISO C isn't Turing-complete is precisely the limit of addressable space. You can write another language in C which handles memory differently.
  
  @purplesyringa 2y
  
  Well, no, you can't write an interpreter in C and hope it has access to unlimited space, because it's still subject to C memory model
  
  @sylfn 2y
  
  asm(...) invented in
  
  @chupasaurus 2y
  
  you can make a different memory management system via loopholes, but you have to rewrite every single piece of code to use it.
  
  @purplesyringa 2y
  
  like, how?
  
  @CcxCZ 2y
  
  Practicality doesn't matter. It's just wankery about the specifics of language definition.
  
  @CcxCZ 2y
  
  I'm fairly sure you can implement UTM or unbounded version of brainfuck using fread()/fwrite() and relative seeks only.
  
  @purplesyringa 2y
  
  I'm pretty sure fread/fwrite is not in the C standard
  
  @callofvoid0 2y
  
  standard c you mean without syscalls?
  
  @purplesyringa 2y
  
  standard C I mean the C as specified by the C standard
  
  @purplesyringa 2y
  
  like, ISO C
  
  @purplesyringa 2y
  
  ANSI C
  
  @CcxCZ 2y
  
  There are no such thing as a syscall in C standard, that's implementation thing. But it does have a standard library. And that defines some OS interfaces including file access.
  
  @purplesyringa 2y
  
  huh, seems like you're right. I thought files were only defined in POSIX
  
  @purplesyringa 2y
  
  does... does that mean free-standing C is not, strictly speaking, C?
  
  @purplesyringa 2y
  
  also, i don't know why i'm stuttering.
  
  @CcxCZ 2y
  
  I guess? Speaking of that, there are loads of C implementations with paged memory access.
  
  @CcxCZ 2y
  
  POSIX defines filedescriptor stuff C89 defines FILE* stuff
  
  @callofvoid0 2y
  
  I didn't mean it directly I thought by standard C you mean things without the system/os specific features
  
  @CcxCZ 2y
  
  https://port70.net/~nsz/c/
  
  @callofvoid0 2y
  
  then how are turing complete languages made?
  
  @purplesyringa 2y
  
  Well, guess what, they aren't :)
  
  @purplesyringa 2y
  
  No Turing-complete implementation of a language exists in the real world.
  
  @L2CacheGay 2y
  
  The C memory model does allow for an infinite amount of memory, even if the memory space is bounded
  
  @L2CacheGay 2y
  
  Volatile accesses allow the same address to effectively reference more than one byte of memory
  
  @L2CacheGay 2y
  
  In fact, you could access as much memory as you want in C from just one address if you hate yourself enough
  
  @callofvoid0 2y
  
  how?
  
  @L2CacheGay 2y
  
  Multibyte control code written to the address selecting the real address followed by the access you wish to make to the same address
  
  @L2CacheGay 2y
  
  Think address/data hwregs but on steroids
  
  @L2CacheGay 2y
  
  More like this
  
  @callofvoid0 2y
  
  like using pointers to pointers ?
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  Create a fake array pointer to wherever you want. You can try to read from it and in normal OSes the kernel should prevent you from reading stuff outside if your app’s allocated memory. Ofc this is a hw feature since BC 300 or something
  
  @L2CacheGay 2y
  
  C != the environment it runs in under an OS
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  If you can run it on hardware in ring0 you can read write wherever you want anyway
@callofvoid0 2y

what do you call turing complete ?
@ZgGPuo8dZef58K6hxxGVj3Z2 2y

Can somebody explain?
1. @CcxCZ 2y
  
  Okay. Let me just make myself some tea first.
2. @CcxCZ 2y
  
  Alan Turing has a bunch of different stuff (deservedly) named after him. One of these is idea of an universal computer. Accompanying that is a proof that given infinite resources every kind of universal computer can emulate any other (that is to say there is a way to mechanically translate the program from one to other). One of such theoretical computer is one he described and which is called Universal Turing Machine. It's not of much use besides that when you implement it in a computational system you prove that that system is universal, or how we'd call it today: Turing-complete. The key part there is that this is all math proofs and hence the theoretically unbounded resources. The one claim above that C is not Turing-complete because the standard defines a datatype that must be able to address all available memory and thus memory must be finite is about difference between the theoretical model with infinite resources and actual implementation — there is no computer with infinite memory. I find that claim rather bogus as the C standard also defines file access API and I'm pretty sure that isn't size-bounded. By the way Brainfuck — the original and most used version does use static memory of IIRC 256 values, so not Turing-complete.
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  Give this guy a raise
  
  @CcxCZ 2y
  
  Too bad, he was killed after that for being gay.
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  I know that and the enigma story of him
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  But I meant you for explaining.
  
  @ZgGPuo8dZef58K6hxxGVj3Z2 2y
  
  Thanks man
@CcxCZ 2y

Yeah, I know.
@chupasaurus 2y

Are you from Redmond? Address space could be backed even by clay tablets.
@chupasaurus 2y

should I remind you that Turing machine is mathematical abstraction?
@chupasaurus 2y

it's not about having infinite storage, it's about the lack of bounds on it. And about bullshit, I might introduce you to COBOL. Yep, that old ugly bastard in case of IBM version isn't limited by the language reference, only by compiler.
@chupasaurus 2y

portability, you don't have to check whether you hit the bound or not inside the code on different systems
@chupasaurus 2y

the word "compiler" flew around your head the same way as "mathematical abstraction"...
@glatavento 2y

OK, C is not turing complete. But what about macros?
1. @callofvoid0 2y
  
  actually the question is who gives a fuck to being turing complete
2. @CcxCZ 2y
  
  Only if fed to itself recursively.
@AmindaEU 2y

I somehow doubt that
1. @AmindaEU 2y
  
  I have a vague impression that he devised the test during last moments of his life, possibly while waiting for the suicide method to take effect

Use J and K for navigation

The Escalating Absurdity of Turing Completeness

Description

Categories

Common Tags

Comments

More like this

Gimli and Legolas Unite: C Dev, C++ Dev, and a Rust Hater

Batman Slaps Robin: C++ Speedup Matters at Billions of Runs

C/C++ Devs No Longer Defend Their Build Systems, Just This Look