<p>As noted in the question, standard C requires that there exists a value UCHAR_MAX such that every variable of type <code>unsigned char</code> 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 <code>unsigned char*</code>, and that there be a constant <code>sizeof(unsigned char*)</code> such that every pointer of that type be identifiable by a sequence of <code>sizeof(unsigned char *)</code> values of type <code>unsigned char</code>.  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.</p>

<p>A program could store an unbounded quantity of information on the stack <em>if nothing that is allocated on the stack ever has its address taken</em>; 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.</p>

<p>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 <em>if code ever examined the sequence of characters associated with those pointers</em>.  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 <em>really</em> slow], then it would indeed be possible to make C a Turing-complete language.</p>

CC BY-SA 3.0
2016-07-26T20:37:36.633Z
With such a machine, what would sizeof(char) return?
TLW
CC BY-SA 3.0
2016-07-26T20:51:36.537Z
@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.
supercat
CC BY-SA 3.0
2016-07-26T21:32:19.913Z
Whoops, I meant CHAR_BITS, as you said, sorry.
TLW
CC BY-SA 3.0
2015-04-27T01:41:32.513Z
2015-05-23T17:03:35.643Z
2015-05-23T17:03:35.643Z
supercat
<p>With C11's (optional) threading library, it is possible to make a Turing complete implementation given unlimited recursion depth.</p>

<p>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.</p>

CC BY-SA 4.0
2019-03-07T18:08:18.950Z
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.
xamid
CC BY-SA 3.0
2016-11-19T22:53:05.540Z
2016-11-19T22:53:05.540Z
Jared
<p>I think it is <strong>Turing complete</strong>: 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 :-)</p>

<ul>
<li>define a structure that can be used as a double linked list for tape representation</li>
</ul>

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

<p>The <code>head</code> will be a pointer to a <code>cell_t</code> structure</p>

<ul>
<li>define a structure that can be used to store current state and a flag</li>
</ul>

<pre>    typedef struct {
      int state;
      int flag;
    } info_t </pre>

<ul>
<li>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:</li>
</ul>

<pre>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
}</pre>

<ul>
<li>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:</li>
</ul>

<pre>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;
  }
}</pre>

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

<pre>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);
}</pre>

<p><strong>EDIT:</strong> after thinking a little bit about it, there is a problem with the pointers ...</p>

<p><em>if every call of the recursive function <code>stacker</code> can mantain a valid pointer to a variable defined locally in the caller then everything is fine</em>; 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).</p>

CC BY-SA 3.0
2012-09-03T21:22:33.783Z
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?
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2012-09-03T21:36:57.783Z
@Gilles: you're right (see my edit); if you limit the recursion depth you get a finite automaton
Marzio De Biasi
CC BY-SA 4.0
2019-03-07T19:00:04.463Z
@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](https://stackoverflow.com/questions/10242839/is-there-any-hard-wired-limit-on-recursion-depth-in-c/10242919#10242919). 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.
xamid
CC BY-SA 3.0
2012-09-03T20:55:43.233Z
2012-09-03T21:25:04.793Z
2012-09-03T21:25:04.793Z
Marzio De Biasi
<p><s>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.</s></p>

<p><strong>EdIT</strong>: <em>If you can only use the ram, which is finite, this construction does not work anymore, so see below.</em></p>

<p>However it is highly questionable why your stack can be infinite but the intrinsic ram is not. <s>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).</p>

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

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

<p><em>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 <strong>and</strong> 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?</em></p>

CC BY-SA 2.5
2010-10-29T22:05:02.357Z
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.
Gilles 'SO- stop being evil'
CC BY-SA 2.5
2010-10-29T22:38:22.440Z
I've modified my answer to exclude the use of a stack-pointer.
bitmask
CC BY-SA 2.5
2010-11-04T23:42:17.307Z
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 *un*defined behavior.
Gilles 'SO- stop being evil'
CC BY-SA 2.5
2010-10-29T21:46:02.720Z
2010-10-29T22:37:34.937Z
2010-10-29T22:37:34.937Z
bitmask
<p>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:</p>

<pre><code>void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&amp;back);
  else reject();
  for(it = back; it != NULL; it = *it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}
</code></pre>

<p>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.</p>

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

<p>A fixed version:</p>

<pre><code>void *it;

void read_triple(void *back)
{
  if(read_a()) read_triple(&amp;back);
  else for(it = back; it != NULL; it = * (void **) it)
     if(!read_b()) reject();
  if(read_c()) return;
  else reject();
}
</code></pre>

