5 ms·

By disallowing recursion and requiring loops to have a fixed upper bound, you’ve defined a subset of C that is less than Turning complete.

jcranmer 3y ago
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.
deleted 3y ago
[deleted]
AnimalMuppet 3y ago
Yes. And by doing so (and by removing recursion), you are also making the Halting Problem decidable.
- hedora 3y ago
  Rule 5 prohibits programs that average less than two undecidable branches per function.
adrianN 3y ago
How many problems in safety critical systems need Turing completeness and how many are fine with something weaker eg primitive recursion? My intuition is that most things are fine without full Turing completeness (as far as you can even apply terms about computability to systems with complex IO behavior)
- marcosdumay 3y ago
  > How many problems in safety critical systems need Turing completeness Probably all, like the ones outside of critical systems. But if you concentrate the complex behavior in a single layer, you will probably get a very thin layer, that you can call an OS or something like that, verify it very well, and have almost all the code follow a non-complete idiom.
  - adrianN 3y ago
    I have worked on a safety critical system and can't recall a part that needed Turing completeness.
    - marcosdumay 3y ago
      What starts your safety critical code?
      - adrianN 3y ago
        Some part of the hardware starts executing the code at some fixed address when the system is powered on. I don't know the details, I only do software.
zokier 3y ago
That is a good thing, right? Turing completeness is rarely a desirable property

jcranmer 3y ago

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.

deleted 3y ago

[deleted]

AnimalMuppet 3y ago

Yes. And by doing so (and by removing recursion), you are also making the Halting Problem decidable.

hedora 3y ago
Rule 5 prohibits programs that average less than two undecidable branches per function.

adrianN 3y ago

How many problems in safety critical systems need Turing completeness and how many are fine with something weaker eg primitive recursion? My intuition is that most things are fine without full Turing completeness (as far as you can even apply terms about computability to systems with complex IO behavior)

marcosdumay 3y ago
> How many problems in safety critical systems need Turing completeness Probably all, like the ones outside of critical systems. But if you concentrate the complex behavior in a single layer, you will probably get a very thin layer, that you can call an OS or something like that, verify it very well, and have almost all the code follow a non-complete idiom.
- adrianN 3y ago
  I have worked on a safety critical system and can't recall a part that needed Turing completeness.
  - marcosdumay 3y ago
    What starts your safety critical code?
    - adrianN 3y ago
      Some part of the hardware starts executing the code at some fixed address when the system is powered on. I don't know the details, I only do software.

zokier 3y ago

That is a good thing, right? Turing completeness is rarely a desirable property