我们知道C++模板元编程是Turing完整的,但预处理器元编程却不是.
C++ 11为我们提供了一种新形式的元编程:constexpr函数的计算.这种计算形式是图灵完备吗？我在想,因为在constexpr函数中允许递归和条件运算符(？:),它会是,但我希望有更多专业知识的人来确认.
如果有限状态机和状态机之间存在差异,我不确定我是否理解？我是不是觉得这个太难了？
我在大学里有一门名为算法分析的课程,我们目前正在研究不同的复杂性类别 - P,NP,NP-hard等.
我们已经讨论过NP完全问题作为NP与NP之间的交集,以及NP中包含的P问题.我们还讨论了一些例子,主要是NP完全问题(k-coloring,k-clique,SAT).
大多数时候,我们通过以下方式证明问题是NP完全的:
一个.找到一个不确定的算法来解决它(使用选择,成功,失败);
湾 减少已知的NP完全问题.
问题是这些问题,当在确定性机器上运行时(顺序而不是在遇到选择时同时分支)具有指数时间解决方案.
我的问题是 - 我从未遇到过在指数时间内既不能在多项式时间内解决的问题; 多项式时间问题在P中,指数时间问题通常在NP完全中.
这里有一个有用的维恩图:http: //en.wikipedia.org/wiki/Np_complete
我想知道一个问题的例子既不是在NP中,也不是在NP中.
另外,本质上是指数问题,比如生成NP-complete集的幂集？或者该名称仅适用于仅使用指数时间算法的问题,因为没有其他明显的方法可以解决它？
好的,所以我给了Rosh Oxymoron的答案,因为他实际列出了一些疑似在P和NPC之间的问题的例子.谢谢你的帮助,我实际上注意到我把这个问题放错了地方.还有:https: //cstheory.stackexchange.com/
在那里我发现了以下非常有用的回答我的问题: https://cstheory.stackexchange.com/questions/79/problems-between-p-and-npc 这是专门约我问及: https://开头cstheory .stackexchange.com/questions/52/hierarchyies-in-np-under-the-assumption-that-p-np ,如果与初始问题不完全相关,通常很有趣.
非常感谢,
担
theory complexity-theory computer-science computation-theory
我真的在努力理解这两者之间的区别.从我的教科书中,它实质上描述了差异
如果语言是图灵可识别语言的补充,那么这种语言就是可识别的.
我想这个定义我不理解的部分是:当它是图灵识别语言的补充时它意味着什么？
你究竟如何确定它是否是另一种语言的补充？
我需要帮助为下面的语言构建左线性和右线性语法？
a) (0+1)*00(0+1)*
b) 0*(1(0+1))*
c) (((01+10)*11)*00)*
对于a)我有以下内容:
Left-linear
S --> B00 | S11
B --> B0|B1|011
Right-linear
S --> 00B | 11S
B --> 0B|1B|0|1
它是否正确？我需要帮助b&c.
grammar computation-theory regular-language formal-languages
根据标题,是否可以在HTML中创建(非平凡的)quine？
我对HTML quine的定义:
在假设HTML文件中的某些字符串由浏览器呈现为纯文本的情况下,非平凡的HTML quine是非空的并且至少使用一个HTML标记.定义HTML quine
q.html,使得标准浏览器呈现的as的输出是其q.html自身的内容.
(我对这个定义的任何评论持开放态度,我现在就把它搞砸了)
HTML不是图灵完备的,因此定点定理不能用来证明它确实是可能的.
但是,这并不一定意味着HTML quine是不可能的.或者它实际上可以证明HTML quine是不可能的？
想象一下立方形的瑞士奶酪.我们通过20x20x20网格对奶酪进行建模.为简单起见,我们假设每个网格立方体完全由奶酪或完全由空气组成.在我们的瑞士奶酪立方体的上方,我们然后倒入水,只穿过立方体中的气孔穿透奶酪.水可以从顶部流到底部通过连续通道,但是如果两个立方体通过面(不仅仅是边缘或角落)连接,它可以仅从一个空气立方体流到下一个空气立方体.水也可以在弯路中流动,例如在水槽排水管中,但它可能不会在奶酪立方体的侧壁上流出.
现在让我们通过如上所述的随机分布的空气和奶酪块来实施瑞士奶酪的模型,其中奶酪p的概率和空气1-p的概率并模拟水流过奶酪以便找出,水是否流经瑞士奶酪块的底部.
通过反复模拟流经瑞士奶酪立方体的水以及奶酪和空气的不同概率,我们可以确定p与水流入瑞士奶酪立方体底部的概率之间的关系,我们将其命名为q.结果如下:
q
1 ************************
0.8 *
0.6 *
0.4 *
0.2 *
0 ***********
0 0.2 0.4 0.6 0.8 1 p
我的气魄:为什么这么奇怪的曲线？
这个问题取自德国第23届联邦信息学竞赛(2004/2005).网上没有提供"为什么这么奇怪的曲线"的答案(提供的解决方案).
我希望我能在这个问题上找到合适的位置.
我真的很感谢你的帮助,这决定了字母表中所有单词的语言是否都是{0,1}无法从同一方面读取的,是一种无上下文的语言(也就是说,它可以转换成特定的语法)规则).{ w | w <> wR }
我试图通过泵浦引理证明它不是一种无上下文的语言,但是我找不到会导致我矛盾的字符串.
有什么建议？
我正在尝试围绕 lambda 演算，以及它与语言、编译器和二进制代码的关系。lambda 演算等同于图灵机的实际含义是什么，它实际上在哪里表现出来？
我不明白 lambda 演算如何取代图灵机作为计算的理论模型。图灵机是关于改变状态的顺序指令，lambda 演算是关于对某些东西进行评估的表达式。它更抽象，就像它自己的编程语言，而不是如何实际计算某些东西、使事情发生的模型。或者让我们这样说：lambda 演算就像路线图，而图灵机就像汽车模型。这两个如何被认为是等价的？是否有可能在不实施图灵机的情况下在硬件上运行软件？
例如，lisp 编译器和语言如何与 lambda 演算相关？lambda演算在哪一层实现？就 lambda 演算的定义而言，实现是否纯粹？lambda 演算背后的理论在哪里以及如何将语法转换为正在运行的二进制文件？例如，在 lambda 演算中，数字被编码为应用于其他函数 n 次的特殊函数。然而在语法上，我们使用数字文字。所有这些公理在哪里使用？
functional-programming computability lambda-calculus turing-machines computation-theory
我知道完整的GPU是计算的庞然大物 - 包括计算的每一步和内存.显然,GPU可以计算我们想要的任何东西 - 它是图灵完成的.
我的问题是关于各种GPU上的单个着色器("流处理器"/"CUDA核心"):
图灵是否完整？
我(理论上)可以使用单个着色器计算任意输入上的任意函数吗？
我试图了解计算着色器的"规模".