Maximum computational power of a C implementation

Question

If we go by the book (or any other version of the language specification if you prefer), how much computational power can a C implementation have?

Note that “C implementation” has a technical meaning: it is a particular instantiation of the C programming language specification where implementation-defined behavior is documented. A C implementation doesn't have to be able to run on an actual computer. It does have to implement the whole language, including every object having a bit-string representation and types having an implementation-defined size.

For the purpose of this question, there is no external storage. The only input/output you may perform is getchar (to read the program input) and putchar (to write the program output). Also any program that invokes undefined behavior is invalid: a valid program must have its behavior defined by the C specification plus the implementation's description of implementation-defined behaviors listed in appendix J (for C99). Note that calling library functions that are not mentioned in the standard is undefined behavior.

My initial reaction was that a C implementation is nothing more than a finite automaton, because it has a limit on the amount of addressable memory (you can't address more than sizeof(char*) * CHAR_BIT bits of storage, since distinct memory addresses must have distinct bit patterns when stored in a byte pointer).

However I think an implementation can do more than this. As far as I can tell, the standard imposes no limit on the depth of recursion. So you can make as many recursive function calls as you like, only all but a finite number of calls must use non-addressable (register) arguments. Thus a C implementation that allows arbitrary recursion and has no limit on the number of register objects can encode deterministic pushdown automata.

Is this correct? Can you find a more powerful C implementation? Does a Turing-complete C implementation exist?

Answer 1

As noted in the question, standard C requires that there exists a value UCHAR_MAX such that every variable of type unsigned char will always hold a value between 0 and UCHAR_MAX, inclusive. It further requires that every dynamically-allocated object be represented by a sequence of bytes which is identifiable via pointer of type unsigned char*, and that there be a constant sizeof(unsigned char*) such that every pointer of that type be identifiable by a sequence of sizeof(unsigned char *) values of type unsigned char. The number of objects that can be simultaneously dynamically allocated is thus rigidly limited to $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$. Nothing would prevent a theoretical compiler from assigning the values of those constants so as to support more than $10^{10^{10}}$ objects, but from a theoretical perspective the existence of any bound, no matter how large, means something isn't infinite.

A program could store an unbounded quantity of information on the stack if nothing that is allocated on the stack ever has its address taken; one could thus have a C program that was capable of doing some things which could not be done by any finite automaton of any size. Thus, even though (or perhaps because) access to stack variables is much more limited than access to dynamically-allocated variables, it turns C from being a finite automaton into a push-down automaton.

There is, however, another potential wrinkle: it is required that if a program examines the underlying fixed-length sequences of character values associated with two pointers to different objects, those sequences must be unique. Because there are only $UCHAR\_MAX ^{sizeof(unsigned\ char*)}$ possible sequences of character values, any program that created a number of pointers to distinct objects in excess of that could not comply with the C standard if code ever examined the sequence of characters associated with those pointers. It would be possible in some cases, however, for a compiler to determine that no code was ever going to examine the sequence of characters associated with a pointer. If each "char" was actually capable of holding any finite integer, and the machine's memory was a countably-infinite sequence of integers [given an unlimited-tape Turing machine, one could emulate such a machine although it would be really slow], then it would indeed be possible to make C a Turing-complete language.

Answer 2

With C11's (optional) threading library, it is possible to make a Turing complete implementation given unlimited recursion depth.

Creating a new thread yields a second stack; two stacks are enough for Turing completeness. One stack represents what is to the left of the head, the other stack what is to the right.

Answer 3

I think it is Turing complete: we can write a program that simulates an UTM using this trick (I quickly wrote the code by hand so there are probably some syntax errors ... but I hope there are no (major) errors in the logic :-)

• define a structure that can be used as a double linked list for tape representation

    typdef struct {
      cell_t *pred; // cell on the left
      cell_t *succ; // cell on the right
      int val; // cell value
    } cell_t 

The head will be a pointer to a cell_t structure

• define a structure that can be used to store current state and a flag

    typedef struct {
      int state;
      int flag;
    } info_t 

• then define a single loop function that simulates an Universal TM when the head is between the boundaries of the double linked list; when the head hit a boundary set the flag of the info_t structure (HIT_LEFT, HIT_RIGHT) and return:

void simulate_UTM( cell_t *head, info_t *info) {
  while (true) {
    head->val = UTM_nextsymbol[info->state, head->val]; // write symbol
    info->state = UTM_nextstate[info->state, head->val]; // next state
    if (info->state == HALT_STATE) { // print if accepts and exit program
       putchar( (info->state == ACCEPT_STATE)? '1' : '0' );
       exit(0);
    }
    int move = UTM_nextmove[info->state, head->val];
    if (move == MOVE_LEFT) {
      head = head->pred; // move left
      if (head == NULL) { info->flag = HIT_LEFT; return; }
    } else {
      head = head->succ; // move right
      if (head == NULL) { info->flag = HIT_RIGHT; return; }
    }
  }  // still in the boundary ... go on
}

• then define a recursive function that first calls the simulation UTM routine and then recursively calls itself when the tape needs to be expanded; when the tape needs to be expanded on the top (HIT_RIGHT) no problems, when it needs to be shifted on the bottom (HIT_LEFT) just shift up the values of the cells using the double linked list:

void stacker( cell_t *top, cell_t *bottom, cell_t *head, info_t *info ) {
  simulate_UTM(head, info);
  cell_t newcell;  // the new cell
  newcell.pred = top; // update the double linked list with the new cell
  newcell.succ = NULL;
  top->succ = &newcell;
  newcell.val = EMPTY_SYMBOL;

  switch (info->hit) {
    case HIT_RIGHT :
      stacker( &newcell, bottom, newcell, info);
      break;
    case HIT_BOTTOM :
      cell_t *tmp = newcell;
      while (tmp->pred != NULL) { // shift up values
        tmp->val = tmp->pred->val;
        tmp = tmp->pred;
      }
      tmp->val = EMPTY_SYMBOL;
      stacker( &newcell, bottom, bottom, info);
      break;
  }
}

• the initial tape can be filled with a simple recursive function that builds the double linked list and then call the stacker function when it reads the last symbol of the input tape (using readchar)

void init_tape(cell_t *top, cell_t *bottom, info_t *info) {
  cell_t newcell;
  int c = readchar();
  if (c == END_OF_INPUT) stacker(&top, bottom, bottom, info); // no more symbols, start
  newcell.pred = top;
  if (top != NULL) top.succ = &newcell; else bottom = &newcell;
  init_tape( &newcell, bottom, info);
}

EDIT: after thinking a little bit about it, there is a problem with the pointers ...

if every call of the recursive function stacker can mantain a valid pointer to a variable defined locally in the caller then everything is fine; otherwise my algorithm cannot mantain a valid double-linked list on the unlimited recursion (and in this case a don't see a way to use recursion to simulate an unlimited random-access storage).

Answer 4

As long as you have an unbounded call-stack size you can encode your tape on the call-stack, and random-access it by rewinding the stack-pointer without returning from the function-calls.

EdIT: If you can only use the ram, which is finite, this construction does not work anymore, so see below.

However it is highly questionable why your stack can be infinite but the intrinsic ram is not. So actually I would say you do not even can recognise all regular languages, as the number of states is bounded (if you do not count the stack-rewind trick to exploit the infinite stack).

I would even speculate that the number of languages you can recognise is finite (even if languages themselves can be infinite, e.g. a* is okay, but b^k only works for a finite number of ks).

EDIT: This is not true, as you can encode the current state in extra functions, so you can truly recognise ALL regular languages.

You can most likely get all Type-2 languages for the same reason, but I'm not sure if you can manage to put both, the state and the stack-constent on the call-stack. But on a general note, you can effectively forget about the ram, as you can always scale the size of the automaton so your alphabet exceeds the capacity of the ram. So if you could simulate a TM with only a stack, Type-2 would equal Type-0, wouldn't it?

Answer 5

I thought about this once, and decided to try implementing a non-context-free language using the expected semantics; the key part of the implementation is the following function:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

Then calling read_triple on a null pointer will return only if the input consists of the non-context-free language $\{a^n b^n c^n\}$. The functions read_a, read_b, and read_c will return TRUE if the specified character is read, and FALSE otherwise. And the function reject terminates the computation with a failure.

At least, I think this works. It may be that I am making some fundamental mistake, though.

A fixed version:

void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}

Answer 6

Along the lines of @supercat's answer:

The claims of incompleteness of C seems to be centered around that distinct objects should have distinct addresses, and the set of addresses is assumed to be finite. As @supercat writes

As noted in the question, standard C requires that there exists a value UCHAR_MAX such that every variable of type unsigned char will always hold a value between 0 and UCHAR_MAX, inclusive. It further requires that every dynamically-allocated object be represented by a sequence of bytes which is identifiable via pointer of type unsigned char*, and that there be a constant sizeof(unsigned char*) such that every pointer of that type be identifiable by a sequence of sizeof(unsigned char *) values of type unsigned char.

I'm wondering if C allows us to operate ordinals and infinite sequences of bytes. If so, we can take the set of unsigned char* pointers to be $\mathbb{N}$ and the set of unsigned chars to be $\{0, 1\}$ just for simplicity. Then we should define sizeof(unsigned char*), s.t. cardinality the set $\{0, 1\}^{\operatorname{sizeof}(\mathit{unsigned\ char*})}$ is not less than cardinality of $\mathbb{N}$. This way, to every pointer we can assigned a sequence of unsigned chars of the appropriate length. This works if define sizeof(unsigned char*) to be $\mathbb{N}$ ($\omega$ if you wish).

At this point, one should check that C standard would indeed allow that.

One small issue in this construction is that not every sequence of unsigned chars denotes a pointer. This may or may not be fine, but can be fixed if needed. But it could also be that the standard would "accidentally" require that byte representations of objects are finite or that some numbers are integer (say, the result of sizeof is always $\in \mathbb Z$) and then we may be out of luck.