52
$\begingroup$

I was trying to explain to someone that C is Turing-complete, and realized that I don't actually know if it is, indeed, technically Turing-complete. (C as in the abstract semantics, not as in an actual implementation.)

The "obvious" answer (roughly: it can address an arbitrary amount of memory, so it can emulate a RAM machine, so it's Turing-complete) isn't actually correct, as far as I can tell, as although the C standard allows for size_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite. (In other words, although you could, given an arbitrary halting Turing machine, pick a length of size_t such that it will run "properly", there is no way to pick a length of size_t such that all halting Turing machines will run properly)

So: is C99 Turing-complete?

$\endgroup$
13
  • 5
    $\begingroup$ What are the "abstract semantics" of C? Are they defined anywhere? $\endgroup$ Jul 26 '16 at 15:01
  • 4
    $\begingroup$ @YuvalFilmus - See e.g. here, i.e. C as defined in the standard as opposed to e.g. "this is how gcc does it". $\endgroup$
    – TLW
    Jul 26 '16 at 18:18
  • 2
    $\begingroup$ there is the "technicality" that modern computers do not have infinite memory like the TM yet are still considered "universal computers". and note that programming languages in their "semantics" do not really assume a finite memory except that all their implementations are of course limited in memory. see eg does our pc work as a Turing machine. anyway essentially all "mainstream" programming languages are Turing complete. $\endgroup$
    – vzn
    Jul 27 '16 at 15:02
  • 5
    $\begingroup$ C (like Turing machines) isn't limited to using internal computer memory for its computations, so this really isn't a valid argument against the Turing completeness of C. $\endgroup$ Oct 3 '16 at 21:05
  • $\begingroup$ @reinierpost - that's like saying a teletype is sapient. That's saying that "C + an external TM-equivalent" is Turing-complete, not that C is Turing-complete. $\endgroup$
    – TLW
    Dec 27 '16 at 4:07

14 Answers 14

38
$\begingroup$

I'm not sure but I think the answer is no, for rather subtle reasons. I asked on Theoretical Computer Science a few years ago and didn't get an answer that goes beyond what I'll present here.

In most programming languages, you can simulate a Turing machine by:

  • simulating the finite automaton with a program that uses a finite amount of memory;
  • simulating the tape with a pair of linked lists of integers, representing the content of the tape before and after the current position. Moving the pointer means transferring the head of one of the lists onto the other list.

A concrete implementation running on a computer would run out of memory if the tape got too long, but an ideal implementation could execute the Turing machine program faithfully. This can be done with pen and paper, or by buying a computer with more memory, and a compiler targeting an architecture with more bits per word and so on if the program ever runs out of memory.

This doesn't work in C because it's impossible to have a linked list that can grow forever: there's always some limit on the number of nodes.

To explain why, I first need to explain what a C implementation is. C is actually a family of programming languages. The ISO C standard (more precisely, a specific version of this standard) defines (with the level of formality that English allows) the syntax and semantics a family of programming languages. C has a lot of undefined behavior and implementation-defined behavior. An “implementation” of C codifies all the implementation-defined behavior (the list of things to codify is in appendix J for C99). Each implementation of C is a separate programming language. Note that the meaning of the word “implementation” is a bit peculiar: what it really means is a language variant, there can be multiple different compiler programs that implement the same language variant.

In a given implementation of C, a byte has $2^{\texttt{CHAR_BIT}}$ possible values. All data can represented as an array of bytes: a type t has at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(t)}}$ possible values. This number varies in different implementations of C, but for a given implementation of C, it's a constant.

In particular, pointers can only take at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ values. This means that there is a finite maximum number of addressable objects.

The values of CHAR_BIT and sizeof(void*) are observable, so if you run out of memory, you can't just resume running your program with larger values for those parameters. You would be running the program under a different programming language — a different C implementation.

If programs in a language can only have a bounded number of states, then the programming language is no more expressive than finite automata. The fragment of C that's restricted to addressable storage only allows at most $n \times 2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ program states where $n$ is the size of the abstract syntax tree of the program (representing the state of the control flow), therefore this program can be simulated by a finite automaton with that many states. If C is more expressive, it has to be through the use of other features.

C does not directly impose a maximum recursion depth. An implementation is allowed to have a maximum, but it's also allowed not to have one. But how do we communicate between a function call and its parent? Arguments are no good if they're addressable, because that would indirectly limit the depth of recursion: if you have a function int f(int x) { … f(…) …} then all the occurrences of x on active frames of f have their own address and so the number of nested calls is bounded by the number of possible addresses for x.

