C# 4.0是否在编译时是图灵完备的？
众所周知，C++模板是图灵完备的, CSS也是图灵完备的 (!)，而C#重载决策是NP难问题（即使没有泛型）。 但是，C# 4.0（带有协变/逆变、泛型等）是否是编译时图灵完备呢？
需要正则表达式来表示有限状态自动机：1的个数为偶数且0的个数也为偶数。
我的问题可能与您听到的不同。 我是一个初学者，正在学习有限自动机。我在互联网上搜索，以找到以下给定机器的有限自动机的正则表达式。 有人能帮我编写上述机器的“有限自动机正则表达式”吗？ 任何帮助将不胜感激。
如何编写所有可计算函数的枚举？
动机：我希望能够在没有一阶函数的语言中使用玩具函数式编程，通过使用自然数代替函数来实现。 通用函数是一个函数f：N->（N->N），等价于f：N * N-> N，它枚举了所有可能的可计算函数。换句话说，有一个数字k，使得f（k）是平方函数，有一个数字j，使得f（j）是第n个素数函数等等。 ...
Datalog计算类？
Datalog并不是图灵完备的。 但是它的计算类别是什么呢？ 它是否等同于有限状态机或下推自动机(即上下文无关)...还是介于两者之间？
完全带权图和哈密顿回路
我在期中考试中遇到了一个问题。有人能解释一下答案吗？ 问题A：给定一个完全加权图G，找到一条带有最小权重的哈密顿回路。 问题B：给定一个完全加权图G和实数R，G是否有一条带有最大权重为R的哈密顿回路？ 假设有一台机器可以解决问题B。如果每次给出G和实数R来解决问题A，我们最多可以调用多少...
证明有限字母表上所有语言组成的集合是不可数的。
尝试进行一些复习，但对于这个问题不是很确定： 证明有限字母表上所有语言的集合是不可数的。 我有一种感觉，需要使用康托对角线方法 - 但我不确定你如何将其用于此问题。
正则语言的泵引理
我在使用泵引理检查给定语言是否为正则语言方面有点困惑。 假设我们要检查以下语言是否是正则语言： L. 接受偶数个 0 的语言是正则语言吗？ 我们知道它是正则的，因为我们可以为 L 构造一个 DFA。但我想用泵引理证明这一点。 现在假设我取一个字符串 w= "0000"： 现在将字...