上午
计算理论课
图书馆借书(《论可计算数》、Cutland's Computability)
操作系统lab2稍微做了点
中午
主、副歌
《论可计算数》翻读
哥德尔的递归函数论在数学界被接受,邱奇的λ-cal则不被数学接受,也不被早期cs接受(太惨了吧)(
波斯特标签系统,d=2时也有通用标签系统;一维元胞自动机的规则编码为(111,110,...,000)时的中间格变为01101110是通用机器
希尔伯特的终极梦想被哥德尔与图灵击碎:哥德尔证明了不一致,图灵证明了不可判定(当然要先提出TM来def何为算法),他们的想法都来自康托的对角线论证
下午
Computability : an intro to recursive function theory ch1, ch2
ch1
URM模型的J指令会导致不可终止。当然,也能对应TM的不可终止吧,应该也是个图灵完备的机器
习题1.3 .3(常数m) .4(T指令冗余)都很有趣T是冗余的,这是否是因为有J呢?如果没有J,有T,是否计算能力不变?计算理论基础这本书里的整函数计算只有Z,S,T?问题是J似乎是递归函数所需要的一种跳转能力?TM里面组合是不是提供了这种跳转能力
又或者说!我们把J指令修改为PC相对寻址,这样子就不会有问题了对吧(x)这样URM模型就不需要改J跳转的地址(好耶)
ch2
子程序的寄存器干扰woc,那这里
还有 substitution
recursion, bounded-mu operator, mu operator
习题还没看哪些值得做(GG)
total computable -> N上都是computable? partial 只有子集D是comoutable
晚上
操作系统lab2做完了,报告也写好发过去了!!
Simply Extended Typed Lambda Calculus, SETLC的Type-parsing做完了。