4 ms·

If you're being that pedantic, C itself is not Turing-complete in the first place: pointers have finite size, which means that C can address only a bounded amou

If you're being that pedantic, C itself is not Turing-complete in the first place: pointers have finite size, which means that C can address only a bounded amount of memory, so it is a finite state machine (just with an extremely large number of states).

tgv 3y ago
I don't think it's about that. Technically, everything is finite. But placing limits on the loops and restricting memory allocation bounds the complexity. It probably limits everything to P-time.
- l33t233372 3y ago
  When everything is finite and memory is always limited, what are you meaningfully saying about the possible behaviors of software here?
- c_crank 3y ago
  Bounding the complexity is desirable for a system that should never fail due to software errors.
- adrianN 3y ago
  You can easily have bounded loops and superexponential runtime.
  - tgv 3y ago
    Without dynamic memory allocation? I think you'd need at least O(n) memory to store enough state to go exponential. But it's some time I did complexity theory; I could be wrong.
    - adrianN 3y ago
      Unless your input is read-only you should always have O(n) memory available.