问题标签 [computability]

如果我定义多时间函数，即图灵机可以在最大多项式（n）时间内计算的函数，其中 n 是输入的大小。这些函数的类是递归可枚举的吗？

我正在考虑开发一个处理可计算性和复杂性的应用程序。它的初始功能列表将是：

1. 接收一个函数并检查它是否可计算（即它是否属于R、RE、coRE）。
2. 接收可计算函数并检查它属于哪个复杂性类。

还有更多，这或多或少是一个方向。
你熟悉这样的应用程序吗？
如果是这样，该程序的功能是什么，我在哪里可以找到它，您能想到该程序缺少的或无法正常运行的新功能吗？

在这篇文章中，作者断言：

...该程序确实表明模板实例化机制是一种原始递归语言，可以在编译时执行非平凡的计算。

我发现这很有趣，因为我帮助教授了一门计算理论课程，该课程深入研究了原始递归函数的理论。然而，我的印象是模板元编程是图灵完备的，这是一个比说它是原始递归更严格的陈述......毕竟，创建一个无法停止的模板元程序并不是很困难.

我错过了什么吗？模板元编程是一种严格的原始递归语言，还是我认为它涵盖更广泛的程序是正确的？

我阅读了 Ken Thompson 的经典论文Reflections on Trusting Trust，他在其中提示用户写一个Quine作为他的论点的介绍（强烈推荐阅读）。

quine 是一种计算机程序，它不接受任何输入并生成其自己的源代码的副本作为其唯一输出。

天真的做法只是想说：

但是很快就会发现这是不可能的。我最终使用 Python自己编写了一个，但仍然无法解释“诀窍”。我正在寻找一个很好的解释为什么 Quines 是可能的。

我有一个执行有用任务的程序。现在，除了执行原始任务之外，我还想在编译的可执行文件运行时生成纯文本源代码。这不是quine，但可能是相关的。

此功能通常很有用，但我的特定程序是用 Fortran 90 编写的并使用 Mako 模板。编译后它可以访问原始源代码文件，但我希望能够确保在用户运行可执行文件时源存在。

这有可能实现吗？

这是一个执行简单任务的简单 Fortran 90 示例。

是否可以修改此程序以使其执行相同的任务（编译时输出字符串）并输出包含源代码的 Fortran 90 文本文件？

提前致谢

我试图理解 NPO 的定义。

我在这里阅读了定义：http: //www.nada.kth.se/~viggo/wwwcompendium/node2.html

如果我们考虑尝试找到一个最小顶点覆盖，那么 I,sol(x) 和 m 是什么？（目标是分钟）

你如何论证 lambda 演算是图灵完备的（以最简单的方式）？

假设存在图灵机 M1、M2、M3，它们识别的语言分别是 L(M1)、L(M2) 和 L(M3)。以下语言 L = {(M1, M2, M3) : L(M1), L(M2), 和 L(M3) 不相等} 语言是否可判定？递归可枚举？或者两者都不是？

我们可以使用康托尔的对角线证明所有单参数函数的集合是不可数的。例如

对于所有函数 f1 到 fn，我们可以将所有参数传递给一些 n，并将 1 传递到 n。然后通过取对角线值并将对角线值加 1，我们可以证明我们不能计算所有一个参数函数。（因为更改对角线值将产生一个唯一的未列出的行）

想知道是否有一种特殊的方法来计算两个参数函数？？？？

谢谢..

例如，不接受自己编码的图灵机的语言不能被任何图灵机接受。