为什么移动图灵是完整的？

Question

我最近发现了这个：https : //github.com/xoreaxeaxeax/movfuscator
这似乎取决于mov图灵完备的事实。这是真的吗，为什么？

Answer 1

是的，x86mov是图灵完备的。我在您的问题中添加了该标签，因为对于具有名为 的指令的其他 ISA 而言可能并非如此mov，并且 movfuscator 编译器仅针对 x86。

它不是“mov”本身在进行计算，而是可以进行加法（和位移）的 x86 寻址模式。我没有详细研究它是如何工作的，但它在很大程度上依赖于查找表，以及诸如mov eax, [base + eax*4]根据 EAX 是 0 或 1 加载两个可能值之一之类的东西。

还要记住，x86mov有几种形式：在内存和寄存器之间（加载、存储或 reg<-reg），或者直接到内存或寄存器。并具有包括绝对和寄存器间接寻址模式。

我不认为它依赖于自我修改代码，但如果我错了，请纠正我。（如果确实如此，我认为/希望 movfuscator 至少不会创建除mov.以外的指令。那将是作弊。）

此外，这只是一种真实；您需要某种方式来循环主程序，假设原始源不是没有循环的直线 - Movfuscator github 自述文件谈到了这一点：

虽然 Dolan 的论文需要 jmp 指令，但 M/o/Vfuscator 不需要 -它使用错误的 mov 指令来实现无限执行循环。如果您担心这仍然是“跳跃”，那么可以通过别名为相同地址的页面、围绕内存的上限范围包装执行、环 0 异常处理或简单地无限期重复 mov 循环来实现相同的效果。jmp 当前用于调度外部函数 - 如果这是一个问题，请避免使用外部函数，或者也使用 M/o/Vfuscator 编译库。

在为仅运行 mov 代码创建用户空间环境时，我假设它创建了一个 SIGSEGV 处理程序（在 POSIX 操作系统上），从顶部重新启动执行。因此，任何故障负载都可以重新启动主循环。

也提到了让执行环绕的可能性：

IP 的环绕可以在 16 位模式下很好地工作，其中 IP 是 16 位，但 CS:IP 形成一个 20 位线性地址（实模式），或者在 16 位保护模式下，线性地址空间中某处的 64k 窗口。即，您只能在部分地址空间中拥有 64k 指令块，而其他空间则留给数据。DS 段可以使用不同的基数。（16 位模式中的 32 位寻址模式是可能的，因此您仍然拥有任何寄存器和缩放索引寻址模式的全部功能。）请注意，读取和写入段寄存器的助记符也是mov.

但在 32 位模式下更难，其中 EIP 是 32 位，因此在 seg+off 计算后是线性地址。除非有其他技巧，否则回绕只能在整个地址空间中发生，而不管您对分段做什么。这没有为数据留下非代码空间。设置较低的段限制可能会导致代码提取错误，但这不会导致回绕（除非您设置信号处理程序，或者在裸机上设置中断处理程序地址）。

无论哪种方式，即使 x86-64 也只有 64 位指针（理论上；实践中为 48 位或 57 位），因此空间是有限的，与具有无限磁带的真正图灵机不同。

Answer 2

系统很少通过直接证明其所有图灵可计算功能的能力而被称为图灵完备。相反，它们通常被“类比”为已知为图灵完备的现有系统。

显示为 TC的 Stephen Dolan的论文通过mov构建 TM 系统的模拟来实现这一点mov。因此，任何可能对 TC 系统提出的问题，在最坏的情况下，都可以在mov构建的模拟中虚拟化。