The %n functionality also makes printf accidentally Turing-complete even with a well-formed set of arguments. A game of tic-tac-toe written in the format string is a winner of the 27th IOCCC.
- sez wiki.
A not so fun fact:
Because the %n format is inherently insecure, it's disabled by default.
>The %n functionality also makes printf accidentally Turing-complete
No it doesn't. Printf has no way to loop so it's not Turing complete. Even if you did what the IOCCC entry did with putting it into a loop it still wouldn't be Turing complete as it would not have an infinite memory.
Nothing real is "Turing complete" if it requires infinite memory. That's a property only abstract machines can have. In common parlance, something is Turing complete if it can compute arbitrary programs that can be computed with M bits of memory, where M is arbitrary but finite.
I'd say they're Turing complete (in common parlance) if they can reasonably viewed as a Turing-complete system that's been hobbled with an arbitrary memory limitation. FSAs generally can't be viewed this way as you can't just "add more memory" to an FSA. By way of contrast, consider a pushdown automaton with two stacks. While any physically real implementation of such a device will necessarily have some kind of limit on the size of the stacks, you can easily see how the device would behave if this limit were somehow removed.
It's definitely a bit fuzzy. I'm sure lots of philosophy papers have been written on when exactly it is or isn't appropriate to consider a finite computational system as a finite approximation to a Turing-complete system. In realistic everyday cases, however, it's usually clear enough what should and shouldn't count as such.
Yes, but it also changes the state transition logic. You can't just 'add 100 more states' to an FSA in the same way that you can 'add 100 more stack slots' to a bounded pushdown automaton.
As I said previously, these are somewhat fuzzy distinctions, and I'm not saying that they're easy to make mathematically precise. They do however seem clear enough in most cases of practical interest. There are many real-world computing systems that would be Turing-complete if they had unbounded memory. There are others that are not Turing-complete for more fundamental reasons than memory limitations. Again, I acknowledge that 'more fundamental' is not a mathematically precise concept.
Well, I'm pretty sure all existing digital computers are finite state automata, so they are not, strictly speaking, Turing complete. But that doesn't make any sense.
Strictly speaking there are essentially no programming languages that are even theoretically Turing-complete because they can only address a bounded amount of memory. For example, in C `sizeof(void*)` must be a well-defined, finite integer. But that definition is not useful in practical use.
Even if that was true, any definition of Turing completeness that includes JavaScript and excludes C is worse than useless in practice. It's useless for communication, it's useless for education, it's useless for reasoning about capabilities. There's simply no place for such a definition in a civilized society.
Turing machines themselves are a useless concept in our society. Since C is lower level and tied more to the physical hardware it makes sense that it is not Turing complete because Turing machines are not applicable to the real world. Computers do not work anything like an infinite tape. I've never seen a practical program have to implement a Turing machine.
The %n functionality also makes printf accidentally Turing-complete even with a well-formed set of arguments. A game of tic-tac-toe written in the format string is a winner of the 27th IOCCC.
- sez wiki.
A not so fun fact:
Because the %n format is inherently insecure, it's disabled by default.
- MSVC reference.