确定性语言的适用性

Question

现场出现了新的确定性语言,用于确定性地执行在多核上运行的多线程软件,例如Cilk++和Deterministic Parallel Java.

现在我的问题是,这些语言可用于实现任何类型的算法或仅用于特定算法.换句话说,这些语言是否以任何方式限制程序员？

Answer 1

"算法"的最常见定义不允许算法指定图灵机不能执行的计算.假设您正在使用其中一个传统定义,

不可以.所有图灵机都可以用图灵完整语言指定(模数资源限制).这些确定性语言大体上是图灵完备的.

也就是说,您可能无法编写某些类型的软件(而不是算法),例如设备驱动程序因硬件接口原因而需要处理易失性存储器,而且出于安全原因,特殊用途软件有时会出于不可预测的行为,例如加密生成强键,盐或non.密码强的PRNG是确定性的,但生成密钥的最佳方式是通过真正的随机源.

例如,由于其事件循环并发模型指定了交错,因此最小的JavaScript(并且只有JavaScript;没有DOM绑定)解释器减去Math.random以及Date.now一些其他非确定性来源将有资格作为确定性.JavaScript是一种图灵完备语言,可以表达像Java这样的语言可以使用的任何算法.您可以在该基本JavaScript中包含这样的工具,仅允许延迟允许确定性延迟评估,从而提供切片时间的丰富确定性方法.setTimeout0

Verilog是另一种事件循环并发语言,具有图灵完备的富有表现力的确定性子集.

Joe-E是图灵完整的Java子集,旨在提供确定性保证,作为提供"Java中可验证的功能纯度"的一部分,尽管它试图支持Java的线程模型.

除了事件循环并发之外,还有各种各样的actor模型提供了确定性,正如什么是*确定性并发*所讨论的那样？