The reason is precisely that C cannot "address an unlimited amount of memory", even if an unlimited amount were available. For more information, see:
https://cs.stackexchange.com/questions/60965/is-c-actually-t...
This is in contrast to languages such as Lisp and Prolog: Conceptually, they can reason about arbitrarily large structures such as lists and terms, and can faithfully model any Turing machine.
That, by itself, though gets us only as far as Push Down Automaton (PDA), not Universal Turing Machine.
If we regard the stack as the machine's tape, the problem is that the tape gets erased when the machine rewinds (terminations of scopes obliterate local variables).
The C language also describes an I/O facility: streams. Streams have no inherent bound on their length. If the functions `fgetpos` and `fsetpos` are not used, but only relative positioning, then the stdio stream gives us a tape that is infinite, in terms of language semantics.
If we use streams as an oracle, then we can represent an unbounded tape, and C together with such streams let us model any Turing machine. However, this is not sufficient to prove that C is Turing-complete: To show that (in this context), one has to express also the semantics of such streams within C! It is at this point that the mentioned limitation manifests itself with this approach.
C also has declarations and for loops. If you use them to build your Universal Turing Machine, why doesn't the same objection apply to those features? I mean: "but you're not expressing declarations or for loops in C, you're just invoking these ready-made feature by their convenient, ready-made syntax!"
This assumes facilities that are not prescribed by the C standard though, such as a data structure whose semantics cannot be expressed in C in general. This is a rather striking difference to other constructs such as declarations and for loops: If pressed, we could express their semantics within C while relying exclusively on features that are prescribed by the standard.
How to specify such a system with C remains unsolved though, unless you assume its existence and availability via streams in the first place. This is in contrast to the other languages I mentioned, where you can specify the semantics of an unbounded storage system via built-in mechanisms and data structures of these languages.
That's given by a conforming, hosted implementation of ISO C (the usual kind). You seem to have been writing about freestanding implementations. We are then severely restricted; there might not be a malloc.
C99 4. Conformance ¶6: "The two forms of conforming implementation are hosted and freestanding. A conforming hosted implementation shall accept any strictly conforming program. A conforming freestanding implementation shall accept any strictly conforming program that does not use complex types and in which the use of the features specified in the library clause (clause 7) is confined to the contents of the standard headers <float.h>, <iso646.h>, <limits.h>, <stdarg.h>, <stdbool.h>, <stddef.h>, and <stdint.h>."
If we are talking hosted, then <stdio.h> streams have to be present as a required feature.
> you can specify the semantics of an unbounded storage system via built-in mechanisms and data structures of these languages.
Which language states that programs must be successfully processed by an implementation, regardless of the resources that they require? The next cons call in your Lisp image could fail. That's no different from a stream-related resource problem.
The thought experiment behind "can this programming language express Turing computation" requires us to imagine, for all languages, that the resource constraints don't exist. The question is whether there are some limitations in the language semantics which cannot be thus hand-waved away. Freestanding C (without streams) has those limitations in the abstract semantics; hosted C doesn't. The abstract semantics of streams is available, and if we imagine that to be free of platform-related resource limitation, then we are in the same league as the other languages that we have imagined to be free of platform-related resource limitations.
#deathtoturingmachines
> Some people might wonder “why Turing machines,” as opposed to a more reasonable programming language like C or Python. Well, first of all, we needed a language that could address an unlimited amount of memory. Also, the BB function is traditionally defined in terms of Turing machines. But the most important issue is that we wanted there to be no suspicion whatsoever that our choice of programming language was artificially helping to make our machine small. And hopefully everyone can agree that one-tape, two-symbol Turing machines aren’t designed for anyone’s convenience!