CC BY-SA 3.0
2012-09-12T02:48:31.760Z
Well, not a fundamental mistake, but `it = *it` should be replaced by `it = * (void **) it`, as otherwise `*it` is of type `void`.
Ben Standeven
CC BY-SA 3.0
2012-09-12T07:26:22.017Z
I would be very surprised if travelling the call stack like that would be defined behavior in C.
Radu GRIGore
CC BY-SA 3.0
2012-10-15T05:12:45.060Z
Oh, this won't work, because the first 'b' causes read_a() to fail and hence triggers a rejection.
Ben Standeven
CC BY-SA 3.0
2012-10-15T05:15:57.180Z
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.
Ben Standeven
CC BY-SA 3.0
2013-10-17T17:20:10.150Z
@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*)}}$.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2012-09-03T18:28:24.403Z
2013-10-17T14:00:17.037Z
2013-10-17T14:00:17.037Z
Ben Standeven
<p>Along the lines of @supercat's answer:</p>

<p>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</p>

<blockquote>
  <p>As noted in the question, standard C requires that there exists a value <code>UCHAR_MAX</code> such that every variable of type unsigned char will always hold a value between 0 and <code>UCHAR_MAX</code>, 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 <code>sizeof(unsigned char*)</code> such that every pointer of that type be identifiable by a sequence of <code>sizeof(unsigned char *)</code> values of type unsigned char.</p>
</blockquote>

<p>I'm wondering if C allows us to operate ordinals and infinite sequences of bytes. If so, we can take the set of <code>unsigned char*</code> pointers to be $\mathbb{N}$ and the set of unsigned chars to be $\{0, 1\}$ just for simplicity. Then we should define <code>sizeof(unsigned char*)</code>, 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 <code>sizeof(unsigned char*)</code> to be $\mathbb{N}$ ($\omega$ if you wish).</p>

<p>At this point, one should check that C standard would indeed allow that.</p>

<p>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 <code>sizeof</code> is always $\in \mathbb Z$) and then we may be out of luck.</p>

