• 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__
    一个算法,给定输入,输出固定。不用说得那么复杂。

    同意。所以呢?

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

    hzx:任意给定计算机,我可以构造等价的DFA。
    斌头:好,我给一台计算机给你,存储空间8bits,每个bit有两种状态,你要构造有多少个状态的DFA?
    hzx:我只需要最多282^8个状态。
    斌头:那我这台计算机刚好有28+12^8 + 1个状态,你看,这机器长这个模样。
    hzx:那我就构造28+12^8+1个状态的DFA。
    斌头:不好意思,数错了,是28+22^8+2个状态...
    hzx:没关系,你有多少状态我就构造多少个状态出来给你。
    斌头:数不清怎么办?
    hzx:没关系,总归是有限状态,不然你叫什么有限状态图灵机?

    请问,最后谁会赢得这次构造游戏?

    我相信我会赢。因为确实,计算机的状态没人数得出来,否则就不会存在“停机问题”了。

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

    @hzx__

    首先,你总是“显然老师认为”,但是你每一次的显然都不显然,我并不是这个意思,所以,我不需要反例。

    其次,你应该回答我的问题,你如何构造?即,给定一个PDA或者TM,你如何构造一个与之等价的DFA。我一直在说,你之前描述的构造不成立。这才是“老师显然的认为”。你需要给出明确的构造,而不是只是论证状态有限。

    提醒一点,PDA的栈无限,TM的纸带无限只是一种方便的描述,我们讨论的都是有限状态自动机或者有限状态图灵机。

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

    @hzx__有限存储的计算机等价于有限自动机(DFA、NFA) 中说:

    证明计算机等价于TM

    而且我要向所有的同学强调一点,没有任何人证明了”计算机等价于TM“!!!请注意,是丘奇图灵命题,不是丘奇图灵定理(或公理)。我们只是相信计算机等价于TM,丘奇图灵命题不能证明也无法证伪,至少现在还是如此。

    我的学习经历中出现过若干次有人声称”证明“或者”证伪“了丘奇图灵命题。但最后都没有得到承认。至于以后会如何,我不知道,目前我们还是相信如此。如果量子计算的理论进一步发展,可以证伪丘奇图灵命题,也是可能的,但是,这是未知的事实。

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

    @hzx__有限存储的计算机等价于有限自动机(DFA、NFA) 中说:

    然后我的思路是, 对任意一台给定的计算机 都可以构造等价的DFA(不仅仅是任意一段某台计算机可以运行的源码)

    天啊,这并不是我的思路!!!

    你一直强调“ 对任意一台给定的计算机 都可以构造等价的DFA(不仅仅是任意一段某台计算机可以运行的源码)”,这是怎么做出来的?我的思路就是,你做不出这样的构造!

    比如说,给出一台可以计算 a + b 的计算机,你大算怎么构造DFA呢?我希望你回答这个问题。或者,你怎么能构造一台识别0n1n0^n 1^n的DFA呢?

    不知道你为什么强调“给定”,现在任何一台计算机都是有限存储的吧,你就构造一台自己的计算机的DFA出来就好了,你怎么构造?我不希望你重复说,因为计算机的存储有限,所以最多2n2^n种状态,所以,只需要一个2n2^n状态的DFA。对不起,你这构造是失败的。这才是我的思路。

    请看你自己的论述“因为源码是M比特长,所以最多有2M2^M 种不同的源码,根据上文,可以为每种元源码构造一个DFA"。这个结论是说,任意一个计算机程序都可以编码为一个DFA,理由还是因为长度有限,所以,状态有限。

    我们看看PDA与DFA之间的关系吧。PDA的状态也是有限的,是不是意味任意PDA都能写成一个DFA?那么也就是说,DFA 等价于PDA等价于TM等价于计算机?我不明白了,为什么你会承认PDA可以识别CFG而DFA不行的结论,而又强调PDA与DFA等价呢?

    我们的分歧到底在哪里?定义?定理?证明?我希望可以回归到ITOC的内容来探讨这种分歧,而不想强调任何的”暗示“、”言下之意“或者自己得出的”推论“。

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

    @没有人
    我仔细看了一下帖子里面的讨论,里面大部分的内容是在支持我的观点,不是支持DFA等价与计算机,我选几篇内容出来:

    Eric Towers

    Actual computers are not FSAs. An actual computer is a universal computer, in the sense that we can describe a computer for a computer to emulate and the computer will emulate it. For many examples, search for "virtual machine".

    It is possible to construct a Universal Turing Machine -- a TM that receives a description of another TM then emulates the operation of that TM on a supplied input.

    osinalvo

    One important feature of turing machines that finite automata do not share is that they can scale the amount of memory needed to solve the problem with the size of the problem.

    MvG

    While other answers have already mention many relevant aspects, I believe that the stronges advantage of Turing machines over finite automata is the separation of data and program. This allows you to analyze a quite finite program and make statements about how that program would handle different inputs, without restricting the size of the input.

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

    @hzx__有限存储的计算机等价于有限自动机(DFA、NFA) 中说:

    而图灵机可以识别该集合内的所有字符串

    请问,图灵机是如何识别该集合内的所有字符串的?我认为,图灵机也不能识别所有的字符串,但是它可以识别所有出现在输入纸带中的字符串。

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

    @hzx__ 没有误解,我整理一下我们讨论的思路。

    hzx的观点:计算机等价与DFA,因为,计算机存储有限,所以,状态有限,所以,可以把任意计算机转换为DFA。

    斌头的观点:计算机不等价与DFA。确实,计算机的存储有限,但是其状态不仅仅由存储器的状态决定。因此,DFA只能描述计算机某一次执行过程,但是无法使用一个DFA描述某一台计算机所有的的执行过程,因为计算机的执行过程会由其输入的不同而不同。计算机强于DFA。

    @没有人 来看看这个思路。。。

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

    @hzx__

    我更不明白你的意思。你一直强调没有否认课本的观点,但是你所有观点都是在否认课本的观点:

    • DFA与计算机等价,这里否认了图灵机强于DFA和NFA
    • 图灵机强过计算机,这里否定了丘奇图灵命题

    你这所谓“强有力的证据”并不是什么证据。计算机是有限状态的图灵机,当然不能做无限的事情。请注意,你只要给定,任何一个n,计算机就能识别。而不是说,计算机可以识别所有的n定义的语言。

    你因此认为TM强于任何一台计算机的结论不知道依据是什么?

    我的意思很简单:“计算机的存储器的状态数等同与计算机的状态数”是错误结论。比如,计算机可以计算加法,即给定a和b,求出a+b。我是说,计算机可以做,但是DFA不能做。你的意思是,DFA也能做,比如,你给出3和5,我也能计算机3+5 。这不就是我们的分歧所在吗?a和b是输入,是任意输入,计算机可以对任意给定整数做加法,DFA不行。也许你说,不对,计算机也是有限的,不能做任意的加法。对,但请注意一点,我是说,只要你能写在输入中(即,给定输入),我就能做。我不需要对不存在的任意进行操作。

    反过来,你设计出的DFA能做什么?要计算机3+5,你就要设计一个DFA,如果要计算300+500,你又要设计一个DFA出来。这就是我之前强调“universal”时要表达的观点,是强调,计算机是通用的机器。在这个意义上,计算机是强于DFA、NFA和PDA的。其实也是说TM强于DFA等。

    丘奇图灵命题是说,TM与计算机等价。

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

    @没有人 你给出链接的讨论跟这里完全不同啊!!!
    “Real computers have only a finite number of states, so what is the relevance of Turing machines to real computers?”,是TM与计算机的等价性。不是DFA与计算机的等价性讨论。

    发布在 博客区 阅读更多

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