精华内容
下载资源
问答
  • 图灵机不可判定问题

    千次阅读 2013-11-03 12:26:39
    接受状态子集和拒绝状态子集相交(能有一个状态既是接受状态,也是拒绝状态)。  有一个字符集Σ,图灵机以Σ上的字符串ω作为输入(ω∈Σ*,Σ*是一个集合,它的元素是:由0个或多个Σ上的字符组成的有限...
    一. 图灵机简介
           图灵机(Turing Machine)有有限个状态。其中一个状态是开始状态。这些状态的一个子集是接受状态,还有一个子集是拒绝状态。接受状态子集和拒绝状态子集不相交(不能有一个状态既是接受状态,也是拒绝状态)。

           有一个字符集Σ,图灵机以Σ上的字符串ω作为输入(ω∈Σ*,Σ*是一个集合,它的元素是:由0个或多个Σ上的字符组成的有限长度的字符串)。图灵机还有一个字符集Γ,是”带“(tape)字符集。Γ包含Σ中的所有字符,还必须有一个Σ中没有的字符,就是空白字符。图灵机的带(tape)上一开始默认都是空白字符。图灵机的带,是一个无限长的带子,分成一个个的单元格,每一个单元格上写一个字符(初始都是空白符)。图灵机有一个读写头,总是位于带的某一个单元格之上。读写头对当前的单元格进行读写。读写头可以顺着带子左右移动,但一次只能移动一个单元格。Γ就是图灵机可以向带子上写的字符的集合。

           图灵机的动作是这样的:根据当前所处的状态和当前读到的字符,在当前单元格上写下一个字符,向左或右移动一个单元格,进入另一个状态(对于这些动作的规定,就是图灵机的转移函数δ)。一开始,将输入字符串ω(ω∈Σ*)放在带子上,把图灵机的读写头对准ω的第一个字符,并让图灵机处于开始状态。然后图灵机就开始一步一步地运行:读字符、写字符、移动读写头、进入新状态,然后再重复......直到图灵机进入某一个接受状态,这时图灵机停机并接受ω。图灵机也有可能进入一个拒绝状态而停机,这种情况下图灵机拒绝ω。除了这两种情况,还有第三种情况:那就是图灵机永远不会停机。图灵机既不进入接受状态,也不进入拒接状态,而是一直运行下去。后两种情况,合称图灵机不接受ω。

           所以,对于Σ*中的一个字符串ω,这个图灵机要么接受它,要么不接受它。图灵机不接受ω,有可能是图灵机拒绝ω,也有可能图灵机不停机。一个图灵机接受的所有字符串构成的集合(是Σ*的一个子集)作为一个语言(字符串集合即为”语言“),就是这个图灵机”识别“的语言。

           有一类图灵机,它们对于任何输入字符串ω都停机(要么接受,要么拒绝。两者必居其一)。这类图灵机被称为判定器。被判定器识别的语言称作被这个判定器”判定“(这类语言称作”可判定语言“)。如果把识别一个语言作为”计算“的通用模型(这点以后说明),那么判定器就是可以明确地给出计算结果的图灵机。要么”是“,要么”不是“。

           一个图灵机的“程序”,就是固化在它的状态集以及转移函数δ中的“动作”。但也可以构建一个”通用图灵机“,它的输入字符串是一个”序列化“了的图灵机M和一个字符串ω。”通用图灵机“在字符串ω上模拟图灵机M的行为,产生和M一样的结果(接受、拒绝或不停机)。一个图灵机只有有限个状态、有穷字符集Σ和带字符集Γ,以及定义域和值域都是有穷离散集合的转移函数δ,所以只要约定好了格式,一个图灵机就可以用一个字符串来描述(序列化成了一个字符串)。”通用图灵机“有点像可存储程序的冯.诺依曼计算机。

    二. 计算、算法与图灵-邱奇论题
           你也许会觉得:图灵机是干吗使的?答案:计算。那什么是计算?图灵机干的事情就是计算。那2×3=6图灵机能算么?如果你把"aa|aaa"作为输入字符串ω提供给某个图灵机,这个图灵机停机,并在带子上留下aaaaaa。你给了它2个a和3个a,它给了你6个a,它不就是计算了2×3=6么。

           这里对”图灵机编程“不做详细介绍了。总之图灵和邱奇证明,任何有步骤的、确定的计算过程,都可以由图灵机实现。任何可执行计算的装置:算盘、珍尼纺纱机、超级计算机等等,都可以由一台图灵机模拟。也就是说:任何计算装置,都无法超过图灵机的能力。图灵机也就定义了计算和算法。

           一切计算问题都可以等价于字符串接受/不接受问题,也就是语言的识别(也许是判定)问题。也就是说一切”计算“,都可由图灵机进行。

    三. 图灵机不可判定问题
           上面说,有些语言(字符串集合)可被一个判定器(总会停机的图灵机)判定(识别)。给一个字符串ω,这个判定器得出结论:ω是否属于这个语言。这些语言是”可判定“语言。那么是否存在不可判定语言?也就是是否存在一个语言,不存在一个判定器可以判定它?答案是”是“。设想下面的语言:

           A = {(<M>,ω) | <M>是表示图灵机M的字符串,ω是一个字符串。M接受ω}

           也就是,语言A中的字符串都有两部分组成:第一部分是一个图灵机M的字符串表示<M>;第二部分是一个字符串ω。且M接受ω。

           假设语言A是可判定的,也就是存在一个判定器H。当M接受ω时,H接受(<M>,ω);当M不接受ω时,H拒绝(<M>,ω)。(注意H是一个判定器,它总会停机,接受或拒绝(<M>,ω))。那么我们对H稍加改造,将它的结果取一下反:当M接受ω时,H拒绝(<M>,ω);当M不接受ω时,H接受(<M>,ω)。这很容易,只要把H的接收状态和拒绝状态互换一下身份即可。

           然后我们可以再对H做一个变化,它的输入字符串仅仅是一个图灵机M的序列化字符串<M>,喂给这个M的输入不再是某个字符串ω,而就是字符串<M>本身。那么H的行为就变成了:输入给它一个表示某个图灵机的字符串<M>。把<M>当做给图灵机M的输入,若M接受<M>,则H拒绝<M>;若M不接受<M>,则H接受<M>。

           精彩之处到了:若把H自己的序列化字符串<H>提供给H会发生什么?当H接受<H>时,H拒绝<H>;当H不接受<H>时,H接受<H>。理发师悖论。唯一的结论只能是,H不可能存在。就是说对于语言A,不可能构造一个判定器去判定它。A是不可判定语言。不可判定语言是存在的。

      再换一种方式说一遍(不带任何符号,争取用话说明白):假如存在一个判定器(还记得判定器么?就是总会停机的图灵机,要么接受,要么拒绝,反正不会不停机),以一个图灵机的描述(也是一个字符串)和一个字符串作为输入。它可以判定这个图灵机是否接受这个字符串,也就是:这个图灵机接受这个字符串,我这个判定器就停机接受;这个图灵机不接受这个字符串,我这个判定器就停机拒绝。(注意我这个既然是判定器,它就能做到上边说的)。那么以这个判定器为基础,就可以构造另一个判定器,这个判定器只拿一个图灵机的描述(一个字符串)当输入,然后把这个描述本身当做给这个图灵机的输入,判断这个图灵机是否接受它自己的描述:它接受,我判定器就停机并接受;它不接受,我判定器就停机并拒绝。然后以这个判定器为基础,再改造一下。这次改造简单,只是把接受和拒绝反一下:判定器的输入是一个图灵机的描述(一个字符串),然后判定这个图灵机是否接受它自己的描述:它接受,我判定器就停机且接受;它不接受,我判定器就停机且拒绝。没问题吧。好!现在把我这个判定器自己的描述输入给它,它将如何?它将在自己接受自己的描述时拒绝自己的描述;在自己不接受自己的描述时接受自己的描述。悖论了!

           如果存在不可判定语言,那么必然存在不可识别语言。就是无法构造一个图灵机,接受这个语言的每一个字符串(用不着拒绝每一个不属于这个语言的字符串,因为这里说的是识别,而不是判定)。因为:如果一个语言L和它的补^L都是图灵机可识别的,那么L是可判定的。证明:设识别L的图灵机是M1,识别^L的图灵机是M2。构造图灵机M,它在字符串ω上交替地一步一步地模拟M1和M2。因为一个字符串要么属于L,要么属于^L,也就是对于一个字符串ω,要么M1进入接受状态,要么M2进入接受状态。于是M总会看到M1或M2(之一)进入接受状态。如M1进入接受状态,则M停机并接受ω;若M2进入接受状态,则M停机拒绝ω。那么M就成了语言L的一个判定器。所以如果一个语言不可判定,必然它或者它的补是不可识别的。不可识别语言是存在的。

           一个不可判定的语言,就是一个不可计算的问题。那是一个超出了计算机能力的问题,一个不能被任何有步骤的、确定性的算法所能解决的问题。那是什么样的问题?也许是女人心吧。
    展开全文
  • 可判定问题

    2014-01-12 16:25:57
    我们知道这个是不可判定的。 这里表示的是: M描述一台能够识别语言L的图灵机,对任何一个字符串,我们判定M是否能接受它(接受或者拒绝)。 A的含义是:对所有图灵机,我们都要实现上边的功能。这是一个可判定...

    定义:A={<M, ω> | M描述一台图灵机,且M描述的机器接受ω}

    我们知道这个是不可判定的。

    这里表示的是: M描述一台能够识别语言L的图灵机,对任何一个字符串,我们判定M是否能接受它(接受或者拒绝)。

    A的含义是:对所有图灵机,我们都要实现上边的功能。这是一个可判定问题。


    如果这里是所有图灵可判定语言的图灵机,那么显然有这么一个图灵机A存在。因此为可判定。


    展开全文
  • 实现编译器对无限循环(“死循环”)的检查,是一个递归不可判定问题。 二、证明过程 1.假设存在方法检测死循环程序,那么可以设计程序LOOP如下: //LOOP程序 void Loop(Program P){ if(P != loop){ //LOOP...

    我自己看的时候没看懂,网上一搜都是“停机问题”,所以了解完“停机问题”又回来看这个例子,有了些思路记录下来,不知道是否正确

    一、问题(原书P263)

    实现编译器对无限循环(“死循环”)的检查,是一个递归不可判定问题。 

    二、证明过程

    1.假设存在方法检测死循环程序,那么可以设计程序LOOP如下:

    //LOOP程序
    void Loop(Program P){
        if(P != loop){
            //LOOP进入死循环
        }
        else{
        //否则终止LOOP
        }
    }

    2. 将上述程序的P替换为LOOP程序自身,这里输入的LOOP就是当前的整个程序。

    void Loop(Program Loop){
        if(Loop != loop){
            //进入死循环
        }
        else{
            //终止
        }
    }

    3. 矛盾之处在于,LOOP为死循环时,LOOP程序会终止;LOOP程序能终止时,LOOP程序为死循环。导致LOOP程序永远不可能正确。

     

    后记:证明思路——若能实现程序判定死循环,那么就会存在这样一种无法确定是否会死循环的程序,故,不存在程序判定死循环的能力。但其实我觉得书上写复杂了,不知道为啥要多加一层P?

    展开全文
  • 最近在读图灵的两本专著,《艾伦图灵传如谜的解谜者》《图灵的秘密》,其中图灵的秘密写得真好。从康托的集合论讲到超越数。...其中我不明白的是,为什么利用图灵机模型可以证明可判定性问题不可解。
  • SCOOPING THE LOOP SNOOPERA proof that the Halting Problem is undecidableGeoffrey K. Pullum(School of Philosophy, Psychology and Language Sciences, University of Edinburgh) No general pr
    
    			

    SCOOPING THE LOOP SNOOPER

    A proof that the Halting Problem is undecidable

    Geoffrey K. Pullum
    (School of Philosophy, Psychology and Language Sciences, University of Edinburgh)

     

    No general procedure for bug checks succeeds.
    Now, I won't just assert that, I'll show where it leads:
    I will prove that although you might work till you drop,
    you cannot tell if computation will stop.
     
    For imagine we have a procedure called P
    that for specified input permits you to see
    whether specified source code, with all of its faults,
    defines a routine that eventually halts.

    You feed in your program, with suitable data,
    and P gets to work, and a little while later
    (in finite compute time) correctly infers
    whether infinite looping behavior occurs.
     
    If there will be no looping, then P prints out `Good.'
    That means work on this input will halt, as it should.
    But if it detects an unstoppable loop,
    then P reports `Bad!' --- which means you're in the soup.
     
    Well, the truth is that P cannot possibly be,
    because if you wrote it and gave it to me,
    I could use it to set up a logical bind
    that would shatter your reason and scramble your mind.
     
    Here's the trick that I'll use -- and it's simple to do.
    I'll define a procedure, which I will call Q,
    that will use P's predictions of halting success
    to stir up a terrible logical mess.
     
    For a specified program, say A, one supplies,
    the first step of this program called Q I devise
    is to find out from P what's the right thing to say
    of the looping behavior of A run on A.
     
    If P's answer is `Bad!', Q will suddenly stop.
    But otherwise, Q will go back to the top,
    and start off again, looping endlessly back,
    till the universe dies and turns frozen and black.
     
    And this program called Q wouldn't stay on the shelf;
    I would ask it to forecast its run on itself.
    When it reads its own source code, just what will it do?
    What's the looping behavior of Q run on Q?
     
    If P warns of infinite loops, Q will quit;
    yet P is supposed to speak truly of it!
    And if Q's going to quit, then P should say `Good'
    --- which makes Q start to loop! (P denied that it would.)
     
    No matter how P might perform, Q will scoop it:
    Q uses P's output to make P look stupid.
    Whatever P says, it cannot predict Q:
    P is right when it's wrong, and is false when it's true!
     
    I've created a paradox, neat as can be ---
    and simply by using your putative P.
    When you posited P you stepped into a snare;
    Your assumption has led you right into my lair.
     
    So where can this argument possibly go?
    I don't have to tell you; I'm sure you must know.
    By reductio, there cannot possibly be
    a procedure that acts like the mythical P.
     
    You can never find general mechanical means
    for predicting the acts of computing machines.
    It's something that cannot be done. So we users
    must find our own bugs. Our computers are losers!

     
    来源:http://www.lel.ed.ac.uk/~gpullum/loopsnoop.html

    展开全文
  • 在分析各种达分析方法求解变迁约束问题不足的基础上,采用约束程序的办法,针对变迁约束进行约束模型构造和算法研究。该约束模型构造的算法充分利用了T向量提供的信息,对可达图进行展望搜索,实例验证表明,...
  • 合取范式的可满足性判定算法和谓词逻辑不可判定性 博客分类:  数理逻辑 作为本系列的最后一篇文章,我们来看被广为研究的SAT问题。 SAT问题是第一个被证明为NP问题的判定问题。更多信息...
  • 什么是“判定问题”?(1)- 计算性理论与计算复杂性理论 已有 1843 次阅读 2015-6-6 00:07 |个人分类:确定性问题和算法讨论|系统分类:科研笔记|关键词:P versus NP 计算复杂性理论 计算性理论 ...
  • 冲突串行化的判定

    2013-05-12 20:34:08
    一.问题的提出在数据库工程师的考试中,对事务的并发操作多次考到,且占有很高的... 冲突串行化的判定判定方法分为两个步骤: - 步骤1:产生调度的优先图; - 步骤2:采用一个合适的算法(如基于深度优先或广度...
  • 二、"停机问题" 不可判定、 三、"图灵机语言是否空集问题" 不可判定、 四、"图灵机是否等价问题" 不可判定、 五、"是否存在自动机接受图灵机语言问题" 不可判定、 六、莱斯定理 ( Rice's Theorem )
  • 不可判定问题:某些判定问题是不能用任何算法求解的,则称这种判定问题为不可判定问题。否则就称作可判定问题。 例如:Halting problem(停机问题):给定一段计算机程序和他的一个输入,判断该程序对于该输入是会中止...
  • lidengdeng (一鸣惊鬼) 2004-07-21 20:19:59 在 .NET技术 / ASP.NET 提问现在在一个页面上有多个服务器控件, 每点击(或下拉等)一个控件都会实行一遍Page_Load(obect sender,...),可不可以根据sender来判定是...
  • 图灵机停机问题不可判定性

    千次阅读 2017-04-09 23:04:57
    图灵机停机问题不可判定的,意思即是不存在一个图灵机能够判定任意图灵机对于任意输入是否停机。 为了证明这个问题的不可判定性,我们将基于莱斯定理(Rice’s Theorem)将其规约成另外的问题来判定某个图灵机是否...
  • 设G=(V,E)是一个无向图,如果顶点V分割为两个互不相交的子集(A,B),并且图中的每条边(i,j)所关联的两个顶点i和j分别属于这两个不同的顶点集,则称图G为二分图。 二分图判定: 定理: 一张无向图是二分图,当...
  • 问题的难度

    千次阅读 2013-12-22 23:11:46
    关于问题,我们是否都能高效解决?我们是否能够解决?... 上图将所有问题分成4个部分: 易解问题, 难解问题, 不可判定问题,高度不可判定问题。易解问题和难解问题属于具有理论上的可计算性。虽然难解问题在目前
  • NP问题概述

    2020-07-29 20:25:49
    P问题:Polynomial-time问题,可以在多项式时间内用算法进行求解的...不可判定问题(undecidable problem):"不可能“解出的问题。 多项式时间: 知乎里面看到的一个比较容易理解的解释如下: 简言之: 对于时.
  • 5-17 哥尼斯堡的“七桥问题” (25分) 哥尼斯堡是位于普累格河上的一座城市,它包含两个岛屿及连接它们的七座桥,如下图所示。 ...欧拉回路是指令笔离开纸面,画过图中每条边仅一次,且可以
  • 遇到的问题:开发中想根据test对象是否有type属性来进行不同的逻辑的操作,type=0时,原本是想要输出is true的,实际结果却是输出的is false。百思不得其解,当时真的是没想到这一层,用if进行判断,会对type进行...
  • 判定表分析示例

    千次阅读 2019-05-06 09:37:55
    问题 分析 Chap.5.1 (Lec.17) 自动售货机软件例子生成的判定表图例的第6列和第23列,分别给出: 输入条件的自然语义陈述; 输出结果的自然语义陈述;...第23列:当前售货机不可找零,投入一元硬币,并...
  • GC的判定

    千次阅读 2016-08-22 15:43:51
    2.可达性分析算法选定一个对象作为GC Roots,如果一个对象对GC Roots不可达,那么就回收。作为GC Roots的对象包括下面几种: 虚拟机栈中引用的对象。 方法区类静态属性引用的对象。 方法区中常量引用的对象。 本地...
  • 对象存活判定

    2021-05-09 16:35:33
    从GC Roots到对象不可达时,则此对象不可能再被使用 GCRoots对象: 虚拟机栈中引用的对象,如:各个线程被调用的方法堆栈中使用到的参数、局部变量、临时变量等 方法区中类静态属性引用的对象,如:Java类的引用...
  • 1、引用计数法 算法:每当有一个地方引用对象时,...问题:无法解决循环引用时的引用问题。如: public class ObjectTest { public ObjectTest instance = null; public static void main(String[] args) { ...
  • 判定表法

    千次阅读 2019-07-12 18:04:18
    (为了简化问题考虑中途断电、卡纸等因素的影响) 假定:优先警告缺纸,然后警告没有墨粉,最后警告驱动程序不对。 等价类怎么做? 定义 决策表是把作为条件的所有输入的各种组合值以及对应输出值都罗列...
  • 有限环判定算法

    2021-01-20 12:04:01
    问题: 寻找新的环的结构不变量,区分R8_8、R8_9、R8_10这3个8阶环。  {8,8,”4,0,0,8,1,5,7,48,7″,”R8_8″}, \  {8,9,”4,0,0,8,1,5,7,48,7″,”R8_9″}, \ ...不可逆元个数n1 幂等元个数n2 2次幂
  •  由于人类对自然资源的消耗, 人们意识到大约在 2300 年之后, 地球就能再居住了。于是在月球上建立了新的绿地,以便在需要时移民。 令人意想不到的是, 2177 年冬由于未知的原因, 地球环境发生了连锁崩溃, ...
  • 机器学习数据量判定

    2019-03-10 18:55:34
    **判定标准 ** 1、 数据的粒度:数据的细分程度 数据的粒度越细,数据量越大; 细粒度数据通过聚合还原到粗粒度数据,但不是越细越好; 寻找有效特征在某特定的粒度; 2、 数据量与特征量的比例 能只关注说有...
  • 可达性分析法,涉及到一个GC Roots,如果一个对象和GC Roots 没有任何引用链(不可达),则证明是可以被垃圾回收的 无论是引用计数法还是可达性分析法,都涉及到对象的引用问题 对象的引用可分为4类,强引用、软...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 622
精华内容 248
关键字:

不可判定问题