3 ms·

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

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...
        camel-cdr 4y ago
        > ...thus there is a limit to how many bits fpos_t may contain Yes, but my point was that a `fgetpos` mustn't work for all FILE pointers, take for example `stdin`. The standard quotes from my above comment show that a FILE pointer mustn't support “positioning requests”, so fgetpos mustn't work.
  - _gabe_ 4y ago
    A pointer is just a number that points to addressable memory. Pointers don't even point to actual memory these days anyways. They're just glorified indices into OS tables that eventually map to actual memory. You can increase a pointer to be 128 bits big, or 256 bits big if you wanted to. It doesn't change anything, because it's just an index. Here's a clarification on Wikipedia that expands on this: > nearly all programming languages are Turing complete if the limitations of finite memory are ignored. And files are just as finite as a pointer. You can't address a location in a file bigger than sizeof(void*) on a modern computer. If you wanted to, you would need to add special support[1] and doing this is equivalent to what you would do to support a bigger memory range for pointers. I'm curious, do you think other languages are Turing complete? As far as I know, all modern programming languages use a 64 bit addressable memory space maximum. [0]: https://en.m.wikipedia.org/wiki/Turing_machine https://en.m.wikipedia.org/wiki/Turing_machine [1]: https://stackoverflow.com/questions/4933561/what-is-the-relation-betwenn-file-pointer-width-and-maximum-file-size https://stackoverflow.com/questions/4933561/what-is-the-rela...
    - camel-cdr 4y ago
      > You can increase a pointer to be 128 bits big, or 256 bits big if you wanted to. It doesn't change anything, because it's just an index. Yes, you can increase the pointer size arbitrarily, but it is always constant for a single C implementation, you can't increase the pointer size at run time. Essentially you recompiling and running a program and choosing an implementation with a successively larger pointer size is Turing complete, but it requires you as a special actor, and I'm only concerned for a what a single implementation can do. To put it in another way, solving the halting problem is trivial for any C program + a fixed C implementation, that doesn't have special language extensions. > I'm curious, do you think other languages are Turing complete? The easiest example would be brainfuck, because you can just move the tape around in it, and a theoretical implementation could trivially be hoked up to a theoretical infinite tape. > As far as I know, all modern programming languages use a 64 bit addressable memory space maximum I don't know enough about how other languages are defined, but I could imagine that Java allows for an implementation with infinite memory, because it doesn't impose any requirements on how the pointers are implemented under the hood.
kps 4y ago
The tape wouldn't have to be provided as a single flat file. You could, for instance, use something like a pair of files, one for control and one for data: fputc('L', tape_control); c = fgetc(tape_data); fputc(d, tape_data); or a single file with controls disjoint from the tape symbols.
- camel-cdr 4y ago
  This would be possible, but it feels like cheating :-) Idk how to express this properly, but I feel like there is a difference between this and the fseek approach. In a similar vain, you could say that a certain kind of undefined behavior controls the tape, or writing to a specific part of memory does. I suppose this would fall under adding additional compiler extension.
  - kps 4y ago
    > … or writing to a specific part of memory does. Memory-mapped devices are pretty common. C's original platform controlled tape drives by writing to memory: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/sys/dev/tc.c https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/sys/dev/tc...

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...
      - camel-cdr 4y ago
        > ...thus there is a limit to how many bits fpos_t may contain Yes, but my point was that a `fgetpos` mustn't work for all FILE pointers, take for example `stdin`. The standard quotes from my above comment show that a FILE pointer mustn't support “positioning requests”, so fgetpos mustn't work.
- _gabe_ 4y ago
  A pointer is just a number that points to addressable memory. Pointers don't even point to actual memory these days anyways. They're just glorified indices into OS tables that eventually map to actual memory. You can increase a pointer to be 128 bits big, or 256 bits big if you wanted to. It doesn't change anything, because it's just an index. Here's a clarification on Wikipedia that expands on this: > nearly all programming languages are Turing complete if the limitations of finite memory are ignored. And files are just as finite as a pointer. You can't address a location in a file bigger than sizeof(void*) on a modern computer. If you wanted to, you would need to add special support[1] and doing this is equivalent to what you would do to support a bigger memory range for pointers. I'm curious, do you think other languages are Turing complete? As far as I know, all modern programming languages use a 64 bit addressable memory space maximum. [0]: https://en.m.wikipedia.org/wiki/Turing_machine https://en.m.wikipedia.org/wiki/Turing_machine [1]: https://stackoverflow.com/questions/4933561/what-is-the-relation-betwenn-file-pointer-width-and-maximum-file-size https://stackoverflow.com/questions/4933561/what-is-the-rela...
  - camel-cdr 4y ago
    > You can increase a pointer to be 128 bits big, or 256 bits big if you wanted to. It doesn't change anything, because it's just an index. Yes, you can increase the pointer size arbitrarily, but it is always constant for a single C implementation, you can't increase the pointer size at run time. Essentially you recompiling and running a program and choosing an implementation with a successively larger pointer size is Turing complete, but it requires you as a special actor, and I'm only concerned for a what a single implementation can do. To put it in another way, solving the halting problem is trivial for any C program + a fixed C implementation, that doesn't have special language extensions. > I'm curious, do you think other languages are Turing complete? The easiest example would be brainfuck, because you can just move the tape around in it, and a theoretical implementation could trivially be hoked up to a theoretical infinite tape. > As far as I know, all modern programming languages use a 64 bit addressable memory space maximum I don't know enough about how other languages are defined, but I could imagine that Java allows for an implementation with infinite memory, because it doesn't impose any requirements on how the pointers are implemented under the hood.

kps 4y ago

The tape wouldn't have to be provided as a single flat file. You could, for instance, use something like a pair of files, one for control and one for data: fputc('L', tape_control); c = fgetc(tape_data); fputc(d, tape_data); or a single file with controls disjoint from the tape symbols.

camel-cdr 4y ago
This would be possible, but it feels like cheating :-) Idk how to express this properly, but I feel like there is a difference between this and the fseek approach. In a similar vain, you could say that a certain kind of undefined behavior controls the tape, or writing to a specific part of memory does. I suppose this would fall under adding additional compiler extension.
- kps 4y ago
  > … or writing to a specific part of memory does. Memory-mapped devices are pretty common. C's original platform controlled tape drives by writing to memory: https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/sys/dev/tc.c https://www.tuhs.org/cgi-bin/utree.pl?file=V7/usr/sys/dev/tc...