5 ms·

Sure this CVE sounds like a joke but if you create a programming language that is non Turing complete it is much easier to secure than a Turing complete languag

Sure this CVE sounds like a joke but if you create a programming language that is non Turing complete it is much easier to secure than a Turing complete language. Making a language that have the expressive power of finite state machines could be an example.

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 ago
  A 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 ago
    Yeah, 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 ago
      C 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 ago
        I had no idea, this is fascinating. Thanks for sharing.
    - UncleMeat 5y ago
      A 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 ago
        Sure, 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 ago
        Datalog would be the closest I can think of. A bunch of static analysis engines are implemented in it.
tester34 5y ago
What does Turing completness even mean in practice when it comes to non-theoretical languages?
- zitterbewegung 5y ago
  You can't do anything like recursion.
  - klyrs 5y ago
    I spent a while trying to parse this, and it doesn't make a lick of sense. Brainfuck is a classical example of a turing complete language that doesn't have a notion of functions. What does "recursion" mean here? Nothing, I think. So you don't need recursion for Turing completeness. Some people work on languages that support functions as first class objects, which don't natively support recursion. This is nice from a language design standpoint, because functions only see the scope of their arguments and can't look any further. The "Y Combinator" pattern is used to bootstrap recursion into these languages. You may have heard of it. Turing-incomplete languages can also support unlimited recursion. For example, take a Turing complete language, and equip it with a state of the art theorem prover. Before entering a loop, or calling a function, the theorem prover is allowed to spend up to 1 minute proving that the loop or function call will terminate. If the theorem prover times out, the program halts with an error. Some functions, such as a naive implementation of factorial, can be easily proved to halt for all inputs. So this language allows recursion, but by construction, all programs terminate, so it's turing incomplete.
    - mousepilot 5y ago
      I'm not that great a programmer, but this one seems easy to me, you write an interpreter in brainfuck that allows function definitions that support recursion, then include your recursive function definitions as an included constant then point your interpreter at the constant and tell it to run it. I assume bf allows constants but like I said I'm not that great a programmer. Obviously using a recursive descent parser is out but thats probably easy to work around right? I could be wrong tho so don't base mission critical code on this without rigorous testing!

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 ago
A 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 ago
  Yeah, 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 ago
    C 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 ago
      I had no idea, this is fascinating. Thanks for sharing.
  - UncleMeat 5y ago
    A 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 ago
      Sure, 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 ago
        Datalog would be the closest I can think of. A bunch of static analysis engines are implemented in it.

tester34 5y ago

What does Turing completness even mean in practice when it comes to non-theoretical languages?

zitterbewegung 5y ago
You can't do anything like recursion.
- klyrs 5y ago
  I spent a while trying to parse this, and it doesn't make a lick of sense. Brainfuck is a classical example of a turing complete language that doesn't have a notion of functions. What does "recursion" mean here? Nothing, I think. So you don't need recursion for Turing completeness. Some people work on languages that support functions as first class objects, which don't natively support recursion. This is nice from a language design standpoint, because functions only see the scope of their arguments and can't look any further. The "Y Combinator" pattern is used to bootstrap recursion into these languages. You may have heard of it. Turing-incomplete languages can also support unlimited recursion. For example, take a Turing complete language, and equip it with a state of the art theorem prover. Before entering a loop, or calling a function, the theorem prover is allowed to spend up to 1 minute proving that the loop or function call will terminate. If the theorem prover times out, the program halts with an error. Some functions, such as a naive implementation of factorial, can be easily proved to halt for all inputs. So this language allows recursion, but by construction, all programs terminate, so it's turing incomplete.
  - mousepilot 5y ago
    I'm not that great a programmer, but this one seems easy to me, you write an interpreter in brainfuck that allows function definitions that support recursion, then include your recursive function definitions as an included constant then point your interpreter at the constant and tell it to run it. I assume bf allows constants but like I said I'm not that great a programmer. Obviously using a recursive descent parser is out but thats probably easy to work around right? I could be wrong tho so don't base mission critical code on this without rigorous testing!