A C program can use non-addressable storage in the form of register variables. “Normal” implementations can only have a small, finite number of variables that don't have an address, but in theory an implementation could allow an unbounded amount of register storage. In such an implementation, you can make an unbounded amount of recursive calls to a function, as long as its argument are register. But since the arguments are register, you can't make a pointer to them, and so you need to copy their data around explicitly: you can only pass around a finite amount of data, not an arbitrary-sized data structure that's made of pointers.

With unbounded recursion depth, and the restriction that a function can only get data from its direct caller (register arguments) and return data to its direct caller (the function return value), you get the power of deterministic pushdown automata.

I can't find a way to go further.

(Of course you could make the program store the tape content externally, through file input/output functions. But then you wouldn't be asking whether C is Turing-complete, but whether C plus an infinite storage system is Turing-complete, to which the answer is a boring “yes”. You might as well define the storage to be a Turing oracle — call fopen("oracle", "r+"), fwrite the initial tape content to it and fread back the final tape content.)

$\endgroup$
17
  • 8
    $\begingroup$ Sorry, but by the same logic, there are no Turing-complete programming languages at all. Each language has an explicit or implicit limitation on address space. If you create a machine with infinite memory, then random access pointers will obviously also be of infinite length. Therefore, if such machine appears, it will have to offer an instruction set for sequential memory access, along with an API for high-level languages. $\endgroup$
    – IMil
    Nov 25 '16 at 18:39
  • 22
    $\begingroup$ @IMil This is not true. Some programming languages have no limitation on address space, not even implicitly. To take an obvious example, a universal Turing machine where the initial state of the tape forms the program is a Turing-complete programming language. Many programming languages that are actually used in practice have the same property, for example Lisp and SML. A language doesn't have to have a concept of “random access pointer”. (cont.) $\endgroup$ Nov 25 '16 at 19:03
  • 16
    $\begingroup$ @IMil (cont.) Implementations usually do for performance, but we know that an implementation running on a particular computer is not Turing-complete since it's bounded by the size of the computer's memory. But that means that the implementation doesn't implement the whole language, only a subset (of programs running in N bytes of memory). You can run the program on a computer, and if it runs out of memory, move it to a bigger computer, and so on forever or until it halts. That would be a valid way to implement the whole language. $\endgroup$ Nov 25 '16 at 19:05
  • 2
    $\begingroup$ @polcott I don't understand what you mean by “defined category of computation”. An example of something a computer with finite memory can't do, but a computer with unlimited memory can do, is to simulates itself. This answer may be what you're looking for. $\endgroup$ Mar 11 '20 at 21:41
  • 4
    $\begingroup$ @polcott, it makes no sense to speak about "practical" and "computability" in the same sentence. Computability (and Turing-completeness) is not about what it is practical; it is about what is mathematically true. You seem to want to talk about what holds "for all engineering purposes" but that's not what Turing-completeness is about. $\endgroup$
    – D.W.
    Mar 12 '20 at 20:16
10
$\begingroup$

C99's addition of va_copy to the variadic argument API may give us a back door to Turing-completeness. Since it becomes possible to iterate through a variadic arguments list more than once in a function other than the one that originally received the arguments, va_args can be used to implement a pointerless pointer.

Of course, a real implementation of the variadic argument API is probably going to have a pointer somewhere, but in our abstract machine it can be implemented using magic instead.

Here's a demo implementing a 2-stack pushdown automaton with arbitrary transition rules:

#include <stdarg.h>
typedef struct { va_list va; } wrapped_stack; // Struct wrapper needed if va_list is an array type.
#define NUM_SYMBOLS /* ... */
#define NUM_STATES /* ... */
typedef enum { NOP, POP1, POP2, PUSH1, PUSH2 } operation_type;
typedef struct { int next_state; operation_type optype; int opsymbol; } transition;
transition transition_table[NUM_STATES][NUM_SYMBOLS][NUM_SYMBOLS] = { /* ... */ };

void step(int state, va_list stack1, va_list stack2);
void push1(va_list stack2, int next_state, ...) {
    va_list stack1;
    va_start(stack1, next_state);
    step(next_state, stack1, stack2);
}
void push2(va_list stack1, int next_state, ...) {
    va_list stack2;
    va_start(stack2, next_state);
    step(next_state, stack1, stack2);
}
void step(int state, va_list stack1, va_list stack2) {
    va_list stack1_copy, stack2_copy;
    va_copy(stack1_copy, stack1); va_copy(stack2_copy, stack2);
    int symbol1 = va_arg(stack1_copy, int), symbol2 = va_arg(stack2_copy, int);
    transition tr = transition_table[state][symbol1][symbol2];
    wrapped_stack ws;
    switch(tr.optype) {
        case NOP: step(tr.next_state, stack1, stack2);
        // Note: attempting to pop the stack's bottom value results in undefined behavior.
        case POP1: ws = va_arg(stack1_copy, wrapped_stack); step(tr.next_state, ws.va, stack2);
        case POP2: ws = va_arg(stack2_copy, wrapped_stack); step(tr.next_state, stack1, ws.va);
        case PUSH1: va_copy(ws.va, stack1); push1(stack2, tr.next_state, tr.opsymbol, ws);
        case PUSH2: va_copy(ws.va, stack2); push2(stack1, tr.next_state, tr.opsymbol, ws);
    }
}
void start_helper1(va_list stack1, int dummy, ...) {
    va_list stack2;
    va_start(stack2, dummy);
    step(0, stack1, stack2);
}
void start_helper0(int dummy, ...) {
    va_list stack1;
    va_start(stack1, dummy);
    start_helper1(stack1, 0, 0);
}
// Begin execution in state 0 with each stack initialized to {0}
void start() {
    start_helper0(0, 0);
}

Note: If va_list is an array type, then there are actually hidden pointer parameters to the functions. So it would probably be better to change the types of all va_list arguments to wrapped_stack.

$\endgroup$
6
  • $\begingroup$ This might work. A possible concern is that it relies on allocating an unbounded number of automatic va_list variables stack. These variables must have an address &stack, and we can only have a bounded number of these. This requirement could be circumvented by declaring every local variable register, maybe? $\endgroup$
    – chi
    Jun 9 '18 at 22:02
  • $\begingroup$ @chi AIUI a variable is not required to have an address unless someone tries to take the address. Also, it's illegal to declare the argument immediately preceding the ellipsis register. $\endgroup$
    – feersum
    Jun 10 '18 at 1:21
  • $\begingroup$ By the same logic, shouldn't an int be not required to have a bound unless someone uses the bound or sizeof(int)? $\endgroup$
    – chi
    Jun 10 '18 at 7:54
  • 1
    $\begingroup$ @chi Not at all. The standard defines as part of the abstract semantics that an int has a value between some finite bounds INT_MIN and INT_MAX. And if the value of an int overflows those bound, undefined behavior occurs. On the other hand, the standard intentionally does not require that all objects be physically present in memory at a particular address, as this permits optimizations such as storing the object in a register, storing only part of the object, representing it differently than the standard layout, or omitting it altogether if it is not needed. $\endgroup$
    – feersum
    Jun 10 '18 at 9:11
  • $\begingroup$ Doesn't work: the size of a struct must <= SIZE_T_MAX; which in turn means there are only 1<<SIZE_T_MAX possible invocations of step before it blows up. All types are blittable in C which means you could write a va_list to a file, discard the original, read it back again and it's still valid provided whatever it referenced is still in scope. $\endgroup$
    – Joshua
    Aug 26 '20 at 1:42
4
$\begingroup$

Nonstandard arithmetic, maybe?

So, it seems that the issue is the finite size of sizeof(t). However, I think I know a work around.

As far as I know, C does not require an implementation to use the standard integers for its integer type. Therefore, we could use a non-standard model of arithmetic. Then, we would set sizeof(t) to some nonstandard number, and now we will never reach it in a finite number of steps. Therefore, the length of the Turing machines tape will always be less than the "maximum", since the maximum is literally impossible to reach. sizeof(t) simply is not a number in the regular sense of the word.

This is one technicality of course: Tennenbaum's theorem. It states that the only model of Peano arithmetic is the standard one, which obviously would not do. However, as far as I know, C does not require implementations to use data types that satisfy the Peano axioms, nor does it require the implementation to be computable, so this should not be an issue.

What should happen if you try to output a nonstandard integer? Well, you can represent any nonstandard integer using a nonstandard string, so just stream digits from the front of that string.

$\endgroup$
6
  • $\begingroup$ What would an implementation look like? $\endgroup$ Feb 28 '19 at 9:40
  • $\begingroup$ @reinierpost I am guessing it would represent data using some countable nonstandard model of PA. It would compute arithmetical operations using a PA degree. I think any such model should provide a valid C implementation. $\endgroup$
    – PyRulez
    Feb 28 '19 at 9:58
  • $\begingroup$ Sorry, this doesn't work. sizeof(t) is itself a value of type size_t, so it is a natural integer between 0 and SIZE_MAX. $\endgroup$ Feb 28 '19 at 15:42
  • $\begingroup$ @Gilles SIZE_MAX would be a nonstandard natural as well then. $\endgroup$
    – PyRulez
    Feb 28 '19 at 19:48
  • $\begingroup$ This is an interesting approach. Note that you'd also need e.g. intptr_t / uintptr_t / ptrdiff_t / intmax_t / uintmax_t to be nonstandard. In C++ this would run afoul of forward progress guarantees... not sure about C. $\endgroup$
    – TLW
    Mar 18 '19 at 1:43
2
$\begingroup$

The answer is yes, but for an unexpected reason.

I believe the above comments are correct — given size_t is bounded, you cannot represent a turing machine with unbounded states by using C as intended. However, we can use C in a way which completely circumvents the size_t issue — using only the C preprocessor.

I will not go over the whole proof here — this answer explains it best. Essentially, using deferred expressions it is possible to create recursively expanding macros that expand forever. In this way, the depth of the recursion becomes limited only to the number of scans which the machine executes — this is a physical limitation, but in theory the machine could scan forever. The answer also explains how logical operations can be constructed.

So in conclusion: yes, C is turing-complete, but you have to totally misuse the preprocessor.

$\endgroup$
1
  • 3
    $\begingroup$ stackoverflow.com/a/3136798 argues that the technique in that answer is does not yield Turing-completeness. Do you have a rebuttal to that argument? $\endgroup$
    – D.W.
    Apr 12 '20 at 2:55
0
$\begingroup$

IMO, a strong limitation is that the addressable space (via the pointer size) is finite, and this is unrecoverable.

One could advocate that memory can be "swapped to disk", but at some point the address information will itself exceed the addressable size.

$\endgroup$
2
  • $\begingroup$ Isn't this the main point of the accepted answer? I don't think it adds anything new to the answers of this 2016 question. $\endgroup$
    – chi
    Mar 8 '19 at 9:14
  • $\begingroup$ @chi: no, the accepted answer doesn't mention swapping to external memory, which might be believed to be a workaround. $\endgroup$ Mar 8 '19 at 9:20
0
$\begingroup$

You could define a language quite similar to C, where it is allowed to change sizeof, for example by assigning

sizeof(int) = 20;
sizeof(void*) += 4;

etc. That would be Turing complete. As your requirements go up, you would just modify sizeof(void*) to be sufficiently large, same with sizeof(size_t), and then you can use realloc to make your arrays bigger.

$\endgroup$
1
  • 1
    $\begingroup$ Wouldn't changing type sizes have to invalidate all existing structs, and arrays of pointers, at least? Or I guess this hypothetical C environment could be "managed" and adjust things to still point to the right places after growing structs? Note that changing the size of void* necessarily changes (char*)&arr[10] - (char*)&arr[0] for an array of void*. But possibly you could define rules for how this works and force code to deal with the potentially massive inconvenience. I guess if opaque things like FILE* become fully abstract, changing their internals doesn't matter? $\endgroup$ Aug 27 '20 at 9:54
0
$\begingroup$

The problem isn’t that computers, being limited by the real world, cannot implement a Turing-complete machine. The problem in this question here is that the C language itself doesn’t allow it.

The C language could easily be changed to be Turing complete. Adding an integer type of unlimited size that can be used in malloc() and in pointer arithmetic would have solved the problem. In practice it wouldn’t make any difference, since we can’t even build a computer where 64 bit pointer sizes are the limit.

$\endgroup$
-1
$\begingroup$

In practice, these restrictions are irrelevant to Turing completeness. The real requirement is to allow the tape to be arbitrary long, not infinite. That would create a halting problem of a different kind (how does the universe "compute" the tape?)

It's as bogus as saying "Python isn't Turing complete because you can't make a list infinitely large".

[Edit: thanks to Mr. Whitledge for clarifying how to edit.]

$\endgroup$
8
  • 7
    $\begingroup$ I don't think this answers the quesiton. The question already anticipated this answer, and explained why it isn't valid: "although the C standard allows for size_t to be arbitrarily large, it must be fixed at some length, and no matter what length it is fixed at it is still finite". Do you have any response to that argument? I don't think we can count the question as answered unless the answer explains why that argument is wrong (or right). $\endgroup$
    – D.W.
    Nov 26 '16 at 18:39
  • 6
    $\begingroup$ At any given time, a value of type size_t is finite. The problem is that you can't establish a bound for size_t that's valid throughout the computation: for any bound, a program might overflow it. But the C language states that there exists a bound for size_t: on a given implementation, it can only grow up to sizeof(size_t) bytes. Also, be nice. Saying that people who criticize you “can't think on their own” is rude. $\endgroup$ Nov 28 '16 at 7:51
  • 2
    $\begingroup$ This is the correct answer. A Turning machine does not require an infinite tape, it requires an "arbitrarily long" tape. That is, you may assume that the tape is as long as it needs to be to complete the computation. You may also assume that your computer has as much memory as it needs. An infinite tape is absolutely not required, because any computation that halts in finite time cannot possibly use an infinite amount of tape. $\endgroup$ Jan 3 '18 at 19:28
  • 2
    $\begingroup$ This is another correct answer which is hardly visible due to the incapacity of most individuals in this community. Meanwhile, the accepted answer is false and its comment section is guarded by moderators deleting critical comments. Bye bye, cs.stackexchange. $\endgroup$
    – xamid
    Mar 7 '19 at 19:31
  • 2
    $\begingroup$ This answer is actually right. $\endgroup$
    – Brent
    Jan 15 at 17:51
-1
$\begingroup$

Removable media allows us to circumvent the unbounded memory problem. Perhaps people will think this is an abuse, but I think it's OK and essentially unavoidable anyway.

Fix any implementation of a universal Turing machine. For the tape, we use removable media. When the head runs off the end or beginning of the current disc, the machine prompts the user to insert the next or previous one. We can either use a special marker to denote the left end of the simulated tape, or have a tape that's unbounded in both directions.

The key point here is that everything the C program must do is finite. The computer only needs enough memory to simulate the automaton, and size_t only needs to be big enough to allow addressing that (actually rather small) amount of memory and on the discs, which can be of any fixed finite size. Since the user is only prompted to insert the next or previous disc, we don't need unboundedly large integers to say "Please insert disc number 123456..."

I suppose the principal objection is likely to be to the involvement of the user but that seems to be unavoidable in any implementation, because there seems to be no other way of implementing unbounded memory.

$\endgroup$
11
  • 3
    $\begingroup$ I'd argue that, unless the C definition requires such unbounded external storage, then this can not be accepted as a proof of Turing completeness. (ISO 9899 does not require that, of course, being written for the real-world engineering.) What concerns me is that, if we accept this, by a similar reasoning we might claim that DFAs are Turing complete, since they could be used to drive a head over a tape (the external storage). $\endgroup$
    – chi
    Jun 10 '18 at 8:08
  • $\begingroup$ @chi I don't see how the DFA argument follows. The whole point of a DFA is that it only has read access to storage. If you allow it to "drive a head over a tape", isn't that exactly a Turing machine? $\endgroup$ Jun 10 '18 at 10:01
  • 4
    $\begingroup$ Indeed, I'm nitpicking a bit here. The point is: why is it OK to add a "tape" to C, let C simulate a DFA, and use this fact to claim that C is Turing complete, when we can't do the same to DFAs? If C has no way to implement unbounded memory on its own, then it should not be considered Turing complete. (I'd still call it "morally" Turing complete, at least, since the bounds are so large that in practice they do not matter in most cases) I think that to definitively settle the matter, one would need a rigorous formal spec of C (the ISO standard does not suffice) $\endgroup$
    – chi
    Jun 10 '18 at 11:06
  • 2
    $\begingroup$ @chi It's OK because C includes file I/O routines. DFAs don't. $\endgroup$ Jun 10 '18 at 11:38
  • 3
    $\begingroup$ C does not completely specify what these routines do -- most of their semantics is implementation defined. A C implementation is not required to store the file contents, for instance, I think it can behave as if every file was "/dev/null", so to speak. It is also not required to store an unbounded amount of data. I'd say that your argument is correct, when considering what the vast majority of C implementations do, and generalizing that behaviour to an ideal machine. If we strictly rely on the C definition, only, forgetting the practice, I don't think it holds. $\endgroup$
    – chi
    Jun 10 '18 at 11:56
-2
$\begingroup$

Choose size_t to be infinitely large

You could choose size_t to be infinitely large. Naturally, it is impossible to realize such an implementation. But that's no surprise, given the finite nature of the world we live in.

Practical Implications

But even if it were possible to realize such an implementation, there would be practical issues. Consider the following C statement:

printf("%zu\n",SIZE_MAX);

This prints a decimal representation of SIZE_MAX to standard out. Presumably, SIZE_MAX is $O(2^{size\_t})$. So if size_t is infinitely large, SIZE_MAX is also infinitely large. The only way I know to print a decimal form of an infinitely large number is to produce an infinite stream of decimal digits. This means that printf will not terminate in some cases.

Fortunately, for our theoretical purposes, I could not find any requirement in the specification that guarantees printf will terminate for all inputs. So, as far as I am aware, we do not violate the C specification here.

On Computational Completeness

It still remains to prove that our theoretical implementation is Turing Complete. We can show this by implementing "any single-taped Turing Machine".

Most of us have probably implemented a Turing Machine as a school project. I won't give the details of a specific implementation, but here's a commonly used strategy:

  • The number of states, number of symbols, and state transition table are fixed for any given machine. So we can represent states and symbols as numbers, and the state transition table as a 2-dimensional array.
  • The tape can be represented as a linked list. We can either use a single double-linked list, or two single-linked lists (one for each direction from the current position).

Now let's see what's required to realize such an implementation:

  • The ability to represent some fixed, but arbitrarily large, set of numbers. In order to represent any arbitrary number, we choose MAX_INT to be infinite as well. (Alternatively, we could use other objects to represent states and symbols.)
  • The ability to construct an arbitrarily large linked list for our tape. Once again, there is no finite limit on the size. This means we cannot construct this list up-front, as we would spend forever just to construct our tape. But, we can construct this list incrementally if we use dynamic memory allocation. We can use malloc, but there's a little more we must consider:
    • The C specification allows malloc to fail if, e.g., available memory has been exhausted. So our implementation is only truly universal if malloc never fails.
    • However, if our implementation is run on a machine with infinite memory, then there is no need for malloc to fail. Without violating the C standard, our implementation will guarantee that malloc will never fail.
  • The ability to dereference pointers, lookup array elements, and access the members of a linked list node.

So the above list is what is necessary to implement a Turing Machine in our hypothetical C implementation. These features must terminate. Anything else, however, may be allowed to not terminate (unless required by the standard). This includes arithmetic, IO, etc.

$\endgroup$
18
  • 6
    $\begingroup$ What would printf("%zu\n",SIZE_MAX); print on such an implementation? $\endgroup$
    – Ruslan
    Nov 26 '16 at 13:26
  • 3
    $\begingroup$ @NathanDavis It's possible to implement a Turing machine. The trick is that you don't need to build an infinite tape — you just build the used portion of the tape incrementally as needed. $\endgroup$ Nov 28 '16 at 7:46
  • 2
    $\begingroup$ @Gilles: In this finite universe in which we are living, it is is impossible to implement a Turing machine. $\endgroup$
    – gnasher729
    Nov 28 '16 at 8:45
  • 3
    $\begingroup$ @NathanDavis But if you do that, then you've changed sizeof(size_t) (or CHAR_BITS). You can't resume from the new state, you have to start again, but the execution of the program may be different now that those constants are different $\endgroup$ Nov 28 '16 at 20:08
  • 3
    $\begingroup$ @NathanDavis Then you wouldn't have an implementation of the C language, you'd have an implementation of the subset of the C language consisting of programs whose behavior does not depend on sizeof(size_t). Not only that, but if you add up all the things that change (sizeof(ssize_t), sizeof(void*), etc.) you might not end up with a Turing-complete language anymore (I don't know if you do but it isn't obvious). $\endgroup$ Nov 28 '16 at 20:43
-2
$\begingroup$

The problem here is that you're artificially limiting the set of C programs to just the ones that use pointers (and size_t, intptr_t, what have you), but that's not necessary. If you're forced to use only the standard library, then "no" is kinda correct like in the accepted answer, but the semantics of C are indeed Turing complete.

Say you have a Real Turing Machine (TM) and it provides a library for pushing and popping from two stacks of unbounded size, and (for thoroughness) lets also say that they just compile to push and pop assembler instructions. Now your C program can push and pop infinitely to two stacks, unrestrained by the semantics of C. Et voila, Turing completeness.

This is not the only way we can show that C is Turing complete, and it turns out that this is not a high bar to meet for programming languages. The real challenge is in constructing a language that is not turing complete (e.g. SQL), and giving a proof for it.

Note: Other answers seem to suggest that Turing completeness requires arbitrary memory access, but that's simply not true. A push-down automaton with two unbounded stacks is sufficient, hence the scenario above.

$\endgroup$
2
  • 3
    $\begingroup$ C plus a library with unbounded push and pop is Turing-complete. Sure. But the question was about C, not C plus a library that provides whatever bits might be missing from C. You've shown that it's possible to give access to a PDA in C, not that it's possible to implement a PDA in C. $\endgroup$ Jan 15 at 19:16
  • 1
    $\begingroup$ The library doesn't give access to a PDA. It gives access to stacks. The question specifically asks about the semantics of C, and calling functions to access an unbounded stack is just as semantically valid as using a pointer to access RAM. You might as well argue that C doesn't let you implement RAM, but only gain access to it. The distinction is meaningless. $\endgroup$
    – Brent
    Jan 15 at 20:13
-2
$\begingroup$

Mapping "C" to a Turing equivalent abstract model of computation

C as it currently exists is not Turing complete because C inherently requires some fixed pointer size. We can however map a C like language to an abstract model of computation that is Turing complete.

The basic syntax and semantics of C could be mapped to an abstract model of computation that is Turing equivalent. The RASP model of computation is a model that "C" can be mapped to.

A variation of the RASP model is shown below that the x86/x64 language maps to. Since it is already known that "C" maps to the x86/x64 concrete models of computation we know that "C" maps to the following abstract model:

Instruction
     : INTEGER ":" OPCODE                     // Address:Opcode 
     | INTEGER ":" OPCODE INTEGER             // Address:Opcode Operand 
     | INTEGER ":" OPCODE INTEGER "," INTEGER // Address:Opcode Operand, Operand
HEXDIGIT [a-fA-F0-9]
INTEGER  {HEXDIGIT}+ 
OPCODE   HEXDIGIT{4} 
// OPCODE distinguishes between INTEGER literal and machine address operand.
// OPCODE INTEGER is space delimited.

Mapping the C language to the above abstract model of computation would enable the C language to become equivalent to a Turing machine.

Because the x86/x64 language maps to the above abstract model this also provides the basis for recognizing the subset of Turing equivalent x86/x64/C computations. As long as the required pointer size is no larger than the pointer size that is available the computation is Turing equivalent on finite hardware.

Turing equivalent computations derive equivalent output or fail to halt on equivalent input between the concrete machine and its Turing machine equivalent.

$\endgroup$
-4
$\begingroup$

The main argument here was that the size of the size_t is finite, although can be infinitely large.

There is a workaround for it, though I am not sure if this coincides with ISO C.

Assume you have a machine with infinite memory. Thus you are not bounded for pointer size. You still have your size_t type. If you ask me what is sizeof(size_t) the answer will be just sizeof(size_t). If you ask if it is greater than 100 for example the answer is yes. If you ask what is sizeof(size_t) / 2 as you could guess the answer is still sizeof(size_t). If you want to print it we can agree on some output. The difference of these two can be NaN and so on.

The summary is that relaxing the condition for size_t have finite size won't break any programs already existing.

P.S. Allocating memory sizeof(size_t) is still possible, you need only countable size, so let's say you take all evens (or similar trick).

$\endgroup$
3
  • 2
    $\begingroup$ "The difference of these two can be NaN". No it cannot be. There is no such thing as a NaN of integer type in C. $\endgroup$
    – TLW
    Dec 24 '16 at 5:32
  • 2
    $\begingroup$ According to the standard, sizeof has to return a size_t. So you have to choose some particular value. $\endgroup$
    – Draconis
    Mar 9 '19 at 0:20
  • $\begingroup$ My reasoning is similar. Instead I make sizeof(size_t) whatever finite size that is large enough for the current computation. This works for all computations requiring a finite amount of memory. Counting to infinity and storing the value of each increment is not on of these computations. $\endgroup$
    – polcott
    Sep 3 '20 at 22:57
-5
$\begingroup$

Yes it is.

1. Quoted answer

As a reaction on the high amount of downvotes on my (and other) correct answers – in comparison to the alarmingly high approval of false answers – I searched for a less theoretically profound alternative explanation. I found this one. I hope it covers some of the here common fallacies, so that a little more insight is shown. Essential part of the argument:

[...] His argument is as follows: suppose one has written a given terminating program which may require, during its execution, up to some arbitrary amount of storage. Without changing that program, it is possible a posteriori to implement a piece of computer hardware and its C compiler that provide enough storage to accommodate this computation. This may require widening the widths of char (via CHAR_BITS) and/or pointers (via size_t), but the program would not need to be modified. Because this is possible, C is indeed Turing-Complete for terminating programs.

The tricky part of this argument is that it only works when considering terminating programs. Terminating programs have this nice property that they have a static upper bound to their storage requirement, which one can determine experimentally by running the program over the desired input with increasing storage sizes, until it “fits.”

The reason why I was mislead in my train of thoughts it that I was considering the wider class of “useful” non-terminating programs [...]

In short, because for every computable function there is a solution in the C language (due to unlimited upper bounds), every computable problem has a C program, thus C is Turing-complete.

2. My original answer

There are widespread confusions between mathematical concepts in theoretical computer science (such as Turing-completeness) and their real-world application, i.e. techniques in practical computer science. Turing-completeness is not a property of physically existing machines or any in spacetime limited model. It is just an abstract object describing properties of mathematical theories.

C99 is Turing-complete regardless of implementation-based restrictions, just like virtually any other common programming language, since it is able to express a functionally complete set of logical connectives and has in principle access to an unlimited amount of memory. People have pointed out that C restricts the random-memory access explicitly to be limited, but this is nothing one could not circumvent, since these are additionally stated restrictions in the C standard, while Turing-completeness is entailed without them already:

Here is a very basic thing about logical systems that should suffice for a non-constructive proof. Consider a calculus with some axiom schemata and rules, such that the set of logical conseqences is X. Now if you add some rules or axioms, the set of logical consequences grows, i.e. must be a superset of X. This is why, for example, the modal logic S4 is properly contained in S5. Similarly, when you have a subspecification which is Turing-complete, but you add some restrictions on top, these do not prevent any of the consequences in X, i.e. there must be a way to circumvent all of the restrictions. If you want a non-Turing-complete language, the calculus must be reduced, not extended. Extensions which claim that something would not be possible, but actually is, only add inconsistency. These inconsistencies in the C standard may bear no practical consequences though, just like Turing-completeness is unrelated to practical application.

Simulating arbitrary numbers based on recursion depth (i.e. this; with the possibility to support multiple numbers via scheduling / pseudo-threads; there is no theoretical limit to recursion depth in C), or using file storage to simulate unlimited program memory (idea) are probably only two out of infinite possibilities to constructively prove Turing-completeness of C99. One should recall that for computability, time and space complexity are irrelevant. In particular, assuming a limited environment in order to falsify Turing-completeness is merely circular reasoning since that limitation excludes all problems which exceed the presupposed complexity bound.

(NOTE: I only wrote this answer to prevent people from being stopped to gain mathematical intuition due to some kind of application-oriented limited thinking. It is quite a pity that most learners will read the false accepted answer due to it being upvoted based on fundamental flaws of reasoning, so that more people will spread such false beliefs. If you downvote this answer, you are just part of the problem.)

$\endgroup$
13
  • 5
    $\begingroup$ I don't follow your last paragraph. You claim that adding restrictions increases expressive power, but that's clearly not true. Restrictions can only decrease expressive power. For example, if you take C and add the restriction that no program may access any more than 640kb of storage (of any kind), then you've turned it into a fancy finite automaton that clearly isn't Turing-complete. $\endgroup$ Mar 7 '19 at 15:54
  • 3
    $\begingroup$ If you have a fixed amount of storage, you can't simulate anything that requires more resources than you have. There are only finitely many configurations that your memory can possibly be in, which means that there are only finitely many things you can possibly do. $\endgroup$ Mar 7 '19 at 16:09
  • 2
    $\begingroup$ I don't understand why you refer to "physically existing machines". Note that Turing-completeness is a property of a mathematical computational model, not of physical systems. I would agree that no physical system, being a finite object, can get close to the power of Turing machines, but that's irrelevant. We can still take any programming language, consider the mathematical definition of its semantics, and check whether that mathematical object is Turing complete. Conway's game of life is Turing powerful even if there's no possible physical implementation. $\endgroup$
    – chi
    Mar 7 '19 at 16:27
  • 2
    $\begingroup$ @xamid If you have concerns regarding the moderation policies of this site, take it to Computer Science Meta. Until then, please be nice. Verbal abuse of others will not be tolerated. (I have removed all comments that do not pertain to the subject matter at hand.) $\endgroup$
    – Raphael
    Mar 7 '19 at 19:27
  • 3
    $\begingroup$ @xamid I feel like we're talking in circles. The theoretical mathematical model behind Python, as defined in the standard, doesn't require some concrete upper limit on the length of a list. The theoretical mathematical model behind C, as defined in the standard, does. Thus Python running on an imaginary infinite machine could have an arbitrarily long tape, while C could not: I can write a C program which checks the limits built into the language and intentionally exceeds them, which cannot run successfully even on a theoretical infinite-memory computer. I can't do that in Python. $\endgroup$
    – Draconis
    Mar 8 '19 at 15:09

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.