150
个编辑
更改
跳到导航
跳到搜索
第557行：
第557行： − + 第566行：
第566行： − − +
→图灵机的等价模型
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.159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能更强大地计算(即更多的数学函数)。(Church–Turing理论假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。)
许多可能被认为比简单的通用图灵机有更多计算能力的机器，实际上并没有更多的能力(Hopcroft和Ullman p.159, cf. Minsky(1967))。它们可能计算得更快，或者使用更少的内存，或者它们的指令集可能更小，但是它们不能计算更多的数学函数。(邱奇-图灵理论假设这对任何机器都是正确的:任何可以被“计算”的东西都可以被某些图灵机器计算。)
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.
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
在另一个极端，一些非常简单的模型变成了图灵等价模型，即具有与图灵机模型相同的计算能力。
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) ，后者的动作表对于每个符号和状态组合最多只有一个条目。
常见的等价模型是多带图灵机、多道图灵机、有输入和输出的机器，以及与确定型图灵机(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).