[Nicholas Carlini] programmed a C implementation of two-player Tic Tac Toe, and he did it in a single call to printf(). The arguments for that single function call get mind-bendingly complex, so it may come as no surprise that it was written for The International Obfuscated C Code Contest (IOCCC).
Most of us are aware that printf() is one of those functions that is considerably more complex under the hood, and capable of far more, than it may appear to be. But did you know that it is capable of Turing-complete computation?
[Nicholas] clearly steps through the theory, so give it a read. In short, a maze of arguments handles the logic of the game while an embedded scanf() reads user input, and printing the game board is always preceded by an escape code to clear the screen.
[Nicholas] is certainly no stranger to in-depth understandings; we’ve seen his work before in demonstrating how to fool speech recognition with hidden commands, including a powerful example showing how two virtually identical-sounding audio files transcribe entirely differently.
i like the license text:
LICENSE
This program is clearly some groundbreaking achievement the likes of which have never been seen before. Therefore, if you would like to use this program in anything, it’s licensed under the GPL v3.
This program also demonstrates why C is also a dangerous memory leaky programming language.
Any sufficiently powerful language is memory leaky.
Honestly, any language can be having unintentional memory leaks. Its all about how different things calls on each other. Something as simple as an “off by one” issue can lead to a program slowly needing more and more memory with each iteration of a loop.
Though, with more complicated programs its easier to get to this point, since there is simply more room for mistakes.
“Honestly, any language can be having unintentional memory leaks.”
Yeah, English can be pretty “leaky” (i.e. vague) though it can be “intentional” as well!
B^)
Assembler tends not leak.
If assembler doesn’t leak, it’s only because people don’t use as much dynamic memory allocation in their typical programs.
Rust wants to have a word with you.
Can you write a C interpreter in Rust ?
If you could, you could do anything in C and not need any of these languages anyway. :)
Apparently, you can: https://github.com/kianenigma/c-interpreter
There are lots of interpreters written in Rust: https://lib.rs/search?q=interpreter
Rust is very much a low level language, very comparable to C. But with loads of protection and safety-nets built into the compiler.
If you can write a full C interpreter in Rust, and you use that interpreter to run a leaky C program, then you have a memory leak in Rust.
Yes, but I forget why
The cause of memory leaks is the programmer not the language
So, it’s the plumber, and not the plumbing?
B^)
The shower head is intentionally leaky.
The language does not cause memory leaks. 101 here
It’s not the language that causes leaks.
You can hurt yourself with a blunt object, but it’s much easier with a knife. C is like sharp knife. Assembly is like scalpel.
But when C is Sharp it is C# which is less likely to cause an injury
If you know how the memory manager works, you can make any language leak.
Modern languages are leaky, just you have buckets under all the leaks and they get emptied out but that costs time.
Any function that accept a function as argument can be Turing complete, because that argument function can implement a complete program and then at its conclusion return a value that please it parent function. So it doesn’t come as a surprise that printf() is Turing complete although it is a stretch to qualify it that way, this is C that is turing complete not printf().
That’s not how this works. The program depends on the format string interpreter used by printf() being sufficiently powerful.
By the way his program is not Turing complete inside printf() as it require an external while(*d) loop to do its work! This control structure must be include inside printf() arguments to consider printf() working as Turing complete.
The while() is only needed because it is interactive. A real Turing Machine can’t be used interactively either.
The expression “Turing complete” means it can execute any computational task including interacting with the user. The demonstration that printf() is turing complete is based on the fact that an array of integers can be switched between 2 states by manipulating printf() arguments. One can configure NOT and OR with it which in theory qualify it as Turing complete. I don’t question that. But i maintain the affirmation that Tic-tac-toe is not Turing complete as it use an outside loop. The fact is that although printf() is in theory Turing complete it would require a huge array simply to design a basic CPU with it. Tic-tac-toe is possible, at least in part, because it can be implemented with a small count of logic gates. Notice also that it require a call to scanf().
No, Turing complete means a system that that can compute every Turing-computable function. See https://en.wikipedia.org/wiki/Turing_completeness
There’s no need for such a system to support interaction. It just needs to be able to compute a function. The original Turing Machine cannot play tic-tac-toe either.
I submitted this point to Mr Carlini an here I quote his answer:
“Yeah, technically you are correct.
We note this in our paper that I based this idea off of: “To achieve full Turing-complete computation, we need a way to loop a format string. This is possible by over-writing the pointer inside printf() that tracks which character in the format string is currently being executed. The attacker is unlucky in that at the time the “%n” format specifier is used, this value is saved in a register on our 64-bit system. However, we identify one point in time in which the attacker can always mount the attack. The printf() function makes calls to puts() for the static components of the string. When this function call is made, all registers are saved to the stack. It turns out that an attacker can overwrite this pointer from within the puts() function. By doing this, the format string can be looped.” (Taken from Section 6.2.1 of this paper.)
The problem with this in practice is it’s not standards compliant, and system-dependent. I wrote this entry for IOCCC which prefers both, so used a loop to make it easier.
This doesn’t bother me too much anyway. Real Turing completeness requires an infinite memory. So no C program on any computer is Turing complete either. It’s all degrees of correctness.
“
Yes, but C programs usually leak memory gradually, while getting some work done as a side effect. A Java program hogs all the memory right away.
Yes, somewhat tongue-in-cheek, but still… ;-P
You can write decent programs in any language. Even in Javascript. It’s not the language, it’s the coder that bogs the memory.
If you stick to static memory allocation at compile time and not mess up your IRQ, then the code can run for years without any memory leaks.
Memory leaks happens when you ask for memory, but not returning it.
No, this is not ‘printf’. This is a extended super-‘printf’ with a zoo of additional non-standard features. The bold claim about ‘printf’ being able of Turing-complete computation made here is invalid. Such entries that rely heavily on non-standard extensions are generally considered lame from IOCCC perspective.
I know that at the time you commented you couldn’t have known but what are you like anyway? Here’s what the judges had to say about this entry:
‘This year’s Best of Show (carlini) is such a novel way of obfuscation that it would be worth of a special mention in the (future) Best of IOCCC list!’
And you call it ‘lame’? Not at all what the judges think!