Re:Reddit's website uses DRM for fingerprinting
by jdm2212 on Wednesday July 08, 2020 @07:43PM
(#23775505)
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
Re:Reddit's website uses DRM for fingerprinting
by Gene_Parmesan on Thursday July 09, 2020 @03:11AM
(#23777729)
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.
Re:Reddit's website uses DRM for fingerprinting
by smitop on Thursday July 09, 2020 @08:12AM
(#23779312)
> it's theoretically possible for it to create an entire simulated CPU
A Javascript x86 implementation already exists: https://copy.sh/v86/
Re:Reddit's website uses DRM for fingerprinting
by ryanlol on Thursday July 09, 2020 @03:08AM
(#23777716)
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.
Re:Reddit's website uses DRM for fingerprinting
by krastanov on Wednesday July 08, 2020 @08:41PM
(#23775858)
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/)
Proving the same constraints and having the same trust in a Turing complete language is basically the halting problem, which is not computable.
Why is Turing-completeness the issue here?