4 ms·
This question seem to be applying a theoretical definition of Turing-completeness (with infinite memory) to a practical implementation of C (with finite integer
by omoikane 2y ago
This question seem to be applying a theoretical definition of Turing-completeness (with infinite memory) to a practical implementation of C (with finite integer sizes and finite addressable memory). This framing doesn't seem consistent.
Either a theoretical definition of C should be used (where integers can be arbitrarily large), or a practical definition of Turing-completeness should be used (where some implementation of a finite computational device is possible), such that it's the same theoretical or practical consideration on both sides of the comparison.
- sapiogram 2y agoNo, the question is definitely applying a theoretical definition of C. The problem is that pointers are required to have a finite (but arbitrary) length, meaning addressable memory is also finite.
- lucianbr 2y agoThis definition of Turing-completeness is useless, as nothing in the universe is infinite. Well, maybe the definition can be used for some Hilbert hotel kind-of-stuff, but I would any day prefer a definition that distinguishes some software constructs as Turing-complete and others as not, where C is definitely in the "yes" camp.
- rightbyte 2y agoputc, getc and ungetc should do fine though, right? No need for indexes or pointers.
- jfengel 2y agoYes. This argument applies to RAM as the only storage, for which C99 does indeed have some fixed size. But the space for a stream is arbitrary. I suppose it depends on whether you consider those "part of the language". Which seems like a pretty arbitrary question, but then, we're making a pretty arbitrary point. We already know that real machines always have some finite limitation on memory and thus cannot be Turing machines.