"完成转换"是什么意思？

我们能否在不过多讨论理论细节的情况下给出简单的解释？

解决方案

回答

从维基百科：

Turing completeness, named after Alan
  Turing, is significant in that every
  plausible design for a computing
  device so far advanced can be emulated
  by a universal Turing machine — an
  observation that has become known as
  the Church-Turing thesis. Thus, a
  machine that can act as a universal
  Turing machine can, in principle,
  perform any calculation that any other
  programmable computer is capable of.
  However, this has nothing to do with
  the effort required to write a program
  for the machine, the time it may take
  for the machine to perform the
  calculation, or any abilities the
  machine may possess that are unrelated
  to computation.
  
  While truly Turing-complete machines
  are very likely physically impossible,
  as they require unlimited storage,
  Turing completeness is often loosely
  attributed to physical machines or
  programming languages that would be
  universal if they had unlimited
  storage. All modern computers are
  Turing-complete in this sense.

除了说"画图完整意味着'在足够的时间和空间下能够回答可计算的问题'"之外，我不知道我们怎么能做到非技术性的。

回答

这是最简单的解释：

Turing Complete系统是指可以编写程序的系统，该程序可以找到答案(尽管不能保证运行时或者内存)。

因此，如果有人说"我的新事物是图灵完成"，这意味着原则上(尽管通常不是在实践中)可以用来解决任何计算问题。

有时候这是个玩笑...一个人在vi中编写了Turing Machine模拟器，因此可以说vi是世界上唯一需要的计算引擎。

回答

我认为"全面完成"概念的重要性在于能够识别可以将其过程分解为"简单"指令的计算机(不一定是机械/电气"计算机")，该指令由越来越简单的组成通用机器可以解释然后执行的指令。

我强烈推荐带注释的图灵

@Mark我认为我们要解释的是通用图灵机的描述与图灵完成的描述之间的混合。

从实际意义上讲，图灵完备的东西是能够被编写并表示为程序的机器/过程/计算，并由通用机器(台式计算机)执行。正如其他人所提到的，尽管它没有考虑时间或者存储空间。

回答

Turing Complete意味着它至少与Turing Machine一样强大。这意味着可以由图灵机计算的任何事物都可以由图灵完整系统计算。

没有人能找到比图灵机更强大的系统。因此，暂时说一个系统是图灵完备就等于说该系统与任何已知的计算系统一样强大(请参阅Church-Turing论文)。

回答

正如韦隆·弗林(Waylon Flinn)所说：

Turing Complete means that it is at least as powerful as a Turing Machine.

我认为这是不正确的，如果一个系统与图灵机一样强大，那么该系统就是图灵完整的，也就是说，该机完成的所有计算都可以由系统完成，但系统的所有计算都可以由图灵机完成。

回答

非正式定义

图灵完整的语言是可以执行任何计算的语言。 Church-Turing论文指出，任何可执行的计算都可以由Turing机器完成。图灵机是一台具有无限随机访问内存和有限"程序"的机器，该程序指示何时应读取，写入和在该内存上移动，何时应终止并产生一定的结果以及下一步该做什么。图灵机的输入在启动之前已放入其内存中。

可以使语言不图灵完成的事物

Turing机器可以根据其在内存中看到的内容做出决策仅对整数支持+，-'，*和/`的'language'并不是图灵完整的，因为它无法做出选择根据其输入，但是图灵机可以。

Turing机器可以永远运行如果我们使用Java，Javascript或者Python并取消了执行任何循环，GOTO或者函数调用的功能，那么Turing机器就不可能完整完成，因为它无法执行从未执行过的任意计算完成。 Coq是一个定理证明者，无法表达不终止的程序，因此它不是图灵完整的。

图灵机可以使用无限内存一种与Java完全一样的语言，但是一旦它使用了超过4 GB的内存就将终止，而图灵机则无法完成，因为图灵机可以使用无限内存。这就是为什么我们实际上不能构建图灵机的原因，但是Java仍然是图灵完整的语言，因为Java语言没有限制，无法阻止它使用无限内存。这是正则表达式未完成图灵的原因之一。

图灵机具有随机访问内存一种仅允许我们通过对堆栈进行"推"和"弹出"操作来处理内存的语言并不能完成图灵的工作。如果我有一个"语言"，它只能读取一次字符串，并且只能通过从堆栈中压入和弹出来使用内存，那么它可以告诉我字符串中的每个(``以后是否都有自己的)，当看到时(并在看到)时弹出。但是，它不能告诉我以后是否每个(都​​有自己的)，以后每个[都有自己的](请注意([)]满足这个条件，但是([图灵机可以使用其随机存取存储器分别跟踪()和[]`，但是只有堆栈的这种语言不能。

图灵机可以模拟任何其他图灵机。在给定适当的"程序"后，图灵机可以采用另一图灵机的"程序"，并在任意输入下对其进行仿真。如果我们使用的语言禁止实现Python解释器，那么Turing并不是完整的。

图灵完整语言的示例

如果语言具有无限的随机访问内存，条件执行和某种形式的重复执行，则图灵可能已完成。还有更多奇特的系统仍然可以实现图灵机可以实现的所有功能，这也使它们的图灵也变得完整：

• 未分类的λ演算
• 康威的生活游戏
• C ++模板
• 序言