• 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))为输入 还是有可能停机的——因为并没有形成无限递归

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

    关于反驳 板桥兄提出的 “如果NFA读完输入,还没有ac,那就是reject,所以NFA不死循环”,书上是说,读到ε\varepsilon 时,可以无输入的滑到下一个状态,但是并没有说这不需要时间。每个操作都定义为需要1单位时间,那么如果某串读完后,可能其会被ac,但是需要n时间后才会通过ε\varepsilon 滑到ac 态,所以并不是立刻接受。所以,如果某输入不被ac,然后又有ε\varepsilon ,那么我们要等待 |Q| (|Q| 是Q的size)时间后才可以知道其被reject。
    这也是我和达超提出来的检测死循环的方法——如果计算机读完输入后(即后面不会有再有输入)的运行过程中重复了状态,那么就是死循环了。

    死循环与否并不会影响ac、reject的字符串集合——因为无论是计算机还是NFA都可以判定死循环

    发布在 博客区 阅读更多
  • H
    hzx__

    可否如此理解“无穷bit串” 不属于Σ\Sigma^*

    Σ\Sigma^* 中的任意字符串都是有确定长度的, 也就是会“ending”,无论其多长,而无穷比特串是 unending的,所以,无法在Σ\Sigma^* 中找到任意一个字符串与 无穷bit序列对应,所以无穷比特串不属于Σ\Sigma^*

    所以,无穷比特串其实是Σ\Sigma^* 中的元素可以无限逼近但是用于无法达到的东西——就好像 0 之于 an,a<1a^n, a<1

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

    @bintou

    输入字符表是{0,1}\{0,1\} ,将所有计算机接受的输入全部编码成bit 串后读入计算机,每次读一个0或者一个1。

    我们能不能把计算机输出输入的过程归约为以上过程呢

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

    @bintou

    计算机的行为由当前状态决定——下一步要执行什么代码,取决于正在被执行的代码段,以及ip寄存器的值,如果text段的内容相同,cs:ip寄存器的相同,指令使用的值也相同,那么下一步的行为就是确定的

    老师同意以上这句话吗

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

    @bintou 一台给定的计算机是DFA,但是当我们可以使用任意计算机时,也就是当我们可以使用任意DFA时,DFA的有限状态已经不是限制了——我们使用另一种 方法达到了任意内存。

    发布在 博客区 阅读更多
  • H
    hzx__

    @bintou 没错,实际上,除非TM、PDA无限死循环,否则他们的识别某字符串的行为总是可以被某台计算机所实现——因为有限时间内,他们读写进无限存储里的东西必然是有限的,对应的,我也可以对其某次处理某个字符串的过程构造对应DFA——为什么不是直接构造一台DFA其等价于某台TM呢?因为TM的行为(排除掉死循环)也无法被一台计算机所完全实现。

    这就是我认为的无限的意义——使得只要TM可以对某个输入运行某个算法,那么我们也可以找到一台计算机,其也可以对该输入运行该算法——而无需局限于给定 的计算机。

    发布在 博客区 阅读更多
  • H
    hzx__

    给定计算机,不会数不过来的

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

    @bintou PDA 的栈是无限的,PDA状态是有限的,所以,唯一描述一台PDA 当前的情况 必须描述该PDA 的 当前状态、当前栈内容等 ,这显然可能是无限的。

    发布在 博客区 阅读更多
  • H
    hzx__

    @bintou 显然老师认为 即使当计算机的存储cell都一样,计算机的下一步行为也可以是不同的,这个我不认可,老师可否先举出一个反例

    老师或许会说 ”下一步有个输入,输入不同,那么他们的行为就不同“ —— 但是,对于一台DFA,即使处于相同状态,输入不同,下一步状态也是不同的。
    所以,考虑另外一个问题,我们能不能枚举完所有输入,为所有可能的输入都预定好接下来的转移函数——显然是可以的

    发布在 博客区 阅读更多
  • H
    hzx__

    @bintou

    老师的思路是: 某台图灵机能识别的任意一个字符串,总是可以找到一台计算机也识别该字符串,所以,图灵机识别的语言类与计算机识别的语言类等价
    也就是说,通过“找到任意一台计算机” 把使得计算机也类似有了任意大小的内存。

    对于语言{0n1n}\{0^n1^n\}, 我们要求要有同一台TM能识别该语言的所有字符串,并且反驳DFA不可以识别该语言时也是在使用同一台DFA的情况下反驳的——pumping lemma 需要该语言长度大于一定值的字符串的路径有环,然后可以无限重复该环,这都是基于同一台DFA——如果我可以对于该语言内的各个字符串使用不同的DFA,那么显然的,对于每个字符串,总是可以找到一台DFA识别该字符串,从而DFA也可以识别{0n1n}\{0^n1^n\} 的所有字符串。

    但是,此处老师证明计算机总是可以识别{0n1n}\{0^n1^n\} 的所有字符串时,却使用不同的计算机——显然是不能这样,如果要证明计算机等价于TM,那么就得使用同一台计算机,其识别了所有该集合的字符串

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

    发布在 博客区 阅读更多

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