门户网站布局,免费设计软件app,网上免费自己设计商标,做自媒体网站需要注册什么公司背景之前读了 Martin Davis 的《Computability and Unsolvability》#xff0c;决定对其中的图灵机和递归函数等价性证明做一个#xff08;不严谨的#xff09;整理#xff0c;证明方法比较有趣#xff0c;虽然最终结果并没有太大的惊喜。整理本身的目标是抛开晦涩难懂的数…背景之前读了 Martin Davis 的《Computability and Unsolvability》决定对其中的图灵机和递归函数等价性证明做一个不严谨的整理证明方法比较有趣虽然最终结果并没有太大的惊喜。整理本身的目标是抛开晦涩难懂的数学符号从结合实际的角度给一个概念上的说明以此希望自己下次回顾的时候不会完全看不懂。更方便讨论的图灵机冯诺依曼体系结构可以看作是图灵机的一个具体实现同时增加了对图灵机上一些基本操作的封装比如说图灵机包括一条无限长的被分成一个单元格的纸带单元格上可以标记 0 或 1这个纸带就可以对应到计算机内存这个纸带上最开始的内容就可以看作输入最终内容可以看作输出图灵机中在具体某个状态下看到纸带当前单元格上的内容执行左移右移或者修改纸带内容的操作并跳转到某个状态即对应为在内存上读出某个数据执行某种计算写回计算结果并跳转到新的指令地址的操作。而程序指令集增加的操作可以看作对图灵机一系列操作的封装并不增加计算能力。而面向过程的高级语言比如 C 语言又很好的反应了冯诺依曼体系结构的特点比如变量对应到内存语句对应到指令同时有各种循环结构或者直接通过 goto 进行语句间的跳转。所以同样可以比较简单的把这样的高级语言看作是和图灵机等价的。所以后面会直接在高级语言的基础上进行讨论。递归函数以及递归函数到图灵机的等价性而递归函数的数学表达比较简单并且看上去比较规则。不严格的说递归函数表示的是任意可计算函数都可以通过对一些基本函数进行组合而成。基本函数的一些例子def s(x): return x 1
def n(x): return 0而组合的方式一共包括以下三种# 组合对任意 h a b 函数
def c(x):return h(a(x), b(x))# 递归对任意 g h
def r(x, y):return x 0 ? g(y): h(x, y, f(x - 1, y))# 最小化对任意 g
def m(x):i 0while g(i, x): i 1return i所以既然基本函数和组合函数都能很容易的写成面向过程的代码潜在的就表示递归函数可以很方便的改写成图灵机所以所有的递归函数都可以用图灵机计算。图灵机到递归函数的等价性所以证明的另一半就是证明所有的图灵机都是递归函数也是比较有趣的部分。证明的基本方法是编码整个图灵机的运算过程然后枚举所有计算过程直到找到一个计算过程满足程序执行过程和程序要求并最终退出然后从中得到计算结果。比如说对以下过程def f(x):i 0# 语句 0while i ! 2: i 1# 语句 1return i要对整个执行过程进行编码对状态 s, v 表示为在语句 s 时 i 的值为 v则初始状态为 0, 0最终结束状态为 1, 2对整个执行过程最终要找到 0, 0, 0, 1, 0, 2, 1, 2。所以对应的递归函数最外层会类似于def f(x):for e in [[(0, 0)], [(0, 1)], [(1, 0)], [(1, 1)], [(0, 0), (0, 0)], [(0, 0), (0, 1)], # 无穷多的状态序列...]:# 符合初始状态if e[0] (0, 0) # 符合结束状态and e[-1] (0, 2)# 对状态序列中的每一个状态# 都能得到下一个状态and all([ yields(e[i], e[i 1]) for i in range(len(e) - 1)])return e[-1][1]将执行过程进行两遍的哥德尔编码即先对每个状态进行哥德尔编码再对整个状态序列进行编码我们就会在最上层得到一个调用了最小化函数的组合函数def f(x): # 组合函数return gl(1, gl(ln(g(x)) - 1, i))def g(x): # 最小化函数i 0while not t(i): i 1return i其中 gl(x, y) 是从哥德尔编码中 y 中得到第 x 位的值。ln 返回哥德尔编码对应的序列长度而 t 函数def t(x):return valid(x) # 符合初始状态and gl(0, x) gn(0, 0) # 符合结束状态and gl(ln(x) - 1, x) gn(0, 2) # 对状态序列中的每一个状态# 都能得到下一个状态and all ([ yields(gl(i, x), gl(i 1, x)) for i in range(ln(x) - 1)])其中 valid 测试是否为合法的两遍哥德尔编码结果gn 是哥德尔编码函数。而 yields 函数描述了合法的程序状态转换def yields(x, y):# if i ! 2: i 1return (gl(0, x) 0 and gl(1, x) ! 2 and gl(0, y) 0 and gl(1, y) s(gl(1, x)))# else: breakor (gl(0, x) 0 and gl(1, x) 2 and gl(0, y) 1 and gl(1, y) 2)其中的子函数都可以由递归函数规则生成举其中一个简化了的例子def f(x, y):return x ! 2 and y 0等价于def f(x, y):return (not abs(x - 2)) abs(y) 0其中加法可以表示为def plus(x, y):return x 0 ? y: 1 plus(x - 1, y)而没有的惊喜在于整个证明过程并不能有效的找出图灵机中潜在的函数调用结构。严格证明可参考《Computability and Unsolvability》。停机问题所以从递归函数的角度看停机问题其实只存在于最小化函数而其它函数都是保证退出的而其实对于整个图灵机到递归函数的证明也只在最后一步使用了最小化函数。
