6 ms·

This is only tangential to the article: C isn't Turing complete without `fseek` (as far as I can tell). Turing completes requires you to be able to read/write

This is only tangential to the article: C isn't Turing complete without `fseek` (as far as I can tell). Turing completes requires you to be able to read/write from an infinite tape (essentially infinite memory). This isn't possible in C, because `sizeof` is a constant expression, thus limiting the size of any type, and importantly also pointer type, to a finite number, thus making the addressable memory finite. From what I can tell, the only way you could theoretically access an infinite tape is using `fseek` with `SEEK_CUR`. There might be more shenanigans possible with `stdio.h`, but I'm pretty sure C can't be Turing complete without the `stdio.h` function (assuming no special language extensions). If anybody is wondering, the preprocessor isn't Turing complete either, because you might theoretically have infinite memory, but then you only have finite recursion, which also isn't enough for Turing completeness. File iteration can have infinite recursion, but can also only carry over finite state between `#include`s. Edit: I'm not talking about any real world implementation, but rather about the theoretical bounds of the C abstract machine.

dmitrygr 4y ago
Your argument sort of imploded on itself…your claim that only a file can be considered tape is insane because memory is just as usable as tape and you can keep extending memory available to you using sbrk() . If you’re going to claim the memory is finite, well so are files. (Also lseek is not part of any C spec) And yes neither is infinite, so every computer is just a DFA, and lseek changes nothing. But given the amount of memory that exists we approximate and say they are Turing machines since there is enough memory to do most what we need.
- camel-cdr 4y ago
  My argument is that `fseek` (not `lseek`) is the only way for standard C to access a infinite tape, because it allows relative seeking in a file. `fseek(file, 1, SEEK_CUR)` to advance and `fseek(file, -1, SEEK_CUR)` to go back.
  - dmitrygr 4y ago
    Pointer++ Pointer—- These do the same to pointers…
    - camel-cdr 4y ago
      No, pointers always have a finite size, because sizeof is a constant expression. A theoretically fseek isn't bound by this, the compiler could implement it with an infinite tape.
      - dmitrygr 4y ago
        You’re spouting nonsense. File offset is guaranteed to be expressible by the integral type off_t. Thus also limited.
        camel-cdr 4y ago
        You are aware that `off_t` isn't in the C standard? The standard has `fgetpos`: > The fgetpos function stores the current values of the parse state (if any) and file position indicator for the stream pointed to by stream in the object pointed to by pos > If a file can support positioning requests (such as a disk file, as opposed to a terminal), then a file position indicator associated with the stream is positioned at the start (character number zero) of the file, unless the file is opened with append mode in which case it is implementation-defined whether the file position indicator is initially positioned at the beginning or the end of the file. Meaning `fgetpos` mustn't work for files that don't support `positioning requests`, whiles relative offsets using `fseek` could still work.
        dmitrygr 4y ago
        ok, that is just more nonsense... but let's go with that. fgetpos stores offset in an fpos_t object...in memory...memory is finite as you admit...thus the length of this fpos_t object must be finite...thus there is a limit to how many bits fpos_t may contain, thus it can address only finite file length...
munificent 4y ago
You could just make a doubly-linked list that dynamically grows new nodes (using malloc()) at either end on demand in order to implement an infinite tape. (Of course on a real machine the malloc() will fail at some point.)
- camel-cdr 4y ago
  My point was that this isn't possible, because the addressable memory, whiles possible humongous, is always finite, because the sizeof pointers is constant. So at some point `malloc` must return the same address, even if you had theoretically infinite memory available, there is no way to address that in C.
  - munificent 4y ago
    Ah, good point!
