Tic-Tac-Toe Implemented In Single Call To Printf()

[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.

33 thoughts on “Tic-Tac-Toe Implemented In Single Call To Printf()

  1. 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.

      1. 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.

        1. “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^)

  2. 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().

  3. 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.

      1. 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().

          1. 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.

  4. 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

  5. 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.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.