150
个编辑
更改
跳到导航
跳到搜索
第581行：
第581行： − + − 等价于图灵机的模型+ − + − 图灵机相当于单堆栈’’’<font color=’’#ff8000’’>下推自动机 pushdown automaton</font>’’’(PDA) ，它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对磁头左侧的磁带进行建模，使用另一个堆栈对磁头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈 PDA。+ − 在另一个极端，一些非常简单的模型变成了’’’<font color=’’#ff8000’’>图灵等价Turing-equivalent </font>’’’模型，即具有与图灵机模型相同的计算能力。+ − 常见的等价模型是’’’<font color=’’#ff8000’’>多带图灵机 multi-tape Turing machine</font>’’’、’’’<font color=’’#ff8000’’>多道图灵机 multi-track Turing machine</font>’’’、有输入和输出的机器，以及与确定型图灵机(DTM)相对的’’’<font color=’’#ff8000’’> 非确定型图灵机 non-deterministic Turing machine </font>’’’(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。+ 第607行：
第607行： − 对于实际的和教学的意图，等价的’’’<font color=’’#ff8000’’> 寄存器机器register machine </font>’’’可以作为通常的汇编’’’<font color=’’#ff8000’’> 编程语言programming language</font>’’’使用。+ − 一个有趣的问题是用具体编程语言表示的计算模型是否是图灵等价的。虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人，2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，’’’<font color=’’#ff8000’’> ANSI C</font>’’’ 并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如’’’<font color=’’#ff8000’’> Pascal</font>’’’ ，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。+
→Models equivalent to the Turing machine model
“计算进度 "图显示了三态繁忙的海狸从开始到结束的计算过程中的 "状态"（指令）进度。最右边是每一步的图灵 "完整配置"。如果机器停止并清空 "状态寄存器 "和整个纸带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。
“计算进度 "图显示了三态繁忙的海狸从开始到结束的计算过程中的 "状态"（指令）进度。最右边是每一步的图灵 "完整配置"。如果机器停止并清空 "状态寄存器 "和整个纸带，则可以使用这些“配置”在其进行中的任何地方重新启动计算（参见Turing（1936）The Undecidable 第139– 140页）。
==Models equivalent to the Turing machine model==
==图灵机的等价模型==
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
Many machines that might be thought to have more computational capability than a simple universal Turing machine can be shown to have no more power (Hopcroft and Ullman p. 159, cf. Minsky (1967)). They might compute faster, perhaps, or use less memory, or their instruction set might be smaller, but they cannot compute more powerfully (i.e. more mathematical functions). (Recall that the Church–Turing thesis hypothesizes this to be true for any kind of machine: that anything that can be "computed" can be computed by some Turing machine.)
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力(Hopcroft和Ullman p. nbsp;159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能更强大地计算(即更多的数学函数)。(回想一下，’’’<font color=’’#ff8000’’>Church–Turing理论Church–Turing thesis </font>’’’ Church–Turing 论文假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。)
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力(Hopcroft和Ullman p.159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能更强大地计算(即更多的数学函数)。(Church–Turing理论假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。)
A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard last-in-first-out semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
A Turing machine is equivalent to a single-stack pushdown automaton (PDA) that has been made more flexible and concise by relaxing the last-in-first-out requirement of its stack. In addition, a Turing machine is also equivalent to a two-stack PDA with standard last-in-first-out semantics, by using one stack to model the tape left of the head and the other stack for the tape to the right.
图灵机相当于单堆栈下推自动机(Pushdown Automaton，PDA) ，它通过放宽其栈中的“后进先出”要求，使其更加灵活和简洁。此外，通过使用一个堆栈对读写头左侧的纸带进行建模，使用另一个堆栈对读写头右侧的磁带进行建模，图灵机也等效于具有标准“后进先出”语义的双堆栈PDA。
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
At the other extreme, some very simple models turn out to be Turing-equivalent, i.e. to have the same computational power as the Turing machine model.
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
Common equivalent models are the multi-tape Turing machine, multi-track Turing machine, machines with input and output, and the non-deterministic Turing machine (NDTM) as opposed to the deterministic Turing machine (DTM) for which the action table has at most one entry for each combination of symbol and state.
常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机(deterministic Turing machine，DTM)和非确定型图灵机（ non-deterministic Turing machine , NDTM）(NDTM) ，后者的动作表对于每个符号和状态组合最多只有一个条目。
Read-only, right-moving Turing machines are equivalent to DFAs (as well as NFAs by conversion using the NDFA to DFA conversion algorithm).
Read-only, right-moving Turing machines are equivalent to DFAs (as well as NFAs by conversion using the NDFA to DFA conversion algorithm).
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.
For practical and didactical intentions the equivalent register machine can be used as a usual assembly programming language.
对于实际的和教学的意图，等价的 寄存器机器可以作为通常的汇编编程语言使用。
An interesting question is whether the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, ANSI C is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language. However, other programming languages like Pascal do not have this feature, which allows them to be Turing complete in principle. It is just Turing complete in principle, as memory allocation in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
An interesting question is whether the computation model represented by concrete programming languages is Turing equivalent. While the computation of a real computer is based on finite states and thus not capable to simulate a Turing machine, programming languages themselves do not necessarily have this limitation. Kirner et al., 2009 have shown that among the general-purpose programming languages some are Turing complete while others are not. For example, ANSI C is not Turing-equivalent, as all instantiations of ANSI C (different instantiations are possible as the standard deliberately leaves certain behaviour undefined for legacy reasons) imply a finite-space memory. This is because the size of memory reference data types, called pointers, is accessible inside the language. However, other programming languages like Pascal do not have this feature, which allows them to be Turing complete in principle. It is just Turing complete in principle, as memory allocation in a programming language is allowed to fail, which means the programming language can be Turing complete when ignoring failed memory allocations, but the compiled programs executable on a real computer cannot.
一个有趣的问题是：用具体编程语言表示的计算模型是否是图灵等价的？虽然真实计算机的计算是基于有限状态的，因此无法模拟图灵机，但编程语言本身并不一定具有这种限制。Kirner等人在2009年的研究表明，在通用编程语言中，有些语言是图灵完备的，而有些则不是。例如，ANSI C并不等同于图灵机，因为ANSI C的所有实例（由于标准出于遗留的原因，故意不定义某些行为，所以可以有不同的实例）都意味着有限空间的内存。这是因为内存引用数据类型的大小，称为指针，可以在语言内部访问。然而，其他编程语言，如Pascal，则没有这个功能，这使得它们在原则上是图灵等价的。只是原则上是图灵等价的，因为编程语言中的内存分配是允许失败的，也就是说，当忽略失败的内存分配时，编程语言可以是图灵等价的，但在真实计算机上可执行的编译程序却不能。
==Choice c-machines, oracle o-machines==
==Choice c-machines, oracle o-machines==