• H
    hzx__

    如果是直接把链表拿去排序,那么需要O(NlgN)O(NlgN) 次链表读写,对cache很不友好

    如果预先搞个数组,把链表的每个块的起始地址、key存起来,然后去排序,然后使用unording map,那么只需要O(N)O(N) 的链表读写,其他都是数组读写。
    我猜或许性能会好一点

    发布在 算法与数据结构讨论区 阅读更多
  • H
    hzx__

    下文中,ww指要进行全排列的字符串,AAww中包含的字母集合

    • 如果按照那个“存在一个验证器,其在多项式时间内验证答案”,全排列算法似乎难以找到一个长度为O(w)O(|w|) 的证据
    • 但是,确实可以有一台NTM在多项式时间内运行全排列算法:从start stat开始,每一步都非确定性的猜测下一个字符,那么,经过w|w|步后,就可以生成Aw|A|^{|w} 个串,每个NTM分支都验证自己生成的这个串是不是合法的ww的一个全排列,如果是,accept(从而有A!|A|!个接受分支),那么接受分支上的字符串就是全排列的结果。consider that,不同分支生成的字符串必然是不同的,所以不需要对所有结果进一步处理就可以得到结果。
    • 备注:多个接受分支是合法的,以下句子暗示可以有多个接受分支。

      书上P48 倒数第一句:The machine accepts if at least one of the computation branches ends in an accept state, as shown in Figure 1.28

    • (此处NTM似乎可能存在问题——该算法的运行结果是所有接受分支上的字符串,这是否是合法的)
    • 那么,全排列算法是否属于NP?

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

    @oded-zeng

    • 上面说的那个U就是师兄描述的那个U
    • 最 “复杂” 的这个 复杂 我只能大概的描述一下“复杂”,给不出形式化定义 。其来自于 第六章谈 打印出 <SELF> 的图灵机时说的 “某机器解决x问题,需要至少跟x问题一样复杂”
    • 确实,需要先设计好 M 才可以 交给 U,从此处来看或许不可以称 U 解决了所有图灵机可以解决的问题——因为问题还是那些图灵机自己解决的 :joy:

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

    可以构造一台图灵机UU,其接受任意一台图灵机 AA 的编码后模拟该图灵机。
    从而,任意一台图灵机接受的语言 的变种(所谓变种,就是比如 A 接受 字符串 s, 那么UU 接受 C(A)sC(A)*s —— C(A)C(A) 就是 A 的编码,* 是连结 ),UU 都接受。
    也就是,UU 可以 解决任意一台图灵机可以解决的问题

    那么,UU 是不是 最”复杂“ 的图灵机

    consider that, 这里的UU 不是ATMA_{TM} 那里提到的那个 universal turing machine

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

    输入源码自己产生转移路径的DFA可以如此构造——还是枚举,枚举所有可能的源码。一旦源码确定,那么该源码的执行过程就确定,所以,我们可以组装这有限台 DFA,以及一个作为解释器的DFA——其根据源码选择对应的DFA。从而这个组装出来的DFA就与给定的计算机等价

    确实,以上过程看起来就是

    有某台TM先枚举出configuration、configuration转移路径

    但是,既然我们构造TM、构造DFA时都需要先构造出转移函数,那么,上面的过程其实就是构造转移函数。

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

    我认为,只要构造出一台DFA,其与给定的计算机接受相同的语言既可以认为他们等价。
    而无需考虑该DFA的运行过程是不是模拟计算机的运行过程。

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

    按照书本在证明 NFA与DFA等价时使用的定义,我认为可以直接把 等价 定义为 识别相同的语言

    • DFA不应该是状态记录器。
    • 为什么要我告诉你答案?B:你都没答案,我怎么构造
    • B:没问题,你能做我就能做,我一定会把你的状态记录下来。A:呃,对不起,我还从来没算过这个加法,我也不知道答案。请你告诉我答案,你告诉我答案,我来验证一下就好了。
    • 即使是有限存储,也不必然会有一台TM会把自己所有的状态枚举出来,让你根据状态去构造DFA。就好比你说,现在的电脑就是一堆芯片,状态就是唯一确定的。确实,但是,谁能告诉我说,任何一台电脑的状态全部都已经出现?根据实际需求去产生状态,这才是TM。

    确实,我构造出来的 ”等价于于某台特定计算机的DFA“ 的运行过程就像在沿着该计算机的执行历史前进。但是,这不需要有某台TM先枚举出configuration、configuration转移路径,我才能构造该DFA。
    电脑在实际中,根据问题的不同都不同的转移路径,其原因就是,对于不同的问题,我们使用不同的源代码——即,我们对这台电脑输入不同的源码。
    同样的,我也可以有一台DFA,其接受输入的源代码,然后自己产生出后面解决问题需要的转移路径。

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

    首先描述一个集合

    • 注:以下串都是比特串
    • 首先,有个origin串,为全0的无穷串
    • 规定,该集合内的元素除了origin串外,其他元素都是对origin串修改某一个bit得到的。
    • 比如,100000...000100000...000 ,其为origin 串修改第一个bit得到的,又比如01000000...000001000000...0000 ,其为origin串修改第二个bit得到的

    使用康托对角线证明其不可数

    • 将除了origin 串外的其他串从上往下排列——修改第一bit的串排在第一行,修改第二bit的串排在第二行,以此类推。最后,origin 串排在最后一行
    • 然后,使用康托对角线法——显然,上面的构造方法使得串中那些相对于origin串被修改的位 就是对角线法将修改的位,从而使得,对角线法每一步总是复位一个串中相对于origin串修改的那 一位,从而该对角线法最后得到的串就是origin 串,所以,康托对角线证明了这是一个不可数集合

    为什么对角线法不会修改到处于矩阵最末尾的origin串

    • 因为,对角线法修改的任意一个坐标(i,j)(i,j),都有i=ji=j,而假设该集合有N个非origin串和一个origin串,则最后一行的坐标都是(N+1,i),iN(N+1,i), i\leq N,所以,最后一行没有任意一个元素会被修改到

    使用一一对应证明其可数

    • 使用N编码该集合内的元素——修改第一bit的串编码为2,修改第二bit的串编码为3,以此类推,origin 串编码为1

    问题

    • 两种方法得到不同结果,这其中哪里出问题了

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

    可以证明,One-More-State 不是判定器。不过,One-More-State 以(<One-More-State >, (<TM>, w))为输入 还是有可能停机的——因为并没有形成无限递归

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

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