C is not Turing-complete

Date
Tags c, programming, semantics
Target Audience C programmers & language lawyers.
Epistemic Status Based on my interpretation of the C11 spec.
Attention Conservation Notice Because of how pointers are defined in the C standard, an isolated C program is equivalent in computational power to a pushdown automata.

A friend told me that C isn’t ac­tu­ally Tur­ing-­com­plete due to the se­mantics of point­ers, so I de­cided to dig through the (C11) spec to find evid­ence for this claim. The two key bits are 6.2.6.1.4 and 6.5.9.5:

Values stored in non-bit-field ob­jects of any other ob­ject type con­sist of n × CHAR_BIT bits, where n is the size of an ob­ject of that type, in bytes. The value may be copied into an ob­ject of type un­signed char [n] (e.g., by memcpy); the res­ulting set of bytes is called the ob­ject rep­res­ent­a­tion of the value. Values stored in bit-fields con­sist of m bits, where m is the size spe­cified for the bit-field. The ob­ject rep­res­ent­a­tion is the set of m bits the bit-field com­prises in the ad­dress­able storage unit holding it. Two values (other than NaNs) with the same ob­ject rep­res­ent­a­tion com­pare equal, but values that com­pare equal may have dif­ferent ob­ject rep­res­ent­a­tions.

The im­portant bit is the use of the def­inite art­icle in the first sen­tence, “where n is the size of an ob­ject of that type”, this means that all types have a size which is known stat­ic­ally.

Two pointers com­pare equal if and only if both are null point­ers, both are pointers to the same ob­ject (in­cluding a pointer to an ob­ject and a su­b­ob­ject at its be­gin­ning) or func­tion, both are pointers to one past the last ele­ment of the same array ob­ject, or one is a pointer to one past the end of one array ob­ject and the other is a pointer to the start of a dif­ferent array ob­ject that hap­pens to im­me­di­ately follow the first array ob­ject in the ad­dress space.

Pointers to dis­tinct ob­jects of the same type1 com­pare un­equal. As pointers are fixed in size, this means that there’s only a fi­nite number of them. You can take a pointer to any ob­ject 2, there­fore there are a fi­nite number of ob­jects that can exist at any one time!

However, C is slightly more in­ter­esting than a fi­nite-state ma­chine. We have one more mech­anism to store val­ues: the re­turn value of a func­tion! For­tu­nately, the C spec doesn’t im­pose a max­imum stack depth3, and so we can in prin­ciple im­ple­ment a push­down auto­mata.

Just an in­ter­esting bit of in­form­a­tion about C, be­cause it’s so common to see state­ments like “be­cause C is Tur­ing-­com­plete…”. Of course, on a real com­puter, nothing is Tur­ing-­com­plete, but C doesn’t even manage it in the­ory.

Ad­dendum: Vir­tual Memory

In a dis­cus­sion about this on Twit­ter, the pos­sib­ility of doing some sort of vir­tual memory shenanigans to make a pointer see dif­ferent things de­pending on its con­text of use came up. I be­lieve that this is pro­hib­ited by the se­mantics of ob­ject life­times (6.2.4.2):

The life­time of an ob­ject is the por­tion of pro­gram ex­e­cu­tion during which storage is guar­an­teed to be re­served for it. An ob­ject ex­ists, has a con­stant ad­dress, and re­tains its last-stored value throughout its life­time. If an ob­ject is re­ferred to out­side of its life­time, the be­ha­vior is un­defined. The value of a pointer be­comes in­de­term­inate when the ob­ject it points to (or just past) reaches the end of its life­time.

The life­time for heap-al­loc­ated ob­jects is from the al­loc­a­tion until the deal­loc­a­tion (7.22.3.1):

The life­time of an al­loc­ated ob­ject ex­tends from the al­loc­a­tion until the deal­loc­a­tion. Each such al­loc­a­tion shall yield a pointer to an ob­ject dis­joint from any other ob­ject.

Ad­dendum 2: Non-Ob­ject In­form­a­tion

I had a fun dis­cus­sion on IRC, where someone ar­gued that the defin­i­tion of pointer equality does not men­tion the ob­ject rep­res­ent­a­tion, there­fore the fixed ob­ject rep­res­ent­a­tion size is ir­rel­ev­ant! There­fore, pointers could have extra in­form­a­tion somehow which is not part of the ob­ject rep­res­ent­a­tion.

It took a while to re­solve, but I be­lieve the final sen­tence of the ob­ject rep­res­ent­a­tion quote and the first clause of the pointer equality quote, to­gether with the fact that pointers are val­ues, re­solves this:

  1. Pointers are val­ues.
  2. Two values (other than NaNs) with the same ob­ject rep­res­ent­a­tion com­pare equal, but values that com­pare equal may have dif­ferent ob­ject rep­res­ent­a­tions.

  3. Points (1) and (2) mean that pointers with the same ob­ject rep­res­ent­a­tion com­pare equal.
  4. Two pointers com­pare equal if and only if…

  5. The “only if” in (4) means that if two pointers com­pare equal, then the rest of the rules ap­ply.
  6. Points (3) and (5) mean that two pointers with the same ob­ject rep­res­ent­a­tion com­pare equal, and there­fore point to the same ob­ject (or are both null point­ers, etc).

This means that there cannot be any fur­ther in­form­a­tion that what is stored in the ob­ject rep­res­ent­a­tion.

In­ter­est­ingly, I be­lieve this for­bids some­thing I ini­tially thought to be the case: I say in a foot­note that dif­ferent types could have dif­ferent heaps. They could, but that doesn’t let you use the same ob­ject rep­res­ent­a­tion for pointers of dif­ferent types!


  1. In­ter­est­ingly, you could have a dis­tinct heap for every type, with over­lap­ping pointer val­ues. And this is totally fine ac­cording to the spec! This doesn’t help you, however, be­cause the number of types is fi­nite: they’re spe­cified in the text of the pro­gram, which is ne­ces­sarily fi­nite.

  2. “The unary & op­er­ator yields the ad­dress of its op­er­and.”, first sen­tence of 6.5.3.2.3.

  3. “Re­cursive func­tion calls shall be per­mit­ted, both dir­ectly and in­dir­ectly through any chain of other func­tion­s.”, 6.5.2.2.11, nothing else is said on the mat­ter.