28
$\begingroup$

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?

$\endgroup$
  • 4
    $\begingroup$ @Dave: As Gilles explained, it seems that you can have unbounded memory, but no way to directly address it. $\endgroup$ – Jukka Suomela Oct 29 '10 at 18:31
  • 2
    $\begingroup$ From your explanation it sounds like any C implementation can only be programmed to accept languages accepted by deterministic pushdown automata, which are weaker than even context-free languages. This observation however is of little interest in my opinion, as the question is a misapplication of asymptotics. $\endgroup$ – Warren Schudy Oct 29 '10 at 18:53
  • 3
    $\begingroup$ One point to keep in mind is that there are many ways to trigger "implementation-defined behaviour" (or "undefined behaviour"). And in general, an implementation can provide, e.g., library functions that provide functionality that is not defined in the C standard. All of these provide "loopholes" through which you could access, say, a Turing-complete machine. Or even something much stronger, like an oracle that solves the halting problem. A stupid example: the implementation-defined behaviour of signed integer overflows or integer–pointer conversions could let you access such an oracle. $\endgroup$ – Jukka Suomela Oct 29 '10 at 19:00
  • 7
    $\begingroup$ By the way, it might be a good idea to add the tag "recreational" (or whatever we are using for funny puzzles) so that people don't take this too seriously. It's obviously the "wrong question" to ask, but nevertheless I found it amusing and intriguing. :) $\endgroup$ – Jukka Suomela Oct 29 '10 at 19:24
  • 2
    $\begingroup$ @Jukka: Nice idea. For example, overflow by X = write X/3 on the tape and move in direction X%3, underflow = trigger the signal corresponding to the symbol on the tape. It feels a bit like an abuse, but it's definitely in the spirit of my question. Could you write it as an answer? (@others: Not that I want to discourage other such clever suggestions!) $\endgroup$ – Gilles 'SO- stop being evil' Oct 29 '10 at 22:00
8
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ With such a machine, what would sizeof(char) return? $\endgroup$ – TLW Jul 26 '16 at 20:37
  • 1
    $\begingroup$ @TLW: Same as any other machine: 1. The CHAR_BITS and CHAR_MAX macros would be a bit more problematical, though; the Standard wouldn't allow for the concept of types which have no bounds. $\endgroup$ – supercat Jul 26 '16 at 20:51
  • $\begingroup$ Whoops, I meant CHAR_BITS, as you said, sorry. $\endgroup$ – TLW Jul 26 '16 at 21:32
7
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ But Turing machines with a tape infinitely progressing in only one direction are just as powerful as Turing machines with a tape infinitely progressing in two directions. Apart from that, multiple threads can be simulated by a scheduler. Anyways, we do not even require a threading library. $\endgroup$ – xamid Mar 7 at 18:08
3
$\begingroup$

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).

$\endgroup$
  • 3
    $\begingroup$ Every time stacker is called, it creates a new object newcell. This object has an address which is distinct from the address of any other object. So there is a finite maximum to the depth of recursion of stacker (a little under $2^n/s$ where $n$ is the number of bits per pointer and $s=$sizeof(cell_t)). As is the program would invoke undefined behavior when it runs out of “stack”. If you limit the recursion depth, you get a finite automaton, right? $\endgroup$ – Gilles 'SO- stop being evil' Sep 3 '12 at 21:22
  • $\begingroup$ @Gilles: you're right (see my edit); if you limit the recursion depth you get a finite automaton $\endgroup$ – Marzio De Biasi Sep 3 '12 at 21:36
  • $\begingroup$ @MarzioDeBiasi No, he's wrong since he refers to a concrete implementation which the standard does not presuppose. In fact, there is no theoretical limit to recursion depth in C. A choice to use a limited-stack-based implementation does not say anything about theoretical limits of the language. But Turing-completeness is a theoretical limit. $\endgroup$ – xamid Mar 7 at 19:00
0
$\begingroup$

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?

