VHDL是否是图灵完备的？

Question

VHDL是否是图灵完备的？我的理解是VHDL创建了一个寄存器机，而只有带有任意RAM的寄存器机才是图灵完备的。

这个观点正确吗？对于不能在寄存器机上解决的问题，是否有标准的方法-例如使用在VHDL之外的RAM，并通过VHDL进行管理？

- SRobertJames

---

你肯定可以用VHDL来实现RAM。对于综合，大多数FPGA都会将你的RAM映射到专用的存储块中。这可能不是最便宜的存储形式，但这是经济学上的争论，而不是基本原则上的。 - user1818839

VHDL具有动态内存分配功能，因此它与其他系统编程语言一样完整。 - Kevin Thibedeau

Answer 1

图灵完备性的主要标准有三个：

1. 序列。 做这件事，然后做那件事，再做另一件事
2. 选择。 如果 这样 那么 做某事
3. 迭代（或递归）。 重复做这件事直到满足条件

对于内存的要求并不是无限制的（这在现代技术下是不可能的，所有语言都会失败），而是无界限或无限可扩展的：即，如果用完了，可以添加更多并重试。

所以我认为VHDL当然符合要求。它可以完成所有这些任务。

- luser droog

---

你能给出一个在VHDL中展示递归的代码示例吗？ - SRobertJames

我找到了一个帖子，其中有一个例子（https://groups.google.com/d/topic/comp.lang.vhdl/6iriCKNutv8/discussion）。 - luser droog

@SRobertJames：状态机很容易展示递归，我认为没有人会争论我们不能在VHDL中构建状态机。 - Bill Lynch

@Bill - 状态机绝对不是图灵完备的。 - SRobertJames

Answer 2

展示图灵完备性的另一种方式是通过一系列转换：

1. 图灵机是图灵完备的。
2. 图灵机可以由寄存器机器模拟，反之亦然。
3. 寄存器机器是现代处理器的一个抽象简单模型。
4. 您可以使用VHDL描述处理器。

因此，VHDL是图灵完备的。

- Paebbels

---

但是，您是否可以使用VHDL模拟布局呢？我的意思是，假设电路的JPEG照片可以转换为VHDL，这是否意味着JPEG是Turing完备的？能够容纳Turing完全但需要解释器的东西并不能使容器成为Turing完全。 - Mikhail

一个光刻描述只是一种写下图灵机的其他方式。当使用笔和纸执行寄存器和图灵机时，没有人要求纸和笔是图灵完备的。 - Paebbels

我想知道进行算术运算的人是否是图灵完备的，而不是纸笔之类的工具 :-) - Mikhail