问题标签 [non-deterministic]

我在某处读到 C 双精度浮点中存在不确定性的来源，如下所示：

1. C 标准说，需要 64 位浮点数（双精度）才能产生大约 64 位精度。

2. 硬件可以在 80 位寄存器中进行浮点运算。

3. 由于 (1)，C 编译器不需要在将 double 填充到高位之前清除浮点寄存器的低位。

4. 这意味着 YMMV，即结果可能会发生微小差异。

是否有任何现在常见的硬件和软件组合真正发生这种情况？我在其他线程中看到.net 有这个问题，但是 C 通过 gcc 加倍好吗？（例如，我正在测试基于精确相等的逐次逼近的收敛性）

在下面的代码中，如何put 1用一些在状态中插入非确定性 1 或 2 的代码替换？

下面的玩具示例通过调用函数来不确定地计算一个数字anyFunction，然后只保留偶数选择。我怎样才能编写一个类似的代码来保持最大选择而不是偶数选择？我需要不同的单子堆栈签名吗？

I am struggling a bit with the meaning of determinism and nondeterminism. I get the difference when it comes to automata, but I can't seem to find an answer for the following: Is a NFA to DFA transformation deterministic?

If multiple DFAs can be constructed for the same regular language, does that mean that the result of a NFA to DFA transformation is not unique? And thus a nondeterministic algorithm?

I'm happy with any information you guys might be able to provide.

Thanks in advance!

剧透：这是Project Euler问题 #18。阅读风险自负

问题是找到从帕斯卡三角形顶部严格向下到底部的所有非确定性路径的“最大和”。我试图通过对三角形的行进行折叠来计算总和。

这是输入字符串，以及一些基本的准备工作：

这里有两个想法——有一排树，一排三角形。我没有做太多类型级别的抽象，但这并不重要。这个想法是三角形中的每一行都是在其长度上的二项式的“平行枚举”（即：）[(4,0), (3,1), (2,2), ... (0,4)]，并且在将标记的三角形行应用于树的行之前，树的每一行都得到“复制分叉”，使得确保每次分叉的机会都保持非确定性的完整性。这是我的技术的样子：

我的问题是代码适用于一行输入，但在折叠多行时失败。我的直觉告诉我，我的“复制叉”技术正在创建新标签，然后我的overElems函数可以通过它期望访问的标签应用。这是我的主要功能：

奇怪的是，折叠一行有效，但折叠多行无法应用高阶函数，但仍将结果扩展为正确的大小。以下是几个示例输入：

我的列表处理中的懒惰会导致这种情况吗？我的感觉是标签枚举发生在overWith有机会通过标签应用功能之前。这也是我的代码的完整页面。

在 Mercury 中，我可以将 lambda 声明为与包含 lambda 的谓词的模式具有相同的确定性吗？

这就是我想要做的。我编写了一个适用于 array2d 类型的折叠函数（如下）。fold为数组中的每个元素调用调用者提供的谓词。只要它只接受一个 det 谓词作为参数，它就可以正常工作。

但我想fold接受 det 或 semidet 谓词（如果对谓词的任何调用失败，则失败）。取消注释该mode ... is semidet行会给我带来我不知道如何解决的编译器错误。问题是 lambdafold被声明为 det，所以它们不能调用 semidet Pred。如果我将 lambdas 更改为 semidet，那么fold作为一个整体就无法确定。

我该如何解决这个问题？似乎最直接的方法是声明 lambdas 从fold谓词继承它们的确定性——所以当它们fold被用作 det 时，它们是 det，对于 semidet 也是如此——但我不知道这是否可能。

当然，另一种方法是转换为具有多种模式FoldRows的FoldCols命名谓词（不是 lambda）。但这很快就变得不优雅，我想知道是否有更直接的解决方案。

我正在编写一个光线追踪器，并且已经能够使用 Phong 着色渲染球体和平面。

但是，我的三角形出现了非常奇怪的行为。每当我运行程序时，三角形似乎采用任意颜色（即使没有重新编译）。我是 C++ 新手，我完全不知道是什么原因造成的，因为其他对象都很好，而且它们都继承了相同的方法来计算它们的颜色。

三角形最常见的是黑色，但偶尔是蓝色、红色或粉红色的单一阴影（可能有其他颜色但不确定）。我注意到的是，每个阴影都是一致的，可能 RGB 值是 1 或 0，根据我的观察，我猜想蓝色例如是 (0,0,1)。

我的问题是，这种奇怪的非确定性可能是什么原因？这让我有点困惑，但我又是 C++ 的新手。这是光线追踪常见的问题吗？可能是面向对象，还是指针/引用问题？

如果需要，我可以提供更多详细信息，我只是不知道为什么会发生这种情况。

谢谢您的帮助！

在一个关于 NFA 的练习中，我被要求在正则表达式 (aa|aab)*b 上构建一个四态 NFA。我尝试自己构建它，我只能找到一个 5-state NFA，后来在线工具证实了这一点。

（我发现它没有（4）是最终的，并且没有从 b 的（3）到（2）的附加箭头，但这导致相同）是我没有看到问题，还是没有办法做这只有四个州？

我有一个不使用随机化的脚本，当我运行它时会给我不同的答案。我希望每次运行脚本时答案都是一样的。这个问题似乎只发生在某些（病态的）输入数据上。

该片段来自一种用于计算线性系统的特定类型控制器的算法，它主要包括进行线性代数（矩阵求逆、Riccati 方程、特征值）。

显然，这对我来说是一个主要的担忧，因为我现在不能相信我的代码会给我正确的结果。我知道对于条件不佳的数据，结果可能是错误的，但我希望始终是错误的。为什么我的 Windows 机器上的答案并不总是相同？为什么 Linux 和 Windows 机器不给出相同的结果？

我正在使用Python 2.7.9 (default, Dec 10 2014, 12:24:55) [MSC v.1500 32 bit (Intel)] on win 32Numpy 版本 1.8.2 和 Scipy 0.14.0。（Windows 8、64 位）。

代码如下。我还尝试在两台 Linux 机器上运行代码，脚本总是给出相同的答案（但机器给出不同的答案）。一个运行 Python 2.7.8，使用 Numpy 1.8.2 和 Scipy 0.14.0。第二个是使用 Numpy 1.6.1 和 Scipy 0.12.0 运行 Python 2.7.3。

我求解 Riccati 方程 3 次，然后打印答案。我每次都希望得到相同的答案，而是得到序列 '1.75305103767e-09; 3.25501787302e-07；3.25501787302e-07'。

我的 numpy 配置如下print np.show_config()

（编辑以减少问题）

我读过函数式编程非常适合多线程程序，因为它带来了编程语言范式（不变性，无副作用的函数）。我还读到多线程程序通常是非确定性的。

鉴于stakx对类似（但不同）问题的回答，这是我的问题：

如果使用函数式编程语言进行编码，多线程程序可以是确定性的吗？