4 ms·

>the idea of letting a site execute Turing-complete computations on its visitor's computers Why is Turing-completeness the issue here?

jdm2212 6y ago
I think that's being used to mean "it's impossible to predict/reason about/constrain what the computation might do". Turing completeness => it can do anything, you can't predict anything
- ryanlol 6y ago
  This only makes sense as far as resource usage goes, Turing completeness has nothing to do with access to APIs which you really need to do anything interesting. Brainfuck is turing complete but can’t call any APIs, you can very much predict that a Brainfuck program won’t be doing anything very exciting.
- Gene_Parmesan 6y ago
  Maybe, but I think it's an overblown term in these sort of questions. Being Turing-complete doesn't mean that it can do anything. It means that it is isomorphic to a Turing machine; in other words, it can emulate a Turing machine, which means it can compute anything a Turing machine can compute. That's definitely not the same as "do anything." For instance, it doesn't mean it's suddenly granted access to APIs to communicate with the system/break out of a sandbox. I mean, I guess it's theoretically possible for it to create an entire simulated CPU (is it though? not sure...), but not in practice. The more concerning thing is how strong your sandbox is.
  - smitop 6y ago
    > it's theoretically possible for it to create an entire simulated CPU A Javascript x86 implementation already exists: https://copy.sh/v86/ https://copy.sh/v86/
krastanov 6y ago
If it is not Turing complete, your sandbox/interpreter/whatever can be certain that the code does not do anything "surprising". Basically, you can know at compile time that the program fulfills certain constraints. For practical examples, see the newish virtual machine inside of the linux kernel used to execute constraint "scripts" to control the firewall (https://lwn.net/Articles/740157/ https://lwn.net/Articles/740157/) Proving the same constraints and having the same trust in a Turing complete language is basically the halting problem, which is not computable.

jdm2212 6y ago

I think that's being used to mean "it's impossible to predict/reason about/constrain what the computation might do". Turing completeness => it can do anything, you can't predict anything

ryanlol 6y ago
This only makes sense as far as resource usage goes, Turing completeness has nothing to do with access to APIs which you really need to do anything interesting. Brainfuck is turing complete but can’t call any APIs, you can very much predict that a Brainfuck program won’t be doing anything very exciting.
Gene_Parmesan 6y ago
Maybe, but I think it's an overblown term in these sort of questions. Being Turing-complete doesn't mean that it can do anything. It means that it is isomorphic to a Turing machine; in other words, it can emulate a Turing machine, which means it can compute anything a Turing machine can compute. That's definitely not the same as "do anything." For instance, it doesn't mean it's suddenly granted access to APIs to communicate with the system/break out of a sandbox. I mean, I guess it's theoretically possible for it to create an entire simulated CPU (is it though? not sure...), but not in practice. The more concerning thing is how strong your sandbox is.
- smitop 6y ago
  > it's theoretically possible for it to create an entire simulated CPU A Javascript x86 implementation already exists: https://copy.sh/v86/ https://copy.sh/v86/

krastanov 6y ago

If it is not Turing complete, your sandbox/interpreter/whatever can be certain that the code does not do anything "surprising". Basically, you can know at compile time that the program fulfills certain constraints. For practical examples, see the newish virtual machine inside of the linux kernel used to execute constraint "scripts" to control the firewall (https://lwn.net/Articles/740157/ https://lwn.net/Articles/740157/) Proving the same constraints and having the same trust in a Turing complete language is basically the halting problem, which is not computable.