精华内容
下载资源
问答
  • 关于四个不可计算的决策问题
  • 用反证法。 假设存在一个可以计算停机问题的程序halting()。halting传入的参数为待判断是否可以停机的程序p,halting的返回值为1或0,若p可停机,test返回1,若p不可停机,test返回0.

    用反证法。
    假设存在一个可以计算停机问题的程序hating声明如下, 该程序计算p是否可停机并返回结果。

    int halting(p);
    

    halting的返回值可以为1或0,若p可停机,halting返回1,若p不可停机,halting返回0.

    再定义程序prove如下。

    void prove(p){
    	bool x = halting(p);
    	while(x)
    		;
    }
    

    现在,我们把prove程序作为参数p传入prove程序中。
    若prove可停机,x为1,while(1)陷入死循环,则prove不可停机。
    若prove不可停机,x为0,while(0)直接结束,则prove可停机。
    prove即可停机,又不可停机,矛盾,所以假设不成立。所以不存在可以计算停机问题的程序。

    展开全文
  • 问 题:直接载入TensorBoard 总是提示No dashboard are active for ...以上这篇解决Tensorboard 显示计算图graph的问题就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持软件开发网。
  • 二、"停机问题" 不可判定、 三、"图灵机语言是否空集问题" 不可判定、 四、"图灵机是否等价问题" 不可判定、 五、"是否存在自动机接受图灵机语言问题" 不可判定、 六、莱斯定理 ( Rice's Theorem )





    一、不可判定性 ( Undecidability )



    不可判定 ( Undecidability ) 是正常的 , 绝大多数的 计算问题 都是不可判定的 ;

    可判定的计算问题 只占 计算问题 中的 一小部分 ;


    证明思路 :

    不可数无穷 : 语言 与 计算问题 的个数是无穷的 , 其个数与实数一样多 , 是 不可数无穷 ;

    可数无穷 : 图灵机 个数也是无穷的 , 其个数与自然数一样多 , 是 可数无穷的 ;

    语言的个数 要 远远多于 图灵机个数 ;





    二、“停机问题” 不可判定



    停机问题 是不可判定的 ;

    停机问题 : 设计一个程序 , 帮助判定 “给定一个程序 , 该程序是否会停机” ;

    ① 如果知道该程序 不会停机 , 就强制停止该程序 ;

    ② 如果知道该程序 会停机 , 就耐心等待该程序执行完毕 ;


    上述 “能判定程序是否会停机” 的程序 , 是不存在的 ;





    三、“图灵机语言是否空集问题” 不可判定



    判定图灵机所认识的语言是否是空集 的问题 , 也是不可判定的 ;





    四、“图灵机是否等价问题” 不可判定



    图灵机的等价问题 , 即 判定两个图灵机是否是相互等价的 , 也是不可判定的 ;





    五、“是否存在自动机接受图灵机语言问题” 不可判定



    图灵机 所认识的语言 , 是否能够找到一个自动机认识 , 是不可判定的 ;





    六、莱斯定理 ( Rice’s Theorem )



    莱斯定理 ( Rice’s Theorem ) :

    任何一个 关于图灵机的计算问题 , 都是 不可判定的 ;

    展开全文
  • (1)- 可计算性理论与计算复杂性理论 已有 1843 次阅读 2015-6-6 00:07 |个人分类:确定性问题和算法讨论|系统分类:科研笔记|关键词:P versus NP 计算复杂性理论 可计算性理论 我们一直在解读,“P...

    什么是“判定问题”?(1)- 可计算性理论与计算复杂性理论

    已有 1843 次阅读 2015-6-6 00:07 |个人分类:不确定性问题和算法讨论|系统分类:科研笔记|关键词:P versus NP 计算复杂性理论 可计算性理论

    我们一直在解读,“P versus NP”之所以成为“世纪难题”,失足于NP定义:NP=Nondeterministic Polynomial time(不确定性多项式时间),遂有流行观念“NP是多项式时间可验证的”,与此相关,还有一个流行观念“NP是可计算的”。这些观念直接导致计算复杂性理论(Computational complexity theory)与可计算性理论(Computability theory)相分离,作为计算复杂性理论基础的NP完备理论(NP-completeness theory),就成了无源之水,无本之木!

    于可计算性理论,按人们一般的理解,顾名思义是研究“可计算性”,即研究哪些问题是可计算的,然而,若追本溯源,可以看到,此理论的目的是通过“可计算性”,研究与之相对的“不可计算性”。“可计算性”概念源于古老的西方哲学问题:思维机械化,其中心议题是设想通过将思维表达成计算,来检验和消除认知错误,正如莱布尼茨所说:

    - 纠正我们推理的唯一方式是使它们同数学一样准确、明晰,这样我们能一眼看出我们的错误,并且在人们有争执的时候,可以简单的说,让我们计算「calculemus」,而无须进一步的忙乱,就能看出谁是正确的。(The only way to rectify our reasonings is to make them as tangible as those of the Mathematicians, so that we can find our error at a glance, and when there are disputes among persons, we can simply say: Let us calculate [calculemus], without further ado, to see who is right.)

    于20世纪初,希尔伯特正式提出了利用计算机彻底系统解决所有数学问题的计划,其中的希尔伯特第10问题,又称“丢番图方程问题”,即探究求解任意的丢番图方程的算法的存在性。然而,哥德尔几乎在同时提出了“哥德尔不完备定理”,证明了不存在着这样的算法,它能正确回答有关初等数论的全部问题。接着,图灵进一步提出普遍意义上的计算机模型-“图灵机”,严格证明了不存在这样的图灵机,一般性地表达为“判定问题(Decision Problem)”,由此形成了可计算性理论的核心内容。

    于20世纪40年代,发明了基于冯·诺伊曼结构的实际计算机,计算机应用广泛开展起来,于实际应用中出现了一些计算困难的问题,“计算复杂性理论”于此创生。一般说来,计算复杂性理论研究“复杂性”,即研究那些计算困难问题的“复杂性”,库克(Cook)于1971年的那篇论文《The Complexity of Theorem Proving Procedures》,引入“Nondeterministic Turing machine(NDTM)”,将那些计算困难的问题定义为NP(Nondeterministic Polynomial time),由于NDTM的本质是图灵机(TM),遂有诸如“NP是多项式时间可验证的”、“NP是可计算的”的流行观念,其相关理论称之“NP完备理论”。

    由此可见,原本NP的提出是针对计算困难的问题,与P相对,然而NP的流行观念混淆了NP与P的本质区别,导致NP的本质“不确定性”消失,是有计算复杂性理论与可计算性理论完全脱节,这是造成现有的NP完备理论严重困难的最根本性的原因。

    展开全文
  • 在python安装完成后尝试用pip方法安装第三方库时,在cmd窗口出现“pip不是内部或外部命令,也不是运行的程序或批处理文件”的问题。 解决方法: 在控制面板——系统与安全——系统中选择高级系统设置: 选择环境...

    在python安装完成后尝试用pip方法安装第三方库时,在cmd窗口出现“pip不是内部或外部命令,也不是可运行的程序或批处理文件”的问题。
    在这里插入图片描述

    解决方法:

    在控制面板——系统与安全——系统中选择高级系统设置:
    在这里插入图片描述
    选择环境变量:
    在这里插入图片描述系统变量中选择Path:在这里插入图片描述
    可以看到,pip在Python\Python37-32\Scripts目录中:
    在这里插入图片描述
    将Python\Scripts的位置添加到路径中:
    在这里插入图片描述
    然后重新打开cmd窗口输入pip指令便可:
    在这里插入图片描述

    展开全文
  • 对于程序计算精度问题:我们往往会遇到 计算 9.999*100 得到999.9000000000001的这种结果。(原因多说,请大家自行学习了)那么问题的解决,需要转换数字的类型为decimal,本例中可以:BigDecimal("9.999&...
  • 编程问题的提出 我们是否可以编写一个程序用来测试任何可以用哥德尔数表示的程序是否会终止? 反证法 假设这样的测试程序存在,然后证明它的存在将会产生一个矛盾。 证明步骤第一步 假设测试程序存在 存在这样的一...
  • 一 Cell - Re 问题  举例, 稳态BURGER'S 方程 u du/ dx = miu * d^2 u/ d x^2 , 中心差分离散 Re(u(i + 1) - u(i) )/ 2 - ( u(i - 1) - 2 u(i) + u(i+1) ) = 0  定义单元雷诺数, Re = U * h/ miu, % h ...
  • GIS面积计算问题

    千次阅读 2017-07-06 17:37:00
    好长时间更新了,今天说点干货,项目用到的。 1、项目中要用到计算面积的,根据...需要的dll有 ESRI.ArcGIS.Client.Toolkit.dll 和 ESRI.ArcGIS.Client.dll 这两个dll即可,需要那么多的dll,到官网下载,也...
  • 博主在这一个问题上犯了两个错,本文提供的方法仅仅适用于SSD的eval.py 同样适用于解决其他项目中的voc_eval.py。 博主思考查询了一晚上,若对你有帮助,给个赞!!! 两个错误: 1、 修改voc_eval函数,出现AP,...
  • 重用计算

    2012-12-11 22:54:39
    当某个问题计算量很大时,很多时候我们都会考虑...如果按照传统方法,从数据库里一个一个查,其计算所花时间 会随着选项的增大而迅速增加,最后我么摒弃了从数据库里一个一个查的想法,而是尝试了一种全新的方法:...
  • 是关于声卡的其它什么都正常:系统服务、硬件(本来是集成声卡,我还换了PCI声卡试了)、BIOS里面的相关设置、声音驱动...最后只有建议人家别听音乐了计算机其他功能还正常的,上网、做其他事情还没事这太邪门儿了
  • 提示:文章写完后,目录可以自动生成,如何生成参考右边的帮助文档 文章目录 前言 一、pandas是什么? 二、使用步骤 1.引入库 2.读入数据 总结 前言 提示:这里可以添加本文要记录的大概内容: ...
  • 本体诊断是一种用于处理基于描述逻辑(DL)的本体中的一致的众所周知的方法,它计算本体的诊断,即本体中公理的最小子集,其移除恢复一致性。 然而,本体诊断在计算上是困难的,尤其是计算最小成本诊断(MCD),...
  • 计算几何问题不可避免的会遇到浮点数计算误差和数值溢出的问题计算结果超出浮点数表示范围)处理的问题,通常有三种基本的方法处理这种问题: 1.采用整数计算 强制所有感兴趣的坐标点位于一个固定大小的整数...
  • 前有谷歌推出的D-Wave量子计算机,号称其解决问题的能力比其他任何计算机都快出一亿倍,后有IBM、微软、Intel等公司的量子计算扩展。可以说,量子计算已经具备完整形态,未来前景十分可观。 量子计算是一种遵循量子...
  • 在目前的计算流体力学问题中,当求解N-S方程等大型科学计算问题时,存在着计算量大、耗时长的问题,对此提出了一种MPI并行算法,其中包括并行求解三对角矩阵与超松弛迭代。通过实例验证,该方法准确、可靠,并且可以...
  • 今天在计算利息的时候遇到这个问题,同事也都遇到过,但是没弄出一套标准的解决方案,做银行业务的其他问题都可以当成缺陷去修复,但是把钱算错这个问题可就严重了,所以就好好研究了一下下,闲话少说,造成这个现象...
  • NP是可计算的吗?

    2017-09-21 11:49:24
    已有 1733 次阅读 2015-12-16 16:03 |个人分类:确定性问题和算法讨论|系统分类:科研笔记|关键词:NP 可计算性 算法 在现有的NP完备理论(Theory of NP-Completeness)中,一个典型的观念就是:“NP是可计算,...
  • 可计算理论简介

    千次阅读 2004-06-26 15:28:00
    在今天,如果一个计算机科学的硕士或博士不知道什么是不可判定问题,什么是停机问题,为什么停机问题不可解,什么是NP=?P问题,也有可能会受到讥笑。因为这些问题对于计算机科学而言,太基本、太重要了,它们都属于...
  • 通信仿真时添加噪声的信噪比计算问题 我想请教一个本应该很简单的问题,觉得自己纠结了很久没有头绪。 信噪比的计算公式为: ![图片说明](https://img-ask.csdn.net/upload/201811/23/1542947077_977703.png) ...
  • 讨论的主要问题是区分两类不同的无限集:可枚举集和不可枚举集。本章只是集合论著作中更全面阐述的无限集理论内容的一部分:与计算和证明密切相关的部分。1.1节引进可枚举性的概念,1.2节则列举一些可枚举集的例子。...
  • 今天有朋友问我一个问题,一个表格中有800米比赛的时间数,此时因为某种需求,需要把所有时间都减去15秒时间,问题是该表中的时间数据是文本格式的,是计算的,有没有什么好办法。 想了想,参考网上的答案,总算...
  • 2.但是我数据源赋值是放在外面的,数组不可变,数组里的模型也不可变,所以里面的计算行高还是针对原先的行高计算 3.所以就导致会报出我cell的contentView行高计算正确,百思不得其解啊。。。搜了好久也没找到...
  • 动态规划算法与分治法类似,其基本思想也是将待求解问题分解成若干子问题,先求解子问题...如果我们能够保存解决的子问题的答案,而在需要时再找出已求得的答案,这样就避免大量重复计算,从而得到多项式时间的算法。
  • 在一个更经常被问到的问题中,围绕着编程语言、框架和库的问题,我们常常想当然地认为,计算机的基本概念是必不可少的。 但是这些电脑似乎拥有无尽的潜力,它们有任何限制吗?有使用计算机却解决不了的问题吗? ...
  • 以下是个人关于电磁波透/反射率计算问题的经验整理,如有错漏欢迎指正和补充。需要计算透/反射率的器件通常分为几种类型:1. 波导器件如各类波导分路器,光纤Bragg光栅,其入射端及出射端都满足波导模式。当入射及...
  • 由于GHOST的系统,计算机重名,所以我将有数据库的计算机名字改掉了,之后发现登录成功,网上查了下资料。最终将问题解决。   首先使用Windows身份验证,服务器名称为“.”,进入数据库,在数据库为master中...
  • 网上看了一些资料,在开发中遇到金额的计算很实用啊!! 如果需要精确计算,非要用String来够造BigDecimal不可

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 11,612
精华内容 4,644
关键字:

不可计算问题