Compilers with pointer providence are allowed to expose Turing-complete C
Under a pointer providence model such as N2676, (size_t)-1 isn't necessarily the max allocatable bytes. Despite that being C17, compilers like Clang and GCC already assume pointer providence no matter the language, so an ideal optimizing compiler is allowed to expose Turing-complete behavior in C99.
The accepted answer is based on supercat's answer on cstheory.SE. However, a crucial portion wasn't copied. My answer provides modern justification for this condition.
[...] 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 [not needed for this answer], 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.
Assume an implementation where size_t and uintptr_t are 32-bit. It's the full C language, not a subset that leaves them indeterminate at infinity. I claim that a compiler is allowed to have the following linked-list be able to allocate as much as $2^{40}$ bytes:
// tape.h
#pragma once
void init(void);
void prev(void);
void next(void);
int get(void);
void set(int);
// tape.c
#include <stdlib.h>
#include "tape.h"
// No non-C library required. Just this pure-C library
struct node {
int value;
struct node *next;
struct node *prev;
};
// The static keyword makes All the difference
// It allows a closed-world assumption that only the code below in this file can touch this
// See also the set/call part of
// https://blog.llvm.org/2011/05/what-every-c-programmer-should-know_14.html
static struct node * cur;
void init(void) {
cur = calloc(sizeof(struct node), 1);
}
void prev(void) {
if (!cur->prev) cur->prev = calloc(sizeof(struct node), 1);
cur->prev->next = cur;
cur = cur->prev;
}
void next(void) {
if (!cur->next) cur->next = calloc(sizeof(struct node), 1);
cur->next->prev = cur;
cur = cur->next;
}
int get(void) {
return cur->value;
}
void set(int x) {
cur->value = x;
}
// turing_machine.c
int main() {
// Not important, just adapt https://cs.stackexchange.com/a/92903/163343
// or https://cstheory.stackexchange.com/a/12498/74073
}
Part 1: Memory allocation doesn't always correspond to integral types
sizeof(size_t) is the wrong constant to examine. A 3-bit size_t can allow allocating $2^{64}$ bytes total, as it only needs to hold the size of the largest object, not its address.
Comparing uintptr_t is better. However, casting between integers and pointers is not always one-to-one like on x86. A compiler for a 32-bit CPU can have a 24-bit uintptr_t if that's the address space, requiring a sign extension / masking for casting. Pointer authentication on ARM further diverges from bit-copy bijectivity. On ARM CHERI, sizeof(size_t) < sizeof(uintptr_t). It wouldn't be far to use a global lookup table for casting, which we will in part 4.
Gilles' accepted answer said that "pointers can only take at most $2^{\texttt{CHAR_BIT} \times \texttt{sizeof(void*)}}$ values". That is only true after being cast to uintptr_t in a non-pathological implementation. Following the ISO C standard link he provided, we see:
Any pointer type may be converted to an integer type. Except as previously specified, the result is implementation-defined. If the result cannot be represented in the integer type, the behavior is undefined. The result need not be in the range of values of any integer type. [emphasis mine]
"All data can [be] represented as an array of bytes" is the harder 6.2.6.1.4, but here's an analogy:
// analogy.c
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
struct foo {
int data[400000000]; // ~ 1.5 GiB
};
struct bar {
char data[1600000000]; // same size
};
int main() {
struct foo *original = malloc(sizeof(struct foo));
fread(original->data, 4, 400000000, fopen("stuff", "r"));
// Reachable
fwrite(original->data, 1, 1, fopen("first", "w"));
fwrite(&original->data[1600000000-1], 1, 1, fopen("last", "w"));
struct bar *copy = malloc(sizeof(struct bar));
// Unreachable
memcpy(copy->data, original->data, 1600000000);
fwrite(copy->data, 1, 1600000000, fopen("out", "w"));
}
Use 32-bit Windows (see part 2), and the memcpy is unreachable. It'd be ~3 GiB after the second malloc, exceeding the 2 GiB limit. But creating a 1.5 GiB integer array works as expected, despite 6.2.6.1.4 "The value may be copied into an object of type unsigned char [n] (e.g., by memcpy);". It's because the compiler interprets the "resulting set of bytes ..." sentences as only applying after memcpy returns. In the analogy and part 4, it's unobservable that pointer "Values stored in non-bit-field objects of any other object type consist of n × CHAR_BIT bits" as long as no memcpy is made, so a pointer can exist without an "object representation".
Part 2: Implementation decides how much memory you can allocate
Consider Windows on a 32-bit CPU with 4 GiB, or it running a 32-bit process on 64-bit with 128 GiB. Despite a 32-bit uintptr_t, only 2**31 bytes can be allocated. Windows with the /3GB switch lets the same C99-source program allocate 3 GB of RAM. Setting ulimit -m on Linux, the same can allocate that much max. Another factor is RAM/swap installed and RAM in other programs. Embedded sometimes has malloc always return 0. In conclusion, the implementation can choose to limit allocatable memory, so it's meaningless to consider anything but the ideal theoretical optimizing compiler.
In C, I can write:
// twice.c
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>
int main(){
if(!!malloc(-1) && !!malloc(-1))
printf("%u\n",SIZE_MAX);
}
With clang -O3 -m32 twice.c (not GCC), ./a.out prints 4294967295. It's analogous for 64-bit. While people were worrying about size_t, I just went ahead and allocated 2*SIZE_MAX and Clang let me. At first glance, this may appear to violate 6.2.4.2 of the C standard as only 1*SIZE_MAX addresses are available:
An object exists, has a constant address,25) and retains its last-stored value throughout its lifetime
25) The term ‘‘constant address’’ means that two pointers to the object constructed at possibly different times will compare equal.
But the compiler knows nobody in twice.c is "compare"ing the pointers. When it can prove so, the "has a constant address" part of the standard has no effect and can be ignored by an optimizing compiler.
Part 3: Union of a Turing-complete and -incomplete language is Turing-complete
A Turing-complete lang's compiler can be combined with a Turing-incomplete lang's one depending on the file received. An evolution is handling both in one file using extern blocks:
Consider this code:
// Example only. Will return to C99.
extern "eBPF" {
int prime_16bit(short nth) {
// Assume this is implemented
}
}
extern "C" {
int main() {
printf("%d\n", prime_16bit(10)); // Prints "29"
}
}
eBPF before 5.15 isn't Turing-complete. Assume it's invoked by the C like a CUDA launch.
Let's return to C99. Change extern to autodetection, and switch those languages to "Turing-complete C99" and "Turing-incomplete C99". Based on part 2, a compiler can choose to allow allocating 1.5 GiB if sizeof(void*) is not actually observed by the specific source code, and 0.5 GiB if it appears. glibc 2.32 did similar to detect threads. Part 4 will be a compiler allocating 16 GiB max with an unmet condition, and infinite memory when satisfied.
Physics doesn't matter for abstract C99. Real numbers are too and unstoreable but still studied. Likewise, a C99-conformant Turing-complete compiler is discussable. glibc's malloc uses mmap via sysenter. An everything-is-a-file platform without sysenter may require read and write to call mmap. Note that the platform, not our C program, calls those functions, so we stay within the other question's only putchar / getchar / standard functions restriction. A 32-bit 2 GiB platform may read and write to disk for 32 GiB memory and software-emulate 64-bit pointers. The abstract C99 machine is in theoretical space, so isn't prevented from containing a Turing machine. Its compiler can optimize tape.c into interactions with said ideal Turing machine and still conform to the C99 standard.
Remember from part 2, the implementation can refuse allocating any amount, such as beyond 2 GiB despite 32 GiB available. Again, it's only meaningful to ask "What is the limit of the largest, as we consider more abstract executions of valid terminating programs, across more compilations by all abstract compilers, sum of malloc invocations that succeeded?".
Part 4: Unexposed allocations under compilers using pointer providence
Why was the static in static struct node * cur = malloc(sizeof(node)); so important? Let's summarize N2676:
- The Abstract Machine has a global list of all “exposed” allocations
- Allocations come into the world unexposed (unaliased)
- Casting a pointer to an integer exposes the allocation for that pointer’s provenance
- Casting an integer to a pointer does a global hittest on all exposed allocations
- If you hit an exposed allocation, congrats! You get provenance to it.
- If you hit two exposed allocations (because of one-past-the-end), be sad and tell the programmer to “just be consistent” and only access one of them.
An implementation can have part 1's "global lookup table for casting" be the "global list of all “exposed” allocations". static in tape.c means no other files can reference cur, so the compiler can closed-world analyse. There's provably no "casting of a pointer to an integer" that "exposes the allocation for that pointer’s provenance". It only has unexposed allocations, occupying zero space in the global list. Therefore, I can allocate n max, conditional on not overflowing uintptr_t's capacity, i.e. $n * 0 < \texttt{SIZE_MAX}$. The indeterminate $\infty * 0$ becomes $0$ because the allocations are ordered. Therefore, an ideal optimizing compiler is allowed to give us the infinite tape required for our Turing machine!
The C standard doesn't say we can examine a running program's internal memory. If you insist, then before we look we might observe an unlimited number of bytes allocated successfully, then after we look, only a finite number of bytes can be allocated before crashing. Remember malloc is nondeterministic. Since the time before looking is arbitrary, we could wait infinitely long to look so that the program may allocate infinite memory.
TL;DR
- An abstract standard-compliant C compiler can choose to let your program be Turing-complete
- Neither you nor the rest of the program may observe the internals of
tape.c while it runs
- That compiler won't work on the computers in our universe, but it should work in the theoretical mathematical space of the C standard
#pragmais allowed, an implementation can be Turing-complete trivially. – johnchen902 Jan 11 '18 at 04:51