Hacker News Reader

Comment by MatthiasPortzel | Hacker News Reader

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.

View on HN

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).

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.

You can easily have bounded loops and superexponential runtime.

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.

Unless your input is read-only you should always have O(n) memory available.

When everything is finite and memory is always limited, what are you meaningfully saying about the possible behaviors of software here?

Bounding the complexity is desirable for a system that should never fail due to software errors.

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)

> 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.

I have worked on a safety critical system and can't recall a part that needed Turing completeness.

What starts your safety critical code?

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.

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

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

Rule 5 prohibits programs that average less than two undecidable branches per function.

Reply on news.ycombinator.com