标签: computation-theory

动机:我希望能够在没有一阶函数的语言中使用玩具函数式编程,使用自然数而不是函数.

通用函数是函数f:N - >(N - > N),等价于f:N*N - > N,它枚举所有可能的可计算函数.换句话说,有一个数k使得f(k)是平方函数,有一个数j使得f(j)是第n个素函数等.

要编写这样的函数,可以使用任何图灵完备语言(编程语言编译器,lambda演算,图灵机..​​....)并枚举所有程序.我不仅要考虑评估,还要考虑添加,构图,曲线等功能.例如,给定两个函数f的指数,g我想知道函数f + g的索引是什么,或者f由g组成.这将允许"玩具功能编程".

编写这样的代码库有什么好方法？我不是在寻找一个极简主义的Turing tarpit,它很难计算10的阶乘,也不想编写高级编译器.它应该有一些基本功能,如添加和写循环的可能性,但不多.

欢迎使用所有高级语言的解决方案.Pseudocode,Haskell和Python是首选.您可以假设任意精度算术.eval不允许使用或类似.

澄清:枚举函数将包含所有部分递归(可计算)函数 - 这包括不停止某些输入的函数.在这种情况下,通用功能将悬而未决; 当然这是不可避免的.另请参见:m-recursive函数 - http://en.wikipedia.org/wiki/Μ-recursive_function.

在大学学习期间,我必须学习很多关于计算理论的知识.我研究了三个学期的主题.我很难过,我不得不承认我忘记了很多.

我想知道这是个人问题,还是我们只需要学习很多(或多或少)无用的东西.

所以我的问题是:您认为计算理论领域中哪些主题最重要,哪些部分值得学习,以及您在正常工作中使用哪些主题？

就个人而言,我很高兴我听说过语言理论(尤其是常规语言=>正则表达式 - 当它们可以应用时,何时不应用)以及不同的时间(和空间)复杂性,特别是O(n)符号.

但我们还要研究更多,包括:

• 可计算性理论
  • 停止问题
  • 半昏人问题
• 复杂性理论
  • P = NP？
• 逻辑理论
  • 命题演算
  • 谓词逻辑

听到这些话题很有意思,但我不确定深入研究它们是多么必要.

我知道这个问题是主观的,答案会因您的日常工作和个人经历而有很大不同.但是我想知道可能比我记忆中更有趣的主题.

试图做一些修改但不确定这个:

证明有限字母表中的所有语言集都是不可数的.

我有一种感觉它需要使用Cantor对角化方法 - 但我不确定如何使用它来解决这个问题.

我一直在努力应对Greplin挑战赛的第3级.对于那些不熟悉的人,问题是:

您必须找到数组的所有子集,其中最大数字是剩余数字的总和.例如,输入:

(1,2,3,4,6)

子集将是

1 + 2 = 3

1 + 3 = 4

2 + 4 = 6

1 + 2 + 3 = 6

以下是您应该运行代码的数字列表.密码是子集的数量.在上面的例子中,答案是4.

3,4,9,14,15,19,28,37,47,50,54,56,59,61,70,73,78,81,92,95,97,99

我能够编写一个解决方案来构建22个数字的所有400万个组合,然后对它们进行全部测试,这将得到正确的答案.问题是需要40多分钟才能完成.在网络上搜索似乎有几个人能够在不到一秒的时间内编写算法来获得答案.任何人都可以用伪代码解释比计算上昂贵的暴力方法更好的解决方法吗？这让我疯了!

我现在正在学习计算理论课程.我能很好地理解这些概念.我能够解决问题.而且,当我向我的导师询问真实世界的应用程序时,他告诉我这些概念在编译器设计中肯定是有用且必不可少的.但是,至少要做一个有意义的研究,我需要一些解释,如何在编码中使用这些概念.

例如,如果我想设计自己的grep.我将在C中使用字符串函数.我不知道如何在编码中使用正则表达式.

同样的情况适用于图灵机.

如果我想添加两个数字,为​​什么我必须遵循这些一元的概念.硬件是否实现了这些概念？

我正在尝试理解上下文敏感的语法,我理解为什么语言会像

1. {ww | w是一个字符串}
2. {a ⁿ b ⁿ c ⁿ | a,b,c是符号}

不是上下文,但我想知道一个类似于无类型lambda演算的语言是否与上下文相关.我想看一个简单但非玩具的例子(我考虑上面的玩具示例),一个上下文敏感语法的例子,对某些生产规则,例如,告诉一些符号串是否可以目前处于范围内(例如,在生成函数体时).上下文敏感语法是否足够强大,可以使未定义/未声明/未绑定的变量成为语法(而不是语义)错误？

在使用泵浦引理检查给定语言是否规则时,我有点困惑.

假设我们必须检查是否:

L. 语言是否接受0常规或非常规的语言？

我们知道这是常规的,因为我们可以为L构建DFA.但我想用抽取引理来证明这一点.

现在假设,我拿一个字符串w= "0000":

现在,将分字符串x = 0,y = 0和z = 00.现在应用泵浦引理i = 2,我将得到字符串"00000",这是我的语言不存在所以通过引入引理证明语言不规则.但它被DFA接受了吗？

任何帮助将不胜感激,
谢谢

我知道^ñ b ^ñ对于n> 0不是由泵引理经常但我想a*b*,以定期,因为两个A,B不必是相同的长度.有证据证明它是正常的吗？

我的问题听起来可能与你有所不同.

我是初学者,我正在学习有限自动机.我正在互联网上搜索下面给定机器的有限自动机的正则表达式.

任何人都可以帮我写上述机器的"有限自动机的正则表达式"

任何帮助将不胜感激

旅行推销员优化(TSP-OPT)是NP难问题,旅行推销员搜索(TSP)是NP完全的.但是,TSP-OPT可以简化为TSP,因为如果TSP可以在多项式时间内求解,那么TSP-OPT(1)也可以.我认为A要降低到B,B必须要比A更难.如我在下面的参考文献中所见,TSP-OPT可以降低到TSP.TSP-OPT应该比TSP更难.我很迷惑...

参考文献:(1)算法,Dasgupta,Papadimitriou,Vazirani练习8.1 http://algorithmics.lsi.upc.edu/docs/Dasgupta-Papadimitriou-Vazirani.pdf https://cseweb.ucsd.edu/classes/sp08/cse101 /hw/hw6soln.pdf

http://cs170.org/assets/disc/dis10-sol.pdf