我是最后一年的工程专业学生。我和我的朋友们决定我们最后一年的项目是“使用模板元编程模拟图灵机”。
我了解“图灵机”和“模板元编程”是什么，但我的问题是，如果我们设计没有 TMP 的图灵机，为什么模拟会很乏味？如果我们使用 TMP，我们可以获得什么优势，如果我们不使用 TMP 而使用传统方法，我们会错过/获得什么？
关于我们将如何进行的任何建议？
问问题
954 次
3 回答
10
使用模板元编程实现图灵机的主要原因不是因为它比“普通”C++ 更容易（事实并非如此），而是为了证明 C++ 模板是图灵完备的。
于 2010-10-19T13:17:23.137 回答
5
我认为使用模板元编程设计图灵机模拟没有优势。它实际上更像是用双手绑在背后的击剑，用牙齿夹住你的花剑。
您这样做的原因是要熟悉 C++ 模板系统的强大功能，并证明 C++ 模板（以及因此 C++ 编译器）是图灵完备的。
于 2010-10-19T13:18:30.463 回答
1
为了显示它的 TM 完备性，实现Lambda 演算就足够了。
无论如何，使用位作为符号和最大带长为 64 位（其中空白为 0）实现受限 TM 可能很容易。另一种方法可能是禁止写入空白并计算左右终止符的相对位置; 那么它将是 65 位宽。uint64_t 将保存 BigEndian 中右侧的所有位，以及 LittleEndian 中左侧的所有位；活动位必须在自己的模板参数中。带上的一位必须保持为 0，或者有计数器来标记带的结束。
于 2010-10-23T21:31:29.710 回答