3 ms·

There are so many things wrong with this paper, and nearly all of them have to do with their "proof" that C is not Turing complete. First off, they say that C

There are so many things wrong with this paper, and nearly all of them have to do with their "proof" that C is not Turing complete. First off, they say that C isn't complete because its functions for reading/writing files are "bounded". Since most other programming languages are really just implemented in C, wouldn't that mean that either ALL programming languages aren't Turing complete, or that C is? Secondly, they mention that programming languages that have "bignum" types get around the "bounded" memory problem (because you can access "infinite" memory). But you can implement a bignum in C... I hope this is a joke.

saurik 11y ago
> Since most other programming languages are really just implemented in C, wouldn't that mean that either ALL programming languages aren't Turing complete, or that C is? No: it means that the imperfect emulation of those programming languages, as implemented in C, will fail to be Turing complete. Put another way, there are programs that are valid Haskell programs that can be proved by the rules of Haskell to halt on certain inputs and generate particular results, which will not be able to execute as the C emulator will run out of state in which to perform the simulation. The interesting point to make here is that it isn't just that C is being limited by the real world constraints of hardware, but that C is itself limited as if it were hardware. That said, this was always an obvious result to anyone who ever bothered asking the question and understands the formalisms, so I am not certain of the contribution of this paper ;P.
wuch 11y ago
What authors point out is not trivial observation that programs are running on finite-memory machines and thus cannot be Turing complete. What they do point out is that even if C programs have been running on infinite-memory machines the memory accessible to C programs is still bounded. In general I would agree with authors on this point as long as we exclude external storage. They also hint that, while it would be trivial to provide interface to infinite memory tape, the standardized part of file I/O does not seem to do that. They claim that it is prohibited by bounded return value of ftell. I would disagree, because ftell may return an error value in this scenario as well. Moreover to access infinite tape you don't even need ftell, relative movement provided fseek suffices.

saurik 11y ago

> Since most other programming languages are really just implemented in C, wouldn't that mean that either ALL programming languages aren't Turing complete, or that C is? No: it means that the imperfect emulation of those programming languages, as implemented in C, will fail to be Turing complete. Put another way, there are programs that are valid Haskell programs that can be proved by the rules of Haskell to halt on certain inputs and generate particular results, which will not be able to execute as the C emulator will run out of state in which to perform the simulation. The interesting point to make here is that it isn't just that C is being limited by the real world constraints of hardware, but that C is itself limited as if it were hardware. That said, this was always an obvious result to anyone who ever bothered asking the question and understands the formalisms, so I am not certain of the contribution of this paper ;P.

wuch 11y ago

What authors point out is not trivial observation that programs are running on finite-memory machines and thus cannot be Turing complete. What they do point out is that even if C programs have been running on infinite-memory machines the memory accessible to C programs is still bounded. In general I would agree with authors on this point as long as we exclude external storage. They also hint that, while it would be trivial to provide interface to infinite memory tape, the standardized part of file I/O does not seem to do that. They claim that it is prohibited by bounded return value of ftell. I would disagree, because ftell may return an error value in this scenario as well. Moreover to access infinite tape you don't even need ftell, relative movement provided fseek suffices.