5 ms·
We are doing this already. - Configuration languages (JSON, YAML, XML) are pure combinatorial logic. - Regular expressions are... mostly not actually regular,
by qsort 5y ago
We are doing this already.
- Configuration languages (JSON, YAML, XML) are pure combinatorial logic.
- Regular expressions are... mostly not actually regular, but you get the idea.
- Some templating languages are deliberately less powerful than Turing machines, e.g. ST4 is context-free.
- Prepared SQL statements are a similar idea on a different axis.
The real question is whether a non-TC language could be useful for general purpose programming. Such a language might come with very strong guarantees (termination, time complexity, even correctness or a limited form of correctness), but they might be extra-cumbersome for 'normal' workloads.
- ludamad 5y agoA non-TC language can be achieved just by forcing proofs. Oh, you want that program to run? Just prove that it is bounded memory and can't halt, etc
- qsort 5y agoYeah, but that's the 'cumbersome' part. Could we imagine a non-TC language with simple syntax that's suitable for at least some of the task you'd use a TC language for?
- magmastonealex 5y agoC compiled down to eBPF (as implemented with the Linux kernel) is not turing-complete. eBPF has a wide variety of uses from network filtering to hooking into certain syscalls. The bytecode is theoretically turing-complete, but the verifier present in the kernel ensures that the code contains no loops and accesses no out-of-bounds memory. With `clang`, you can compile C down to eBPF bytecode. It's a subset of C, with a lot of restrictions, but it is familiar and capable of some remarkable things past just simple packet parsing & filtering.
- qsort 5y agoI had no idea, this is fascinating. Thanks for sharing.
- UncleMeat 5y agoA useful subset of SQL is not turing-complete and is suitable for meaningful computational tasks. Datalog is also not turing-complete and is similarly useful.
- qsort 5y agoSure, more examples are CSP solvers and AMPL. They are all somewhat specific though. I was wondering if it would be possible to make one that's "general purpose" in the same sense you call programming languages "general purpose", i.e. one you'd write application software in.
- UncleMeat 5y agoDatalog would be the closest I can think of. A bunch of static analysis engines are implemented in it.