使用 mov 指令实现通用图灵机
5.00/5 (14投票s)
基于 mov 的 UTM 具有图灵完备性论文 x86 和 x86-64
引言
Stephen Dolan 于 2013 年发表了一篇证明 x86 `mov` 指令是图灵完备的论文，随后又有一个 movfuscator 项目，它基于该项目创建了一个完整的编译器。请参阅论文：https://www.cl.cam.ac.uk/~sd601/papers/mov.pdf。论文中提出了一种通用图灵机（UTM），作为仅使用单个跳转指令即可证明图灵完备性的依据。
这些代码还可以作为一些关于如何实现 x86 和 x86-64 条件编译的参考，包括内联汇编和外部汇编，以及一些可能仅限于 Windows 平台但可应用于任何平台的语义。
背景
最好了解计算模型、图灵完备性、通用图灵机、图灵机以及 C 和 x86 汇编语言，同时了解内联汇编器和 Windows 技术，或了解如何将它们移植到其他平台（如 Linux 和 Mac）（这应该不难）。
Using the Code
下载包中包含另外两种图灵机模型：一种是非通用的、状态有限的，另一种是非通用的但输入磁带大小有限。这些模型提供了 C 和汇编格式的额外示例。
代码遵循的定义被呈现出来，它允许对研究论文进行完整的 C 语言模拟。为了在 C 语言中优雅地中止代码而不崩溃，使用了一些“作弊”方法，例如 `cmp` 和 `je` 指令，因为原始研究论文允许通过对内存地址 0 的错误访问触发段错误来终止。
必须根据代码进行推断，以弄清楚图灵机的数据结构和格式，以及输入磁带和如何正确初始化它们。通过查看互斥性、使用频率来定义寄存器，以便以最低影响的方式完成。汇编之前的 C 序言通过简单的图灵机编码进行适应，该编码假定按当前状态的排序顺序排列到内存寻址编码版本中。
代码可以在 Microsoft Visual Studio 2015 上成功编译和运行。
首先，必须根据以下格式对执行某些计算的图灵机进行编码
//{old state, old symbol, new symbol, direction, new state}
char turingMachine[][5] = {
{ '1', '0', '0', 'R', '1' },
{ '1', '1', '1', 'R', '1' },
{ '1', '_', '_', 'R', '3' },
{ '3', '0', '0', 'R', '3' },
{ '3', '1', '1', 'R', '4' },
{ '3', '_', '_', 'R', '2' },
{ '4', '0', '0', 'R', '4' },
{ '4', '1', '1', 'R', '4' },
{ '4', '_', '_', 'L', '5' },
{ '5', '0', '1', 'L', '5' },
{ '5', '1', '0', 'L', '6' },
{ '6', '0', '0', 'L', '6' },
{ '6', '1', '1', 'L', '6' },
{ '6', '_', '_', 'L', '7' },
{ '7', '1', '0', 'L', '7' },
{ '7', '0', '1', 'R', '1' },
{ '7', '_', '1', 'R', '1' }
}; //must be sorted
char Input[] = "0100_1001_";
这是一个执行二进制加法的图灵机，它使用递减然后递增直到 0 的策略。初始输入编码为 4 和 5，因此结果应该是 9 和 0。它必须按当前状态值排序，以便可以处理，因此如果未预排序，则可以使用快速排序或其他选项。以下函数用于对新状态执行二分查找。
int TMCmp(const void* l, const void* r)
{
if (*(unsigned char*)l == *(unsigned char*)r) return 0;
return *(unsigned char*)l > *(unsigned char*)r ? 1 : -1;
}
用于外部汇编器支持，这对 x64 是必需的
#include <basetsd.h>
extern "C" void __cdecl MovTM
(ULONG_PTR, ULONG_PTR, ULONG_PTR, ULONG_PTR, ULONG_PTR, ULONG_PTR);
其余代码如下
//<pointer to trigger symbol> <pointer to next state>
//<trigger symbol> <pointer to new symbol>
//<new symbol> <pointer to direction>
//<direction> <pointer to pointer to new state>
//<pointer to new state>
ULONG_PTR* TransitionTape = (ULONG_PTR*)malloc((sizeof(turingMachine) / 5)
* 9 * sizeof(ULONG_PTR)); //{old state, old symbol, new symbol, direction, new state}
ULONG_PTR* InputTape = (ULONG_PTR*)malloc(sizeof(Input) * sizeof(ULONG_PTR) * 2);
ULONG_PTR* InputTapeLeft = (ULONG_PTR*)malloc(sizeof(Input) * sizeof(ULONG_PTR) * 2);
for (int i = 0; i < sizeof(turingMachine) / 5; i++) {
TransitionTape[i * 9] = (ULONG_PTR)(TransitionTape + i * 9) + sizeof(ULONG_PTR) * 2;
TransitionTape[i * 9 + 3] = (ULONG_PTR)(TransitionTape + i * 9) + sizeof(ULONG_PTR) * 4;
TransitionTape[i * 9 + 5] = (ULONG_PTR)(TransitionTape + i * 9) + sizeof(ULONG_PTR) * 6;
TransitionTape[i * 9 + 7] = (ULONG_PTR)(TransitionTape + i * 9) + sizeof(ULONG_PTR) * 8;
char* ptr = (char*)bsearch(&turingMachine[i][4], turingMachine,
sizeof(turingMachine) / 5, 5, TMCmp);
int idx;
if (ptr != NULL) {
idx = (ptr - (char*)turingMachine) / 5;
while (idx != 0 && turingMachine[idx - 1][0] == turingMachine[i][4]) idx--;
}
TransitionTape[i * 9 + 8] = ptr == NULL ? (turingMachine[i][4] == '2' ?
(ULONG_PTR)InputTapeLeft : (ULONG_PTR)InputTapeLeft) :
(ULONG_PTR)(TransitionTape + (idx * 9));
TransitionTape[i * 9 + 2] = turingMachine[i][1];
TransitionTape[i * 9 + 4] = turingMachine[i][2];
TransitionTape[i * 9 + 6] = turingMachine[i][3] == 'R' ? sizeof(ULONG_PTR) : 0;
TransitionTape[i * 9 + 1] = ((i == sizeof(turingMachine) / 5 - 1) ||
turingMachine[i + 1][0] != turingMachine[i][0]) ? (ULONG_PTR)InputTapeLeft :
(ULONG_PTR)(TransitionTape + (i + 1) * 9);
}
for (int i = 0; i < sizeof(Input); i++) {
InputTape[i * 2] = Input[i];
InputTapeLeft[i * 2] = '_';
InputTape[i * 2 + 1] = (ULONG_PTR)(InputTape + (i + 1) * 2);
InputTapeLeft[i * 2 + 1] = (ULONG_PTR)(InputTapeLeft + (i + 1) * 2);
}
ULONG_PTR scratch[256]; // must be the size of the alphabet range
ULONG_PTR TransitionTapePtr = (ULONG_PTR)TransitionTape;
ULONG_PTR InputTapePtr =
(ULONG_PTR)InputTape + sizeof(ULONG_PTR) * 2; //part of tape right of current position,
// initially at beginning of input tape after current symbol
ULONG_PTR InputTapeLeftPtr =
(ULONG_PTR)InputTapeLeft; //part of tape left of
//current position, initially empty
//temporary registers,
//4 of which are mutually exclusive in usage
MovTM((ULONG_PTR)TransitionTapePtr, (ULONG_PTR)InputTape,
(ULONG_PTR)InputTapeLeft, (ULONG_PTR)scratch, (ULONG_PTR)InputTapePtr, (ULONG_PTR)InputTapeLeftPtr);
#if !defined(_WIN64)
for (int i = 0; i < sizeof(Input); i++) {
InputTape[i * 2] = Input[i];
InputTapeLeft[i * 2] = '_';
InputTape[i * 2 + 1] = (ULONG_PTR)(InputTape + (i + 1) * 2);
InputTapeLeft[i * 2 + 1] = (ULONG_PTR)(InputTapeLeft + (i + 1) * 2);
}
#define ADDRPLIER 4
#define SIZEWORD dword
#define X eax
#define Y ebx
#define M ecx
#define Z Y
#define D Z
#define H M
//5 globally used registers
#define L edi
#define R L
#define T R
#define S edx
#define N esi
__asm {
mov T, TransitionTapePtr;; current state, initially Q0
mov S, InputTape;; current symbol, initially Q0
mov N, InputTapeLeft;; scratch part of tape left of current position, initially empty
start:
mov X, [T];; get transition
mov X, [X];; get trigger symbol
mov Y, [S];; get current symbol
mov SIZEWORD ptr [scratch + Y * ADDRPLIER], 0;; compare symbols
mov SIZEWORD ptr [scratch + X * ADDRPLIER], 1 * ADDRPLIER
mov M, SIZEWORD ptr [scratch + Y * ADDRPLIER]
mov X, [T];; get transition
mov X, [X + 1 * ADDRPLIER];; skip trigger symbol
mov X, [X];; load new symbol
mov Y, [S];; load old symbol
mov [N], Y;; select between X and Y
mov [N + 1 * ADDRPLIER], X
mov Z, [N + M]
mov [S], Z;; write the new symbol
mov D, [T];; get transition
mov D, [D + 1 * ADDRPLIER];; skip trigger symbol
mov D, [D + 1 * ADDRPLIER];; skip new symbol
mov D, [D];; load direction
mov R, InputTapePtr
mov [N], R;; select new value for[S + 1]
mov L, InputTapeLeftPtr
mov [N + 1 * ADDRPLIER], L
mov X, [N + D]
mov [S + 1 * ADDRPLIER], X
mov [N], L;; select new value for L
mov [N + 1 * ADDRPLIER], S
mov L, [N + D]
mov InputTapeLeftPtr, L
mov [N], S;; select new value for R
mov R, InputTapePtr
mov [N + 1 * ADDRPLIER], R
mov R, [N + D]
mov InputTapePtr, R
mov SIZEWORD ptr [N], 1 * ADDRPLIER;; set X = not D
mov SIZEWORD ptr [N + 1 * ADDRPLIER], 0
mov X, [N + D]
mov [N], X;; select between D and X
mov [N + 1 * ADDRPLIER], D
mov D, [N + M]
mov L, InputTapeLeftPtr
mov [N], L;; select new value of S
mov R, InputTapePtr
mov [N + 1 * ADDRPLIER], R
mov S, [N + D]
mov X, [S + 1 * ADDRPLIER];; get new start of L or R
mov [N], X;; select new value for L
mov L, InputTapeLeftPtr
mov [N + 1 * ADDRPLIER], L
mov L, [N + D]
mov InputTapeLeftPtr, L
mov R, InputTapePtr
mov [N], R;; select new value for R
mov [N + 1 * ADDRPLIER], X
mov R, [N + D]
mov InputTapePtr, R
mov T, TransitionTapePtr
mov X, [T + 1 * ADDRPLIER];; get next transition of this state
mov Y, [T];; get current transition
mov Y, [Y + 1 * ADDRPLIER];; skip trigger symbol
mov Y, [Y + 1 * ADDRPLIER];; skip new symbol
mov Y, [Y + 1 * ADDRPLIER];; skip direction
mov Y, [Y];; load transition list of next state
mov [N], X;; select next transition
mov [N + 1 * ADDRPLIER], Y
mov T, [N + M]
mov TransitionTapePtr, T
mov X, [T]
mov SIZEWORD ptr [N], 1 * ADDRPLIER
mov SIZEWORD ptr [T], 0
mov H, [N]
mov [T], X
mov SIZEWORD ptr [N], 0;; select between 0 and N
mov [N + 1 * ADDRPLIER], N
mov X, [N + H]
cmp X, 0
je finish
mov X, [X];; load from 0 or N
jmp start
finish:
}
#endif
free(TransitionTape);
free(InputTape);
free(InputTapeLeft);
x86 预链接事件命令（safeseh 可能仅在发布版本中需要）：ml.exe /safeseh /Fo "$(OutDir)tm.obj" /c tm.asm
x64 预链接事件命令：ml64.exe /DX64 /Fo "$(OutDir)tm.obj" /c tm.asm
x86/64 链接器输入附加依赖项：$(OutDir)\tm.obj
x64 构建后事件（仅用于调试版本，因为 C 运行时程序集链接存在问题）：copy "$(MSBuildProgramFiles32)\Microsoft SDKs\Windows Kits\10\ExtensionSDKs\Microsoft.UniversalCRT.Debug\10.0.14393.0\Redist\Debug\x64\ucrtbased.dll" "$(OutDir)" copy "$(MSBuildProgramFiles32)\Microsoft Visual Studio 14.0\VC\redist\debug_nonredist\x64\Microsoft.VC140.DebugCRT\vcruntime140d.dll" "$(OutDir)"
汇编 x64 序言
ifndef X64
.model flat, C
endif
option casemap :none
.code
ifndef X64
ADDRPLIER EQU 4
SIZEWORD TEXTEQU <dword>
X TEXTEQU <eax>
Y TEXTEQU <ebx>
M TEXTEQU <ecx>
Z EQU Y
D EQU Z
H EQU M
L TEXTEQU <edi>
R EQU L
T EQU R
S TEXTEQU <edx>
N TEXTEQU <esi>
;eax, ecx, edx are considered volatile
MovTM PROC USES ebx edi esi TransitionTapePtr:DWORD, InputTape:DWORD, InputTapeLeft: DWORD,
scratch: DWORD, InputTapePtr: DWORD, InputTapeLeftPtr: DWORD
else
ADDRPLIER EQU 8
SIZEWORD TEXTEQU <qword>
X TEXTEQU <rax>
Y TEXTEQU <rbx>
M TEXTEQU <rdi>
Z EQU Y
D EQU Z
H EQU M
L TEXTEQU <r10>
R EQU L
T TEXTEQU <rcx>
S TEXTEQU <rdx>
N TEXTEQU <r8>
scratch TEXTEQU <r9>
TransitionTapePtr TextEQU <T>
InputTape TextEQU <S>
InputTapeLeft TextEQU <N>
;rax, rcx, rdx, r8, r9, r10, r11 are considered volatile
;x64 calling convention passes arguments fastcall: RCX, RDX, R8, R9, on stack
;but using default argument scheme uses stack and without first 4 indexes them incorrectly
;PROC -> DWORD PTR[rsp + 40] also could work here to use a more appropriate esp based indexing
;instead of ebp
MovTM PROC USES rbx rdi Dummy1: QWORD, Dummy2: QWORD, Dummy3: QWORD,
Dummy4: QWORD, InputTapePtr: QWORD, InputTapeLeftPtr: QWORD
endif
上面 `__asm {}` 块内的代码应放在此处，后面跟着这个汇编 x64 尾声
ret
MovTM ENDP
END
为了简化对双向链表堆栈和内存指针转换表构造的理解，以下 C 伪代码引入了控制流简化，代表了通用功能
ULONG_PTR CurInputTapePtr = (ULONG_PTR)InputTape;
TransitionTapePtr = (ULONG_PTR)TransitionTape;
InputTapePtr = (ULONG_PTR)InputTape + sizeof(ULONG_PTR) * 2;
InputTapeLeftPtr = (ULONG_PTR)InputTapeLeft;
do {
if (*(ULONG_PTR*)(*(ULONG_PTR*)TransitionTapePtr) == *(ULONG_PTR*)CurInputTapePtr) {
*(ULONG_PTR*)CurInputTapePtr = *(ULONG_PTR*)(*(ULONG_PTR*)
(*(ULONG_PTR*)TransitionTapePtr + sizeof(ULONG_PTR)));
if (*(ULONG_PTR*)(*(ULONG_PTR*)(*(ULONG_PTR*)(*(ULONG_PTR*)TransitionTapePtr +
sizeof(ULONG_PTR)) + sizeof(ULONG_PTR))) == 0) {
*(ULONG_PTR*)(CurInputTapePtr + sizeof(ULONG_PTR)) = InputTapePtr;
InputTapePtr = CurInputTapePtr;
CurInputTapePtr = InputTapeLeftPtr;
InputTapeLeftPtr = *(ULONG_PTR*)(CurInputTapePtr + sizeof(ULONG_PTR));
} else {
*(ULONG_PTR*)(CurInputTapePtr + sizeof(ULONG_PTR)) = InputTapeLeftPtr;
InputTapeLeftPtr = CurInputTapePtr;
CurInputTapePtr = InputTapePtr;
InputTapePtr = *(ULONG_PTR*)(CurInputTapePtr + sizeof(ULONG_PTR));
}
TransitionTapePtr = *(ULONG_PTR*)(*(ULONG_PTR*)(*(ULONG_PTR*)(*(ULONG_PTR*)
(*(ULONG_PTR*)TransitionTapePtr + sizeof(ULONG_PTR)) +
sizeof(ULONG_PTR)) + sizeof(ULONG_PTR)));
} else {
TransitionTapePtr = *(ULONG_PTR*)(TransitionTapePtr + sizeof(ULONG_PTR));
}
} while (TransitionTapePtr != (ULONG_PTR)InputTapeLeft);
关注点
图灵机编码格式的数据结构，该结构使用内存指针和给定状态内的状态转换列表，是通过一些简单的 C 代码推导出来的，并从典型编码中得出。输入磁带及其左侧部分的链表格式也通过推导和模拟得到。
研究论文中发现了 2 个错误，即在这里，我们看到 R 被错误地放置而不是 L：mov [N], X ;; select new value for L \\ mov [N+1], R \\ mov L, [N + D]，我们看到“H 为 1，我们必须停止机器”，但实际上代码选择在 H 为 0 时停止而不是 1。为了在前面的代码中纠正这一点，我们交换 0 和 1，mov [N], 0 \\ mov [T], 1 现在如果 H 为 0，我们必须停止机器，这通过 2 条“作弊”指令完成，一条比较和一条条件跳转，仅用于在 C 中实现优雅终止的成功模拟。
研究论文可能存在一些小错误，需要仔细审阅并花时间修复。我们尽量忠实于论文中的伪代码，仅在寄存器添加、从 C 转换以及优雅终止方面进行调整，并用制表符进行了注释。
x86 寄存器数量有限，需要寻找互斥性并以谨慎的方式保存或重新加载它们。`esp` 和 `ebp` 不应使用，尤其是在 C 语言中，恢复它们或访问数据会变得更加困难，尽管付出巨大的努力和谨慎，这是可能的。64 位代码可以访问 r8-r15 寄存器，这使得每个所需变量都可以拥有一个寄存器。调用约定很特殊，必须特别处理。
示例性的 C 语言通用 UTM，以及一个 64 位条件编译版本，使得实现更加通用且易于理解。
结论是，研究论文中的 UTM 虽然更具理论性，并且不像论文的结果那样被广泛实现，但其使用 `mov` 指令进行混淆的能力是正确的。
历史
- 初始版本
- x64 和外部汇编文件支持