Applicability of Deterministic Languages

New deterministic languages are arising on the scene for deterministic execution of mulithreaded software running on multicore, such as Cilk++ and Deterministic Parallel Java.

Now my question is, can th开发者_开发问答ese languages be used to implement any type of algorithm or only specific ones. In other words, do these languages limit the programmer in any way?

---

Most common definitions of "algorithm" do not allow an algorithm to specify a computation that cannot be performed by a Turing machine. Assuming you are using one of those conventional definitions,

No. All Turing machines can be specified (modulo resource limits) in a Turing complete language. These deterministic languages are Turing complete by and large.

That said, you may not be able to write some kinds of software (not algorithms) like device drivers that need to deal well with volatile memory for hardware interface reasons and special purpose software sometimes wants to behave unpredictably for security reasons, e.g. generation of cryptographically strong keys, salts, or nonces. There are cryptographically strong PRNGs that are deterministic, but the best way to generate a key is via a source of true randomness.

As an example, a minimal JavaScript (and only JavaScript; no DOM bindings) interpreter minus Math.random and Date.now and a few other sources of non-determinism would qualify as deterministic since its event-loop concurrency model specifies the interleaving. JavaScript is a Turing-complete language that can express any algorithm that a language like Java can. You can include in that basic JavaScript a facility like setTimeout that only allows 0 as the delay to allow deterministic delayed evaluation providing a rich deterministic way to slice time.

Verilog is another event-loop concurrent language that has a Turing-complete richly expressive deterministic subset.

Joe-E is a Turing complete subset of Java that aims to provide determinism guarantees as part of providing "Verifiable Functional Purity in Java" though it punts on trying to support Java's threading model.

Besides event-loop concurrency, there are varieties of the actor model that provide determinism as discussed at What's *Deterministic concurrency*?

---

Some algorithms will work best if they have some randomness, (Monte carlo algorithms). However, you can emulate randomness by using a Mersenne twister or similar random number generator. Thus, by using a RNG, you can emulate non-deterministic behavior. Why one would do want that, I don't know.

Multi-threading that are non-deterministic CAN be used as a source of randomness, so you REALLY need some random events, then using non-deterministic MT can be such source, but there are probably a million better options (like go online, download weather data)...