• 周凯

    这里, 对角线法的证明貌似没有推理出矛盾吧?!

    对角线法来证明不可数, 先假设了存在那么一个一一对应的函数, 使到自然数集可以映射到这个language. 但是呢, 用对角线法构造出来了一个串\in这个language, 它没有对应的定义域, 从而推理出了矛盾.

    emmm, 这里是不是缺少点什么呀??感觉证明不可数的过程有问题.

    一一对应证明可数, 可以将这个语言覆盖.应该是可数的.

    发布在 计算理论讨论区 阅读更多
  • 周凯

    之前发帖时写的一些讨论逻辑有问题

    [1]M accept 或者 reject的讨论;
    如果R accept, 那么M2一定是regular的. 那么M2一定不接受形如 0^n1^n 这样的串. M2是regular的, 如果M reject w, 那么M2识别的就是空语言(空语言是regular的, 可以构造一个DFA没有accept state). 如果M accept w, 那么M2识别regular language. 所以M可以accept或者reject.

    如果M reject w, 那么M2识别的就是空语言! 错! M2只是不接受这个x而已! 并不是所有的x, 所以怎么会是空呢?

    发布在 计算理论讨论区 阅读更多
  • 周凯

    终于弄懂了.

    如果 M 死循环,那么 M2M_2什么都做不了

    之前一直在纠结死循环的事, 误以为死循环了, 还会识别空语言:dizzy_face: ,然后空语言又是regular的.
    M2什么都干不了,自然不会是regular的, 连空都不能识别.

    OK, Thanks

    发布在 计算理论讨论区 阅读更多
  • 周凯

    这里有一个疑惑:
    @诟屍 在 回复中说:

    S 是这样一台图灵机:
    对于一个特定的输入 M 和 w,首先构造一个 M2M_2,使得:
    如果 M 接受 w,那么 L(M2)=ΣL(M_2) = \Sigma^* 即任意串都接受,是正则
    如果 M 不接受 w,那么 L(M2)={0n1n}L(M_2) = \{0^n1^n\},不是正则

    将M2放到RegularTMRegular_{TM}中跑, 如果RegularTMRegular_{TM} accept, 那么说明M对于输入的w会halt, 因为regular是decidable的. 如果RegularTMRegular_{TM} reject, 那么M2不是regular的, 它有可能是recognizable的, 但不是decidable的. 也就是说, M是否接受w, 无法判断. 这样的话, 也就无法使用判断M是否接受w来判断L(M2)了.

    第二个疑惑就是:
    你说的M2其实就是不理解的那句话,直接转过去的,很直接.可是为什么书上构造的M2是先判断是否0n1n0^n1^n这样的形式,然后在判断M是否接受.

    "We design a M2 to recognize the nonregular language {0n1nn>=00^n 1^n | n >= 0} if M does not accept w, and to recognize the regular language Σ\Sigma^{*} if M accepts w."

    有个作业deadline了,留给zzk的时间已经不多了23333(逃

    发布在 计算理论讨论区 阅读更多
  • 周凯

    Theorem 5.3 RegularTMRegular_{TM} is undecidable
    书上有一段话没看懂:

    "We design a M2 to recognize the nonregular language {0n1nn>=00^n 1^n | n >= 0} if M does not accept w, and to recognize the regular language Σ\Sigma^{*} if M accepts w."

    M2是不是regular的, 和M是不是accept w之间有什么关系?

    试图论证一下:
    1, M2是regular的, 那么它一定是decidable的, M输入任何w一定会halt.可是M accept或者reject, 是不确定的[1]. 论证的第三点却说道:"If R accepts, accept", 也就是说不管M是否accept w, 只要M2是regular的, S就accept. If M2 is regular, Whether M accept w or not, S accept.
    2,S逻辑上是: If M accept w then accept, reject w then reject.
    以上两点有矛盾.

    [1]M accept 或者 reject的讨论;
    如果R accept, 那么M2一定是regular的. 那么M2一定不接受形如 0^n1^n 这样的串. M2是regular的, 如果M reject w, 那么M2识别的就是空语言(空语言是regular的, 可以构造一个DFA没有accept state). 如果M accept w, 那么M2识别regular language. 所以M可以accept或者reject.

    发布在 计算理论讨论区 阅读更多
  • 周凯

    @诟屍 谢谢大佬的表格…终于写好了总结。

    第二章:http://zazakai.com/2017/08/20/CSAPP-chapter2/
    第三章:
    http://zazakai.com/2017/08/27/CSAPP-chapter3/

    顺便说一句,3.4.1的配图文字有错inmediately,3.6.7的代码while loop那段jump to middle少了test标签。嗯,再次感谢dalao的分享。

    发布在 博客区 阅读更多
  • 周凯

    @诟屍 dalao,你这篇博客里的表格,我能截图拿来用吗:heart_eyes:

    发布在 博客区 阅读更多
  • 周凯

    应该说是够用就好……看了不用容易忘掉,不如不看。

    发布在 灌水区 阅读更多
  • 周凯

    今天刚好看到数组这部分,CSAPP,第257页,3.8.2第一句话。

    C allows arithmetic on pointers,where the computed value is scaled according to the size of the data type referenced by the pointer.

    这句话就概括了以上第2、4两种情况。x是一个指向int类型的指针,&x是指向数组类型的指针,两者指向的地址相同。加的大小,取决于指针的类型,x+1是数组首地址加上1×sizeof(int),&x+1是数组首地址加上1×sizeof(x)。自从开始看CSAPP之后,看到一段代码都有一种想看看汇编码的冲动,虽然每次看到汇编码都是一脸懵逼。以下的图,主要关注register %rsi 的变化情况。
    0_1502464530553_Screenshot from 2017-08-11 22-58-24.png

    发布在 CSAPP 讨论区 阅读更多
  • 周凯

    上面的代码对应右边的汇编码

    发布在 灌水区 阅读更多

与 图灵班论坛 的连接断开,我们正在尝试重连,请耐心等待