TL;DR: all C implementations are FSMs (finite state machines, bounded by addressable memory based on wordsize) which are not Turing Complete because of the finite, as Turing machines have infinite tape.
A useful perspective to contrast to this idea that it's not a "real" Turing machine if you don't have infinite tape (and thus, no such machines can ever exist) is the Busy Beaver (perpetual favourite of Hacker News, just use the search at the bottom to find such topics). Some very small beavers are already completely beyond our ability to reason about because they express unsolved problems of mathematics.
the aforementioned comment from TFA:
C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, va_args can be used to implement a pointerless pointer.
Of course, a real implementation of the variadic argument API is probably going to have a pointer somewhere, but in our abstract machine it can be implemented using magic instead.
[1] Whether that copy is meaningfully usable is a different matter, which is why va_copy exists.
One could imagine a memory API with infinite storage, perhaps some sort of null-terminated addresses with no defined upper bound, but it'd be different than that.
You'd need to store it, and our universe is finite, so there isn't enough room.
Much worse the universe despite being finite is already so enormous and growing that you cannot cross it, so it would be impossible to actually perform computation as even if the data exists it can't necessarily ever be moved from where it is to the site of computation - it may get further away instead despite travelling as fast as possible.
Fit on a normal machine c99 runs on.
The second you say "most computations" you stopped talking about Turing Completeness.
Wait until you find out all memory lookups are O(n^0.5) too (assuming a holographic universe)
Only physical "Turing complete" systems. JavaScript, as specified by ECMA, is properly Turing machine; you can express a program which will allocate an arbitrary amount of objects. In the "JavaScript abstract machine", there is no upper limit.
In C, there is necessarily a finite upper limit to the amount of objects allocated, since every object needs a unique address and addresses are represented by finite-bit pointers. That means that the "C abstract machine" as defined by ISO can not even in principle allocate arbitrarily many objects.
(And yes, this all means that any Turing-machine-like systems built in the real world aren't proper Turing machines, since strictly speaking, a Turing machine is a theoretically construct with an infinitely long tape.)
However, in most languages (JavaScript, Python, Java, ...) there's no concept of an object's location in memory as expressed by a finite number of bits. In those languages, you can express programs which will create an ever increasing number of objects. Trying to run that program will eventually cause a crash as you run out of space, but the source code itself encodes a program which would allocate objects with no upper bound.
That's not the case for C. In C, every object has a unique address. That address is encoded in a fixed number of bits. As such, you can't even write source code which allocates objects with no upper bound; the upper bound will always be 2 to the power of the number of bits in a pointer.
You have made an arbitrary causal network between the idea of Rule 110, and its implementation in C++. Its arbitrary, and minds much greater than yours can enjoy and understand this distinction, as does Stephen, and I. See Pages 770ff.
You can compile rule 110 into a Mathemetica notebook, you can output it in x86 assembler. Since they are the same, i.e. they produce the exact outputs, and can determine computability
"Turing completeness is a term in computer science that describes the ability of a system to compute any possible calculation or program, and can be used to describe modern programming languages (Python, C++, etc.). Turing complete describes a programmable system that can solve any computational problem."
Now, how about a little bit of reading?
https://philarchive.org/archive/CASOTC-3
"Virtually all programming languages today are Turing-complete."
It is a finite number and it's a big number, but still finite (and proven).
https://en.wikipedia.org/wiki/Bekenstein_bound
Also the playlist Understanding the Holographic Universe from PBS Space Time https://www.youtube.com/watch?v=qPKj0YnKANw&list=PLsPUh22kYm... and Entropy Explained! https://www.youtube.com/watch?v=nhy4Z_32kQo&list=PLsPUh22kYm...
But the gist is that turing completeness even limited by finite universes is still turing completeness in the most interesting interpretation.
A Turing machine that you implement in C as “the tape is a single array in address space” would be, but that’s not what is required for Turing completeness.
The entire argument about pointer size is facetious - programs have operated over data that is larger than address space for ever, and is not hard to manage.
But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be.
If the real argument is “to be turing complete means that a Turing machine must be able to have infinite state”, then the argument is only technically true, but that’s argument applies equally to every Turing complete system.
> But let’s just go nuts: you can make a Turing machine in C that implements the tape as a stream api that wraps all the cloud storage providers and just pauses until more drives are installed whenever necessary, and you have just as much of a Turing machine as any physical Turing machine could possibly be.
It isn't stupid. The post is not about "real world" implementations. The question was about C99's abstract semantics. As the first answer points out:
> (Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)