CC BY-SA 3.0
2016-11-25T16:03:39.430Z
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?
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2016-11-25T16:26:08.087Z
@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).
Alexey B.
CC BY-SA 3.0
2016-11-25T16:35:52.430Z
`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.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2016-11-25T16:49:48.280Z
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.
Alexey B.
CC BY-SA 3.0
2016-11-25T17:04:23.383Z
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.
Alexey B.
CC BY-SA 3.0
2016-11-25T15:48:27.857Z
2016-11-25T16:01:13.300Z
2016-11-25T16:01:13.300Z
Alexey B.
<p>If we go by the <a href="http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf">book</a> (or any other version of the language specification if you prefer), how much computational power can a C implementation have?</p>

<p>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.</p>

<p>For the purpose of this question, there is no external storage. The only input/output you may perform is <code>getchar</code> (to read the program input) and <code>putchar</code> (to write the program output). Also any program that invokes <em>undefined</em> 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.</p>

<p>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 <code>sizeof(char*) * CHAR_BIT</code> bits of storage, since distinct memory addresses must have distinct bit patterns when stored in a byte pointer).</p>

<p>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 (<code>register</code>) arguments. Thus a C implementation that allows arbitrary recursion and has no limit on the number of <code>register</code> objects can encode deterministic pushdown automata.</p>

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

CC BY-SA 3.0
2013-06-28T00:13:01.167Z
@JukkaSuomela: "the same overflow could give you different results, which is clearly against the spirit of the standard". I'd bet optimizing C compilers do that, I think the first example of [this blog post](http://blog.regehr.org/archives/226) from John Regehr already shows that. Note that he makes a living from craziness of C compilers.
Blaisorblade
CC BY-SA 3.0
2016-07-26T19:04:36.190Z
I suspect you could do something with storing data in the call stack and using setjmp / longjmp.
TLW
CC BY-SA 3.0
2016-07-26T19:18:20.980Z
@TLW How would that help? There can only be finitely many reachable jump buffers ($2^{\texttt{CHAR_BIT} \times \texttt{sizeof(sigjmp_buf)}}$).
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2016-07-26T19:21:09.247Z
@Gilles - Given a C implementation that ensures that stack frames do not overlap upon jumping, and that allows arbitrary recursion, I think you might be able to make a two-stack machine, using the two sets of stack frames as the two stacks. If that makes sense.
TLW
CC BY-SA 3.0
2016-07-26T19:31:14.687Z
@Gilles - Actually, you may be able to emulate a TM directly. The Nth stack frame holds the value at the Nth cell of the tape. The first time it's called, it setjmps a placeholder and then longjumps back into the parent frame. After that, it sets up another child if necessary, and otherwise does the TM action at that step based on the current value, and longjmps either to the parent or child, depending.
TLW
CC BY-SA 3.0
2016-07-26T20:16:03.227Z
@TLW But that requires a jmpbuf per tape cell, and that's not possible since the number of jmpbufs is bounded.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2016-07-26T20:27:29.767Z
Is it actually bounded if they are register variables? Or, to put it another way, what is the difference between unbounded recursion with each stack frame having a register jmpbuf and unbounded recursion with each stack frame having a register int?
TLW
CC BY-SA 3.0
2016-07-26T20:33:16.517Z
@TLW You can have an unbounded number of live `register jmp_buf` variables, but that's no help: they can only take finitely many different values.
Gilles 'SO- stop being evil'
CC BY-SA 3.0
2016-07-26T21:07:54.790Z
@Gilles - The C implementation has to behave "as if" different `register jmp_buf`s are different - but that is not the same thing as saying that they have to actually be different. Imagine, for instance, if the implementation  encodes jmp_bufs as offsets of the stack address where the jmp_buf is declared as long as it can deduce that the address of the jmp_buf is never taken and it is never checked for equality / inequality.
TLW
CC BY-SA 4.0
2019-02-26T07:15:34.677Z
@Gilles I do not see how this overflow trick could lead to showing the Turing completeness of C, would you like to work this out in detail? (asked on behalf of user100814, see [here](https://cs.stackexchange.com/questions/104704/) for details )
Discrete lizard
CC BY-SA 2.5
2010-10-29T18:26:33.607Z
If you assume that memory is finite, then you have a finite state machine. If you assume unbounded memory, you have a Turing-complete language, assuming of course that there is a way of addressing all of that memory.
Dave Clarke
CC BY-SA 2.5
2010-10-29T18:31:32.777Z
@Dave: As Gilles explained, it seems that you can have unbounded memory, but no way to directly address it.
Jukka Suomela
CC BY-SA 2.5
2010-10-29T18:53:21.530Z
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.
Warren Schudy
CC BY-SA 2.5
2010-10-29T19:00:19.590Z
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.
Jukka Suomela
CC BY-SA 2.5
2010-10-29T19:17:19.787Z
@Jukka: good point about undefined behavior, that was a loophole I hadn't intended. But I don't see how to exploit signed overflow: the implementation may raise a signal, but how does this help beyond adding a few states to the automaton?
Gilles 'SO- stop being evil'
CC BY-SA 2.5
2010-10-29T19:22:34.960Z
@Gilles: Well, can't that implementation write a bit on a hidden "query tape" every time you do an overflow (different bits depending on the kind of overflow)? And then if the implementation doesn't raise a signal but returns a value, the value could be an answer from the oracle? (Of course this would mean that the *same* overflow could give you *different* results, which is clearly against the spirit of the standard, but I guess not explicitly forbidden. :)
Jukka Suomela
CC BY-SA 2.5
2010-10-29T19:24:25.783Z
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. :)
Jukka Suomela
CC BY-SA 2.5
2010-10-29T22:00:26.667Z
@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!)
Gilles 'SO- stop being evil'
CC BY-SA 2.5
2010-11-04T17:54:02.417Z
Surely if you can use stdout and stdin you can communicate over the internet with a Turing machine (with an infinite tape)? (Edit: Or is there some limit on how much you can write to stdout? Say because of a file counter or something?)
Emil
CC BY-SA 2.5
2010-11-04T17:57:56.920Z
If internet communication is allowed, we may as well hook our C program up to a Halting Oracle! :)
Emil
CC BY-SA 2.5
2010-11-04T23:36:10.290Z
@Emil: Stdin and stdout are only to read the input data and write the output data (they have to come from somewhere). If you can communicate with an external oracle, you're no longer measuring the computational power of the C implementation, you're measuring the system consisting of the implementation plus the oracle.
Gilles 'SO- stop being evil'
<computability><turing-machines><pl.programming-languages><recreational>
Maximum computational power of a C implementation
Gilles 'SO- stop being evil'
# Maximum computational power of a C implementation

(Asked by: username_0 on 2010-10-29)

If we go by the [book](http://www.open-std.org/jtc1/sc22/wg14/www/docs/n1256.pdf) (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?

**Tags:** computability, turing-machines, pl.programming-languages, recreational
> **Comments:**
> **username_4**: If you assume that memory is finite, then you have a finite state machine. If you assume unbounded memory, you have a Turing-complete language, assuming of course that there is a way of addressing all of that memory.  
> **username_5**: @Dave: As Gilles explained, it seems that you can have unbounded memory, but no way to directly address it.  
> **username_6**: 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.  
> **username_5**: 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.  
> **username_0**: @Jukka: good point about undefined behavior, that was a loophole I hadn't intended. But I don't see how to exploit signed overflow: the implementation may raise a signal, but how does this help beyond adding a few states to the automaton?  
> **username_5**: @Gilles: Well, can't that implementation write a bit on a hidden "query tape" every time you do an overflow (different bits depending on the kind of overflow)? And then if the implementation doesn't raise a signal but returns a value, the value could be an answer from the oracle? (Of course this would mean that the *same* overflow could give you *different* results, which is clearly against the spirit of the standard, but I guess not explicitly forbidden. :)  
> **username_5**: 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. :)  
> **username_0**: @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!)  
> **username_7**: Surely if you can use stdout and stdin you can communicate over the internet with a Turing machine (with an infinite tape)? (Edit: Or is there some limit on how much you can write to stdout? Say because of a file counter or something?)  
> **username_7**: If internet communication is allowed, we may as well hook our C program up to a Halting Oracle! :)  
> **username_0**: @Emil: Stdin and stdout are only to read the input data and write the output data (they have to come from somewhere). If you can communicate with an external oracle, you're no longer measuring the computational power of the C implementation, you're measuring the system consisting of the implementation plus the oracle.  
> **username_1**: @JukkaSuomela: "the same overflow could give you different results, which is clearly against the spirit of the standard". I'd bet optimizing C compilers do that, I think the first example of [this blog post](http://blog.regehr.org/archives/226) from John Regehr already shows that. Note that he makes a living from craziness of C compilers.  
> **username_2**: I suspect you could do something with storing data in the call stack and using setjmp / longjmp.  
> **username_0**: @TLW How would that help? There can only be finitely many reachable jump buffers ($2^{\texttt{CHAR_BIT} \times \texttt{sizeof(sigjmp_buf)}}$).  
> **username_2**: @Gilles - Given a C implementation that ensures that stack frames do not overlap upon jumping, and that allows arbitrary recursion, I think you might be able to make a two-stack machine, using the two sets of stack frames as the two stacks. If that makes sense.  
> **username_2**: @Gilles - Actually, you may be able to emulate a TM directly. The Nth stack frame holds the value at the Nth cell of the tape. The first time it's called, it setjmps a placeholder and then longjumps back into the parent frame. After that, it sets up another child if necessary, and otherwise does the TM action at that step based on the current value, and longjmps either to the parent or child, depending.  
> **username_0**: @TLW But that requires a jmpbuf per tape cell, and that's not possible since the number of jmpbufs is bounded.  
> **username_2**: Is it actually bounded if they are register variables? Or, to put it another way, what is the difference between unbounded recursion with each stack frame having a register jmpbuf and unbounded recursion with each stack frame having a register int?  
> **username_0**: @TLW You can have an unbounded number of live `register jmp_buf` variables, but that's no help: they can only take finitely many different values.  
> **username_2**: @Gilles - The C implementation has to behave "as if" different `register jmp_buf`s are different - but that is not the same thing as saying that they have to actually be different. Imagine, for instance, if the implementation  encodes jmp_bufs as offsets of the stack address where the jmp_buf is declared as long as it can deduce that the address of the jmp_buf is never taken and it is never checked for equality / inequality.  
> **username_3**: @Gilles I do not see how this overflow trick could lead to showing the Turing completeness of C, would you like to work this out in detail? (asked on behalf of user100814, see [here](https://cs.stackexchange.com/questions/104704/) for details )  

---

## 6 answers

### Answer by username_8 on 2015-04-27. Score: 8

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.

> **Comments:**
> **username_2**: With such a machine, what would sizeof(char) return?  
> **username_8**: @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.  
> **username_2**: Whoops, I meant CHAR_BITS, as you said, sorry.  

---

### Answer by username_9 on 2016-11-19. Score: 7

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.

> **Comments:**
> **username_10**: 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.  

---

### Answer by username_11 on 2012-09-03. Score: 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(⊤, 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).

> **Comments:**
> **username_0**: 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?  
> **username_11**: @Gilles: you're right (see my edit); if you limit the recursion depth you get a finite automaton  
> **username_10**: @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](https://stackoverflow.com/questions/10242839/is-there-any-hard-wired-limit-on-recursion-depth-in-c/10242919#10242919). 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.  

---

### Answer by username_12 on 2010-10-29. Score: 0

~~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 `k`s).

**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?*

> **Comments:**
> **username_0**: 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.  
> **username_12**: I've modified my answer to exclude the use of a stack-pointer.  
> **username_0**: 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 *un*defined behavior.  

---

### Answer by username_13 on 2012-09-03. Score: 0

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();
}

> **Comments:**
> **username_13**: Well, not a fundamental mistake, but `it = *it` should be replaced by `it = * (void **) it`, as otherwise `*it` is of type `void`.  
> **username_14**: I would be very surprised if travelling the call stack like that would be defined behavior in C.  
> **username_13**: Oh, this won't work, because the first 'b' causes read_a() to fail and hence triggers a rejection.  
> **username_13**: 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.  
> **username_0**: @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*)}}$.  

---

### Answer by username_15 on 2016-11-25. Score: 0

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.

> **Comments:**
> **username_0**: 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?  
> **username_15**: @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).  
> **username_0**: `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.  
> **username_15**: 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.  
> **username_15**: 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.  

---

