Re:Subtleties of the ANSI/ISO C standard [pdf]
by saurik on Wednesday December 23, 2015 @12:26AM
(#10782128)
> 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.
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.