Hacker News new | ask | show | jobs
by Retra 4048 days ago
You can write a program that doesn't terminate, consumes ever increasing amounts of memory, and can perform arbitrary arithmetical calculations in just about any language. Any language that can do that is Turing complete.

About the only non-Turing complete languages in wide use today are basic dialects of SQL, Regex, and some layout engines. Every non-Turing complete language we've invented has a very specific domain of application, and none of them are suitable for writing low-level systems.

1 comments

I think you missed my point, which I admit is rather subtle. I mean that there are already restrictions which we place on programs in practice; if we make those explicitly part of the language rather than implicitly part of the environment, the resulting language is not Turing complete but might still be comparably useful. The trick is in doing this in a way that practically (instead of just theoretically) improves our ability to reason about the programs, and in building it into a language that's actually usable.

Edited to add: Note that I'm not saying this is a trivial engineering exercise.