问题标签 [turing-complete]

我知道 C++ 是不可判定的。但它是递归可枚举的吗？

让我们将一组有效的 C++ 程序定义为当前 C++ 标准下任何定义良好的程序。

是否有可能构建一个总能在有限时间内识别有效 C++ 程序的编译器？

还是它是递归可枚举的？

是否有可能构建一个总能在有限时间内识别无效C++ 程序的编译器？

或者两者都不是？

如果我有一个只包含一个功能符号的逻辑编程子集，我能做所有事情吗？

我认为我不能，但我完全不确定。如果编程语言是图灵完备的语言，它可以做任何用户想做的事情。我被教导这意味着它必须能够执行 if..then..else 命令、递归和应该定义自然数。

任何帮助和意见将不胜感激！

我一直在阅读各种类型系统和 lambda 演算，我发现 lambda 立方体中的所有类型化 lambda 演算都在强归一化，而不是图灵等价物。这包括 System F，简单类型的 lambda 演算和多态性。

这使我想到了以下问题，我一直无法找到任何可以理解的答案：

• （例如）Haskell 的形式主义与它表面上基于的微积分有何不同？
• Haskell 中的哪些语言特性不属于 System F 形式主义？
• 允许图灵完成计算所需的最小更改是多少？

非常感谢任何帮助我理解这一点的人。

This answer says

1. Here is a basic y-combinator in lambda calculus:

   Y f = (\x -> f (x x)) (\x -> f (x x))

Ie Something like this in Clojure:

2. Here is another expression of the y-Combinator (step 2 of the argument)

3. We have encoded a Turing complete language (since we used the y-Combinator) (step 3 of the argument)

My question is: Why does the y-combinator provide Turing equivalence? It seems it was just an assumption of the argument.

VHDL图灵完整吗？我的理解是 VHDL 创建了一个寄存器机器，而没有任意 RAM 的寄存器机器不是图灵完备的。

这是准确的吗？对于寄存器机器中无法解决的问题，是否有标准方法——例如在 VHDL 之外使用 RAM，并通过 VHDL 进行管理？

我正在听 edX 课，教授强调每台能够执行这六个基本原语的机器都可以称为图灵完备。但是六个基本原语是什么？

因此，我在他们的官方文档中阅读了有关比特币脚本的内容，并发现了这一行：“脚本很简单，基于堆栈，并且从左到右处理。它故意不是图灵完备的，没有循环。 ”我试图推理很难，但无法理解为什么有人会“故意非图灵完备”的语言。这是什么原因？如果一种语言成为图灵完备的会发生什么？进一步扩展，“没有循环”是否与非图灵完备的脚本有关？

因此，在一般情况下，程序同时使用堆栈中的内存（自动管理）和堆（垃圾收集或手动管理）。

哪类程序可以编译为仅以类似堆栈的方式使用内存而没有堆分配？它仍然是图灵完备的，还有其他一些权衡（例如代码爆炸）还是一个较弱的语言类？

this is my first question on this site.

I‌ recently, study on NP. I have some confusion about this Topic, and want to propose my inference and some one verify me.

I) each NP problem can be solved in Exponential Time.

II) if P=NP then NP=NP-Complete.

III) Problem of factorization into 2-prime factor, is NP.

IV) if problem X can reduce to a known NP-Hard problem, then X must be NP-HARD.

anyone can verify my inference and learn me?‌

我创建了自己的编程语言，可以编译成图灵机指令，我想知道如何实现if(a>b) do _ end. 这是语言的定义（也可在此处获得）

变量以任意宽度动态分配，因此可以具有任意大的整数

每行可以做三件事之一，它可以调用一个函数（修改它的参数），启动一个while循环（这实际上更像是一个for循环），或者分配一个变量。

可用的函数有incr（加一，可能溢出），decr（减一，可能溢出），pop（从变量中删除最后一位），first（将变量中最重要的 0 更改为 1）和frost（更改最显着 1 到 0）。

while 循环具有以下语法，

基本上每次循环它都会<func>直到a出现错误情况。错误情况如下，incr全first1，decr全frost0，pop去掉最后一位。在 while 循环后，循环变量的所有位incr或所有位都将为 0，与and相反。While 循环必须在函数调用时结束，并且它们会在每次运行后删除其中包含的所有变量。frostfirstdecr

赋值可以根据语法做一些不同的事情。a=b意味着将变量复制b到变量所拥有的空间中，a如果b长度超过a这会导致未定义的行为，除非a是创建了最新的变量。a=b,5分配b给a左侧五个填充位（设置为零），再次溢出导致未定义的行为，除非a是创建的最新变量。a=a,0归零a。最后a=5,3将分配5 % 2**3到a3 位。

现在我可以if(a != 0) do _ end用

我的问题是如何实现其他 if 语句，如if(a==b),if(a!=b)和if(a>b)

作为第二个问题是这种语言图灵完备，我相信基于这个答案编程语言是否有最低标准是图灵完备的？. 我知道语言满足 1 到 5，但我不确定 6。