$\endgroup$
  • 5
    $\begingroup$ What is a “stack-pointer”? (Note that the word “stack” does not appear in the C standard.) My question is about C as a class of formal languages, not about C implementations on a computer (which are obviously finite state machines). If you want to access the call stack, you must do it in a way that is provided by the language. For example by taking the address of the function arguments — but any given implementation has only a finite number of addresses, which then limits the depth of recursion. $\endgroup$ – Gilles 'SO- stop being evil' Oct 29 '10 at 22:05
  • $\begingroup$ I've modified my answer to exclude the use of a stack-pointer. $\endgroup$ – bitmask Oct 29 '10 at 22:38
  • 1
    $\begingroup$ I don't understand where you're going at with your revised answer (apart from changing the formulation from computable functions to recognized languages). Since functions have an address too, you do need a large enough implementation to implement any given finite state machine. The question is whether and how a C implementation could do more (say, implement a universal Turing machine) without relying on undefined behavior. $\endgroup$ – Gilles 'SO- stop being evil' Nov 4 '10 at 23:42
0
$\begingroup$

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();
}
$\endgroup$
  • $\begingroup$ Well, not a fundamental mistake, but it = *it should be replaced by it = * (void **) it, as otherwise *it is of type void. $\endgroup$ – Ben Standeven Sep 12 '12 at 2:48
  • $\begingroup$ I would be very surprised if travelling the call stack like that would be defined behavior in C. $\endgroup$ – Radu GRIGore Sep 12 '12 at 7:26
  • $\begingroup$ Oh, this won't work, because the first 'b' causes read_a() to fail and hence triggers a rejection. $\endgroup$ – Ben Standeven Oct 15 '12 at 5:12
  • $\begingroup$ But it is legit to travel the call stack in this fashion, since the C standard says: "For such an object [i.e. one with automatic storage] that does not have a variable length array type, its lifetime extends from entry into the block with which it is associated until execution of that block ends in any way. (Entering an enclosed block or calling a function suspends, but does not end, execution of the current block.) If the block is entered recursively, a new instance of the object is created each time." So each call of read_triple would create a new pointer that can be used in the recursion. $\endgroup$ – Ben Standeven Oct 15 '12 at 5:15
  • 2
    $\begingroup$ @BenStandeven The thing is, if you do that, eventually you'll run out of addresses. If you create an addressable object at each recursive call, then there is a limit to the recursion depth (no more than $2^{\text{CHAR_BIT} \cdot \text{sizeof(char*)}}$. $\endgroup$ – Gilles 'SO- stop being evil' Oct 17 '13 at 17:20
0
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ Many operations on integral types are defined to have a result that is “reduced modulo one more than the maximum value representable in the result type”. How would that work if that maximum is a non-finite ordinal? $\endgroup$ – Gilles 'SO- stop being evil' Nov 25 '16 at 16:03
  • $\begingroup$ @Gilles This is an interesting point. It is indeed not clear what would be the semantics of uintptr_t p = (uintptr_t)sizeof(void*) (putting \omega into something that holds unsigned integers). I do not know. We may get away with defining the result to be 0 (or any other number). $\endgroup$ – Alexey B. Nov 25 '16 at 16:26
  • 1
    $\begingroup$ uintptr_t would have to be infinite too. Mind you, this type is optional — but if you have an infinite number of distinct pointer values then sizeof(void*) must also be infinite, so size_t must be infinite. My objection about reduction modulo isn't so obvious however — it only comes into play if there's an overflow, but if you allow infinite types then they might never overflow. But on the gripping hand, each type has a minimum and maximum values, which as far as I can tell implies that UINT_MAX+1 must overflow. $\endgroup$ – Gilles 'SO- stop being evil' Nov 25 '16 at 16:35
  • $\begingroup$ Also a good point. Indeed, we get a bunch of types (pointers and size_t) that should be ℕ, ℤ, or some construction based on them (for size_t if would be something like ℕ ∪ {ω}). Now, if for some of these types, the standard requires a macro defining the maximum value (PTR_MAX or something like that), things will get hairy. But so far I was only able to fund the requirement of MIN/MAX macros for non-pointer types. $\endgroup$ – Alexey B. Nov 25 '16 at 16:49
  • $\begingroup$ Another possibility to investigate is to define both size_t and pointer types to be ℕ ∪ {ω}. This gets rid of the min/max problem. The issue with overflow semantics still remains. What should be the semantics of uint x = (uint)ω is not clear to me. Again, we could haphazardly take 0, but it does look a bit ugly. $\endgroup$ – Alexey B. Nov 25 '16 at 17:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.