arcbyte 4y ago
You are pedantically correct and wrong. Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory. Rather than go so esoteric as to say that only programs structured with fseek are Turing complete, we generally just make the jump from languages able to use arbitrarily sized RAM to assuming infinite RAM and say youre turing complete enough for most purposes.
- camel-cdr 4y ago
  > Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory I should've explained that I'm not talking about a physical implementation, but about the theoretical bounds of the C abstract machine.
  - Phrodo_00 4y ago
    Talking theoretically, since size_t is defined as: > size_t can store the maximum size of a theoretically possible object of any type (including array). In a proper theoretical turing machine, size_t would allow you to create and address arbitrarily large arrays too.
    - camel-cdr 4y ago
      `sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite. For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).
      - Phrodo_00 4y ago
        Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity. So, I don't think it having to be a constant is a problem as much as having to deal with infinitely big numbers inside of infinite memory (which may or may not be a contradiction, depending on axioms used to define a turing machine. I still need to work my way through annotated turing). Of course, things do get a lot simpler and grounded using IO functions like you said earlier.
wgd 4y ago
The issue of memory bounds is commonly handwaved away. Note that your desktop computer is technically not Turing complete either, since it only has access to a finite amount of memory+disk storage, and is thus a (very large) finite state machine since there are only a finite number of states it can be in.
deleted 4y ago
[deleted]
jwilk 4y ago
See "Subtleties of the ANSI/ISO C standard" <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf>, section V "C is not Turing complete". They discuss file I/O briefly too, but I don't follow their reasoning.
- camel-cdr 4y ago
  Yes, this is basically my argument. They address that `ftell` must return a finite value, but don't mention that `ftell` can fail for specific FILEs: > If successful, the ftell function returns the current value of the file position indicator for the stream But FILEs don't necessarily have a "file position indicator": > If a file can support positioning requests (such as a disk file, as opposed to a terminal), then a file position indicator associated with the stream is positioned at the start (character number zero) of the file, unless the file is opened with append mode in which case it is implementation-defined whether the file position indicator is initially positioned at the beginning or the end of the file. They don't seem to discuss the topic further. > Therefore we will here only consider C programs without I/O. (Our argument can be adapted to show that the programs that restrict I/O to reading stdin and writing stdout are Turing incomplete as well, but we will not do so here.) So they don't address the problem of IO completely.
lelanthran 4y ago
> This isn't possible in C, because `sizeof` is a constant expression, thus limiting the size of any type, and importantly also pointer type, to a finite number, thus making the addressable memory finite. Who said it had to be finite in theory? `size_t` is defined in terms of the implementation, not in terms of bit-widths. Sure, size_t is finite in practice, but then again, so are all other programming languages. In theory, there is no upper limit on size_t.
- camel-cdr 4y ago
  `size_t` is defined as > the unsigned integer type of the result of the sizeof operator (https://port70.net/~nsz/c/c11/n1570.html#7.19p2 https://port70.net/~nsz/c/c11/n1570.html#7.19p2) `sizeof` returns the following: > If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant. (https://port70.net/~nsz/c/c11/n1570.html#6.5.3.4p2 https://port70.net/~nsz/c/c11/n1570.html#6.5.3.4p2) So `sizeof(size_t)` must be a concrete integer constant for any given C implementation, it can't change at runtime. As far as I'm aware, there isn't an instance of an infinitely large integer, even in mathematics, there are finite integers and there is the concept of infinity.
  - lelanthran 4y ago
    > So `sizeof(size_t)` must be a concrete integer constant for any given C implementation, it can't change at runtime. I didn't say it has to change at runtime, I said that there is no upper limit on it in theory, because the upper limit is specified in terms of the implementation, and a a theoretical implementation with no upper limit on memory means that there is no upper limit on size_t. Besides, I also said: > Sure, size_t is finite in practice, but then again, so are all other programming languages. Using your definition of Turing complete (no upper limit on pointer, references or addresses), I cannot think of one popular language that would satisfy that definition. Can you?
    - camel-cdr 4y ago
      The easiest example would be brainfuck, which doesn't have addresses and you just move the tape head. I'm not that versed in how other languages are defined, but does e.g. JavaScript even expose pointers to the user? From my understanding of the language, an implementation could be able to allocate infinitely many objects, without breaking the language spec.
cypress66 4y ago
I'm sure someone more knowledgeable will point out the flaw, but couldn't Turing's machine definition be changed from infinite tape, to arbitrarily large tape, and thus solve this technicality?
- camel-cdr 4y ago
  Let me put it that way. Given any theoretical C implementation and a strictly confirming program (that doesn't do io) I can theoretically trivially solve the halting problem. Since the possible memory is constant for any given implementation, I can use the following algorithm: 1. Execute one instruction of the program 2. If the program terminated, goto 4. 3. insert entire program state into a hash table if it is already in the hash table, goto 5. otherwise, goto 1. 4. The Program terminates 5. The program never terminates The above algorithm solves the halting problem of any C program with a constant memory bound in finite time.
GabrielTFS 4y ago
If you want to talk about this kind of technicality, here are three other avenues through which I believe Turing completeness of C can be achieved: 1. As https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm helpfully points out, "If two objects have identical bit-pattern representations and their types are the same they may still compare as unequal", and "[implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical". It can thus be argued that, with a rather strict definition of provenance (i.e. how pointer values may be constructed), one could construct an implementation where every byte of every pointer is tagged with additional unbounded data that lets the whole pointer be properly dereferenced (I say every byte so that you're able to convert the pointer to an integer and convert it back to the same valid pointer), and where, as allowed by DR 260, pointers that have identical observable bit-pattern representations might not compare equal if they point to different objects. Thus, that implementation could create an unbounded amount of pointers. 2. Spawning off another thread and using infinite recursion (C has no defined recursion depth limit, and if you want to argue about automatic variables needing addresses or whatever and that the as-if rule doesn't cover that, there's `register` which makes address-less variables) to have two pushdown automatas that can together work as a Turing Machine. 3. Using variadic arguments. With `va_copy`, one can iterate through variadic arguments multiple times, and thus `va_list` can be used to implement a mechanism equivalent to pointers without actual pointers (any sane implementation probably uses a pointer for `va_list` somewhere in it, but that's not a problem here) and thus make a pushdown automata with 2 stacks
- camel-cdr 4y ago
  Let me address 2. and 3. first, because 1. is probably correct. 2. The problem with that is that you may have infinite recursion, but you can only pass finite amounts of memory between recursion steps. This has also been addressed by https://cs.stackexchange.com/a/60978 https://cs.stackexchange.com/a/60978. 3. I don't follow, how could you create a growing `va_list`? Edit: Actually, I think I do now, so you essentially create a sort of linked list of `va_list`s? 1. This is probably correct. You'd need to be able to round trip through a void*, but that could still be implemented to retain the tagged data. I thought of pointer tagging more in terms of marking addresses with certain memory protection properties, but what you suggest should be possible. There may still be some wording disallowing it, but I couldn't find it.

dmitrygr 4y ago

Your argument sort of imploded on itself…your claim that only a file can be considered tape is insane because memory is just as usable as tape and you can keep extending memory available to you using sbrk() . If you’re going to claim the memory is finite, well so are files. (Also lseek is not part of any C spec) And yes neither is infinite, so every computer is just a DFA, and lseek changes nothing. But given the amount of memory that exists we approximate and say they are Turing machines since there is enough memory to do most what we need.

camel-cdr 4y ago
My argument is that `fseek` (not `lseek`) is the only way for standard C to access a infinite tape, because it allows relative seeking in a file. `fseek(file, 1, SEEK_CUR)` to advance and `fseek(file, -1, SEEK_CUR)` to go back.
- dmitrygr 4y ago
  Pointer++ Pointer—- These do the same to pointers…
  - camel-cdr 4y ago
    No, pointers always have a finite size, because sizeof is a constant expression. A theoretically fseek isn't bound by this, the compiler could implement it with an infinite tape.
    - dmitrygr 4y ago
      You’re spouting nonsense. File offset is guaranteed to be expressible by the integral type off_t. Thus also limited.
      - camel-cdr 4y ago
        You are aware that `off_t` isn't in the C standard? The standard has `fgetpos`: > The fgetpos function stores the current values of the parse state (if any) and file position indicator for the stream pointed to by stream in the object pointed to by pos > If a file can support positioning requests (such as a disk file, as opposed to a terminal), then a file position indicator associated with the stream is positioned at the start (character number zero) of the file, unless the file is opened with append mode in which case it is implementation-defined whether the file position indicator is initially positioned at the beginning or the end of the file. Meaning `fgetpos` mustn't work for files that don't support `positioning requests`, whiles relative offsets using `fseek` could still work.
        dmitrygr 4y ago
        ok, that is just more nonsense... but let's go with that. fgetpos stores offset in an fpos_t object...in memory...memory is finite as you admit...thus the length of this fpos_t object must be finite...thus there is a limit to how many bits fpos_t may contain, thus it can address only finite file length...

munificent 4y ago

You could just make a doubly-linked list that dynamically grows new nodes (using malloc()) at either end on demand in order to implement an infinite tape. (Of course on a real machine the malloc() will fail at some point.)

camel-cdr 4y ago
My point was that this isn't possible, because the addressable memory, whiles possible humongous, is always finite, because the sizeof pointers is constant. So at some point `malloc` must return the same address, even if you had theoretically infinite memory available, there is no way to address that in C.
- munificent 4y ago
  Ah, good point!

arcbyte 4y ago

You are pedantically correct and wrong. Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory. Rather than go so esoteric as to say that only programs structured with fseek are Turing complete, we generally just make the jump from languages able to use arbitrarily sized RAM to assuming infinite RAM and say youre turing complete enough for most purposes.

camel-cdr 4y ago
> Even with fseek there are only so many atoms in the universe and you'd eventually run into limited memory I should've explained that I'm not talking about a physical implementation, but about the theoretical bounds of the C abstract machine.
- Phrodo_00 4y ago
  Talking theoretically, since size_t is defined as: > size_t can store the maximum size of a theoretically possible object of any type (including array). In a proper theoretical turing machine, size_t would allow you to create and address arbitrarily large arrays too.
  - camel-cdr 4y ago
    `sizeof(size_t)` and `size_t x; sizeof x` must be constant expressions. It is possible to create a c implementation where the size of a pointer is arbitrarily large, but it can't grow/isn't infinite. For any give C implementation, it is thus trivial to theoretically solve the halting problem (assuming no stdio.h stuff is used).
    - Phrodo_00 4y ago
      Speaking in so much the abstract that it becomes absurd (which also can be used to prove your point, but bear with me here), since `size_t` is required to hold the size of any object, and a turing machine has infinite memory, then size_t would also need to be infinitely big, and `sizeof(size_t)` would be a constant returning infinity. So, I don't think it having to be a constant is a problem as much as having to deal with infinitely big numbers inside of infinite memory (which may or may not be a contradiction, depending on axioms used to define a turing machine. I still need to work my way through annotated turing). Of course, things do get a lot simpler and grounded using IO functions like you said earlier.

wgd 4y ago

The issue of memory bounds is commonly handwaved away. Note that your desktop computer is technically not Turing complete either, since it only has access to a finite amount of memory+disk storage, and is thus a (very large) finite state machine since there are only a finite number of states it can be in.

deleted 4y ago

[deleted]

jwilk 4y ago

See "Subtleties of the ANSI/ISO C standard" <https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf https://www.open-std.org/jtc1/sc22/wg14/www/docs/n1637.pdf>, section V "C is not Turing complete". They discuss file I/O briefly too, but I don't follow their reasoning.

camel-cdr 4y ago
Yes, this is basically my argument. They address that `ftell` must return a finite value, but don't mention that `ftell` can fail for specific FILEs: > If successful, the ftell function returns the current value of the file position indicator for the stream But FILEs don't necessarily have a "file position indicator": > If a file can support positioning requests (such as a disk file, as opposed to a terminal), then a file position indicator associated with the stream is positioned at the start (character number zero) of the file, unless the file is opened with append mode in which case it is implementation-defined whether the file position indicator is initially positioned at the beginning or the end of the file. They don't seem to discuss the topic further. > Therefore we will here only consider C programs without I/O. (Our argument can be adapted to show that the programs that restrict I/O to reading stdin and writing stdout are Turing incomplete as well, but we will not do so here.) So they don't address the problem of IO completely.

lelanthran 4y ago

> This isn't possible in C, because `sizeof` is a constant expression, thus limiting the size of any type, and importantly also pointer type, to a finite number, thus making the addressable memory finite. Who said it had to be finite in theory? `size_t` is defined in terms of the implementation, not in terms of bit-widths. Sure, size_t is finite in practice, but then again, so are all other programming languages. In theory, there is no upper limit on size_t.

camel-cdr 4y ago
`size_t` is defined as > the unsigned integer type of the result of the sizeof operator (https://port70.net/~nsz/c/c11/n1570.html#7.19p2 https://port70.net/~nsz/c/c11/n1570.html#7.19p2) `sizeof` returns the following: > If the type of the operand is a variable length array type, the operand is evaluated; otherwise, the operand is not evaluated and the result is an integer constant. (https://port70.net/~nsz/c/c11/n1570.html#6.5.3.4p2 https://port70.net/~nsz/c/c11/n1570.html#6.5.3.4p2) So `sizeof(size_t)` must be a concrete integer constant for any given C implementation, it can't change at runtime. As far as I'm aware, there isn't an instance of an infinitely large integer, even in mathematics, there are finite integers and there is the concept of infinity.
- lelanthran 4y ago
  > So `sizeof(size_t)` must be a concrete integer constant for any given C implementation, it can't change at runtime. I didn't say it has to change at runtime, I said that there is no upper limit on it in theory, because the upper limit is specified in terms of the implementation, and a a theoretical implementation with no upper limit on memory means that there is no upper limit on size_t. Besides, I also said: > Sure, size_t is finite in practice, but then again, so are all other programming languages. Using your definition of Turing complete (no upper limit on pointer, references or addresses), I cannot think of one popular language that would satisfy that definition. Can you?
  - camel-cdr 4y ago
    The easiest example would be brainfuck, which doesn't have addresses and you just move the tape head. I'm not that versed in how other languages are defined, but does e.g. JavaScript even expose pointers to the user? From my understanding of the language, an implementation could be able to allocate infinitely many objects, without breaking the language spec.

cypress66 4y ago

I'm sure someone more knowledgeable will point out the flaw, but couldn't Turing's machine definition be changed from infinite tape, to arbitrarily large tape, and thus solve this technicality?

camel-cdr 4y ago
Let me put it that way. Given any theoretical C implementation and a strictly confirming program (that doesn't do io) I can theoretically trivially solve the halting problem. Since the possible memory is constant for any given implementation, I can use the following algorithm: 1. Execute one instruction of the program 2. If the program terminated, goto 4. 3. insert entire program state into a hash table if it is already in the hash table, goto 5. otherwise, goto 1. 4. The Program terminates 5. The program never terminates The above algorithm solves the halting problem of any C program with a constant memory bound in finite time.

GabrielTFS 4y ago

If you want to talk about this kind of technicality, here are three other avenues through which I believe Turing completeness of C can be achieved: 1. As https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm https://www.open-std.org/jtc1/sc22/wg14/www/docs/dr_260.htm helpfully points out, "If two objects have identical bit-pattern representations and their types are the same they may still compare as unequal", and "[implementations] may also treat pointers based on different origins as distinct even though they are bitwise identical". It can thus be argued that, with a rather strict definition of provenance (i.e. how pointer values may be constructed), one could construct an implementation where every byte of every pointer is tagged with additional unbounded data that lets the whole pointer be properly dereferenced (I say every byte so that you're able to convert the pointer to an integer and convert it back to the same valid pointer), and where, as allowed by DR 260, pointers that have identical observable bit-pattern representations might not compare equal if they point to different objects. Thus, that implementation could create an unbounded amount of pointers. 2. Spawning off another thread and using infinite recursion (C has no defined recursion depth limit, and if you want to argue about automatic variables needing addresses or whatever and that the as-if rule doesn't cover that, there's `register` which makes address-less variables) to have two pushdown automatas that can together work as a Turing Machine. 3. Using variadic arguments. With `va_copy`, one can iterate through variadic arguments multiple times, and thus `va_list` can be used to implement a mechanism equivalent to pointers without actual pointers (any sane implementation probably uses a pointer for `va_list` somewhere in it, but that's not a problem here) and thus make a pushdown automata with 2 stacks

camel-cdr 4y ago
Let me address 2. and 3. first, because 1. is probably correct. 2. The problem with that is that you may have infinite recursion, but you can only pass finite amounts of memory between recursion steps. This has also been addressed by https://cs.stackexchange.com/a/60978 https://cs.stackexchange.com/a/60978. 3. I don't follow, how could you create a growing `va_list`? Edit: Actually, I think I do now, so you essentially create a sort of linked list of `va_list`s? 1. This is probably correct. You'd need to be able to round trip through a void*, but that could still be implemented to retain the tagged data. I thought of pointer tagging more in terms of marking addresses with certain memory protection properties, but what you suggest should be possible. There may still be some wording disallowing it, but I couldn't find it.