• bintou

    @iwktd981220 这。。。我不知道啊。如果你们指的是Han Kunlin之类的,那就肯定是你们了!!!这么牛的一群人不讲,谁讲?

    发布在 灌水区 阅读更多
  • bintou

    暑假是非常重要的学习时段,需谨慎安排。每个人情况不同,需根据实际情况进行安排,我暂时还不清楚你们的情况。但是,无论是谁,都需要围绕两点进行:基础性、迫切性。就是说,重点考虑基础科目,重点考虑比较迫切的科目。比如:算法是基础,需要加紧,进行更多的学习;迫切性需要考虑下学期上的课程,尽量做好预习。再结合自身的缺陷,比如,编程是否过关,不行还需要补。

    一句话,围绕:基础性和迫切性,查漏补缺,攻关新知识。且计划性要强,每一个学习任务都要具体落实。

    建议以下两个阅读重点:
    1、CLRS
    2、CSAPP

    编程跟着CSAPP走:
    1、C/C++
    2、汇编

    增加一个Python的自学也是不错的选择。

    发布在 灌水区 阅读更多
  • bintou

    1、“全排列算法”的输入时一个串,输出什么?
    2、“全排列算法”是判断性还是计算性?

    搞清楚这个,大概就有答案了吧。

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

    @诟屍 只是我的看法,不知道泽鑫是否同意。

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

    我必须承认,我没怎么看懂问题。。。

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

    与相关同学讨论过很多次,互相都无法说服对方。我尝试再做努力。

    目前讨论双方达成的共识就是,说“有限存储图灵机等价于DFA”的理由是:有限存储TM的状态有限,既然有限,则可枚举,利用枚举出的所有状态,必可构造相应的DFA。

    首先,“有限存储”这个限定其实是不必须的,因为,即使是无限存储的TM,其状态也可能是有限。根据上文,只要状态有限,则可构造DFA。所以,某些无限存储TM也可等价于DFA。我强调这一点,主要是认为我们的讨论不应该重点放在“有限存储”上,而是“等价”。

    什么是等价,就是你能做的事情,我也能做。试想这样一种情形,我是TM一方,记为A,对方记为B。A说:我能做整数加法,你DFA能做吗?B:能,只要是有限的加法,你能做我就能做。A:好,那请你构造好机器,你构造好了,我就告诉你题目,而且我一定确保是有限计算。B:不行,你是有限机器,你必须告诉我你有多少比特,或者比特上限。请问,这里是分歧所在吗?

    即使是告诉你一个上限,比如,现在的计算机有12G的存储空间。于是,再次展开竞赛。A:我有12G存储,你准备好了吗?B:没问题,这次做什么?A:还是做加法,这次就算21000+310002^{1000} + 3^{1000}好了。B:没问题,你能做我就能做,我一定会把你的状态记录下来。A:呃,对不起,我还从来没算过这个加法,我也不知道答案。请你告诉我答案,你告诉我答案,我来验证一下就好了。B:不对啊,你一定会,你既然会就一定有答案,你快把答案告诉我。这就是我为什么不认同DAF等价于有限存储TM的主要原因。即使是有限存储,也不必然会有一台TM会把自己所有的状态枚举出来,让你根据状态去构造DFA。就好比你说,现在的电脑就是一堆芯片,状态就是唯一确定的。确实,但是,谁能告诉我说,任何一台电脑的状态全部都已经出现?根据实际需求去产生状态,这才是TM。

    如果上面还不能说服你们,那再考虑一种情形。假如存在一台可以求解哥德巴赫猜想的GB-TM,当然,这样的东西还没被发明。A:很高兴,我发现了GB-TM,它可以求解哥德巴赫猜想。B:是吗?你这台机器是有限TM?A:是的,存储器只有1024M比特。B:哈哈,那我这里有一台DFA与它等价。A:真的吗?你构造出来了吗?B:不用,显然存在,根本不需要讨论。A:太好了,你告诉我答案吧,是真还是假?B:你说是真就是真,你说是假就是假,你告诉我答案先。A:不是,你不是跟我等价吗?为什么要我告诉你答案?B:你都没答案,我怎么构造?

    这就是我为什么不认同“有限存储图灵机等价于DFA”,把某台TM的状态记录下来能称为”等价“吗?

    课本确实说了,DFA等价于某些计算机。当然,一台识别正则语言的计算机当然会有DFA与之等价了。而且,下这个结论都是针对双方可以解决的问题而言。DFA离开其所能识别的语言去谈状态,不可取。DFA不应该是状态记录器。

    如果,到此我们双方依然没办法说服对方。没关系!但是,我呼吁,对问题的讨论,不可情绪化,应该回归到问题本身。讨论问题是为了理清思路,帮助思考,寻求更多的发展。同时还需要一种包容的心态,一种开放的态度。过早地先下结论,封闭自我,没什么帮助。

    总之,说了这么多,我依然相信,这个问题有值得讨论的地方,我会保持开放的心态接受更多的反面意见。如果有同学可以从DFA定义本身出发提出自己的观点,更好!我认为,这恰好是我讨论中缺乏的东西。

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

    能把自己的学士论文发出来,本身就是值得鼓励的事情。再接再厉!

    发布在 博客区 阅读更多
  • bintou

    给定任意TM的编码<TM>与输入w,构造这样一台TM,假如命名为 One-More-State,它干这样的工作:做与(<TM>, w)相同的工作,但是,增加多一个无效的状态。可以这样想象:One-More-State 在输入(<TM>, w)之后发了一会儿呆,或者循环了一阵子,或者延时了一秒,然后模拟(<TM>, w)的所有工作。

    相信,构造One-More-State 是容易的,且不需要无限的纸带,也许只需要使用足以模拟(<TM>, w)所需要的存储即可。如果构造出来了,One-More-State 的编码也是容易的,比如就记为<One-More-State > 。

    我的问题是,One-More-State 以(<One-More-State >, (<TM>, w))为输入可以吗?如果可以,One-More-State 会停机吗?One-More-State在这种输入下的运行的状态会是有限的吗?

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

    @hzx__
    一个算法,给定输入,输出固定。不用说得那么复杂。

    同意。所以呢?

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

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