Subtleties of the ANSI/ISO C standard [pdf]

Money quote for those checking the comments first:<p>&quot;Furthermore, we argue that the C standard does not allow Turing complete implementations, and that its evaluation semantics does not preserve typing. Finally, we claim that no strictly conforming programs exist. That is, there is no C program for which the standard can guarantee that it will not crash.&quot;

We discussed the Turing completeness of C a while ago on HN ( <a href="https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=4795542" rel="nofollow">https:&#x2F;&#x2F;news.ycombinator.com&#x2F;item?id=4795542</a> ). Also the following was produced around that time:<p><a href="https:&#x2F;&#x2F;tdotc.wordpress.com&#x2F;2012&#x2F;11&#x2F;20&#x2F;on-the-turing-completeness-of-c-part-2&#x2F;" rel="nofollow">https:&#x2F;&#x2F;tdotc.wordpress.com&#x2F;2012&#x2F;11&#x2F;20&#x2F;on-the-turing-complet...</a>

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

As the author points out, the standard does not mention stack overflow at all. From this, the author concludes an implementation that always overflows stack is conforming, therefore no strictly conforming programs exist, therefore all implementations are conforming. More reasonable conclusion is that under the current standard, implementations are not allowed to overflow stack, therefore no bounded storage conforming implementation is possible, and all current implementations are buggy. Is anyone surprised that all current implementations are buggy?<p>It would have been more interesting if the author discussed Microsoft’s solution to this problem, namely __try&#x2F;__except and EXCEPTION_STACK_OVERFLOW, which is actually used by programmers to recover from stack overflow.

tl;dr; Some interesting points about bits of C that are undefined. Some points valid, the other ones appear to be self-panicking unless you&#x27;re heavily in the theorem-proving correctness camp.<p>I remain unconvinced that memcmp of pointer values is at all interesting (viz the pointer normalization dancing acts of the early x86 memory models, ugh).<p>From a working programmer&#x27;s point of view, it&#x27;s useful to know some of the points in the paper; just read the middle third and skim the rest.

Interesting article that exposes some problems of C, that some take for granted or ignore.<p>However the arguing that C is not Turing complete after you take away the IO and limit yourself on an non-abstract machine is silly. C can simulate any Turing machine limited by the same previously mentioned rules and the same holds if you remove those rules for both systems, not just for one.

int read(void); void write(int); void left(void); void right(void);<p>read returns 0 or 1. write only uses the least significant bit.