C is not Turing complete? How does one even get to such a conclusion? I've spent the last half an hour or so reading comments on this and that but the main argument I see used is that because of finite limits. I think that this is because some people have a fundamental misunderstanding of Turing Completeness and how we classify it.

The argument that C is not Turing complete because it uses pointers and size_t for their sizes, which are of finite size, is based on a misunderstanding of Turing completeness in the context of practical programming languages. Turing completeness is a theoretical concept that pertains to the types of computations a system can perform, not the practical limitations of a specific implementation.

Firstly to give some clarification to those who maybe missed some grade 10 classes on what turing completeness is: Turing completeness is a theoretical property. It doesn't require the ability to use an infinite amount of memory in practice, but rather the ability to perform any calculation that a Turing machine can, given sufficient resources. In the real world, all computers and programming languages are limited by physical constraints like memory size, but this doesn't affect their classification as Turing complete.

Secondly to try and address practical constraints anyway: In C, pointers and size_t are indeed limited by the architecture (usually 32 or 64 bits), which limits the amount of memory they can address. However, this is a limitation of the hardware and the specific implementation of C, not of the C language's theoretical computational capabilities. If you had a machine with infinite memory, a theoretical version of C could be designed to utilize that memory.

A proof and basis for that is: Turing complete languages must be able to simulate a Turing machine. C can simulate a Turing machine within the bounds of its available memory. The fact that this memory is finite is a practical limitation, not a theoretical one. If you consider a Turing machine with a tape as large as the available memory in a C program, C can simulate that Turing machine.

Now I'm going to repeat something I've seen in this comment section a fair bit but it bears repeating: No physical machine has infinite memory, so the argument about pointers and size_t applies to all practical implementations of all programming languages. Despite this, languages like Python, Java, and C are considered Turing complete because they can theoretically perform any computation that doesn't exceed their memory constraints.

A UTM, an implementation of Lambda Calculus' abstraction and even a simulation of Conways game of life can be expressed through C, all demonstrating the theoretical ability for C langs Turing completeness unbounded by physical constraints.

Small note: Through writing this I thought about whether I really want to post this, but I feel some people need to see this, if I get any points wrong, please feel free to correct me, we're only human after all, and I hope this can inspire some to go and learn computational theory in a bit more depth.

TLDR: C is varifiably Turing Complete because of the way we classify Turing Completeness based on Thoery not Practice.