If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have?
Note that “C implementation” has a technical meaning: it is a particular instantiation of the C programming language specification where implementation-defined behavior is documented. A C implementation doesn't have to be able to run on an actual computer. It does have to implement the whole language, including every object having a bit-string representation and types having an implementation-defined size.
For the purpose of this question, there is no external storage. The only input/output you may perform is
getchar (to read the program input) and
putchar (to write the program output). Also any program that invokes undefined behavior is invalid: a valid program must have its behavior defined by the C specification plus the implementation's description of implementation-defined behaviors listed in appendix J (for C99). Note that calling library functions that are not mentioned in the standard is undefined behavior.
My initial reaction was that a C implementation is nothing more than a finite automaton, because it has a limit on the amount of addressable memory (you can't address more than
sizeof(char*) * CHAR_BIT bits of storage, since distinct memory addresses must have distinct bit patterns when stored in a byte pointer).
However I think an implementation can do more than this. As far as I can tell, the standard imposes no limit on the depth of recursion. So you can make as many recursive function calls as you like, only all but a finite number of calls must use non-addressable (
register) arguments. Thus a C implementation that allows arbitrary recursion and has no limit on the number of
register objects can encode deterministic pushdown automata.
Is this correct? Can you find a more powerful C implementation? Does a Turing-complete C implementation exist?