561
个编辑
更改
跳到导航
跳到搜索
第175行：
第175行： − 文献中提出了许多不同于标准多带图灵机的机器模型，例如随机存取机。也许令人惊讶的是，这些模型中的每一个都可以转换成另一个模型，而不需要提供任何额外的计算能力。这些替代模型的时间和内存消耗可能会有所不同。所有这些模型的共同点是，这些机器都是以确定的方式运行的。+ 第183行：
第183行： − 然而，一些计算问题更容易用更多不寻常的资源来分析。例如，非确定型图灵机是一个允许同时检查许多不同可能性的计算模型。非确定型图灵机对我们物理上想要的计算算法没有什么影响，但是它的分支精确地捕获了我们想要分析的许多数学模型，因此非确定性时间是分析计算问题的一个非常重要的资源。+ − −
→Other machine models其他机型
Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.
Many machine models different from the standard multi-tape Turing machines have been proposed in the literature, for example random access machines. Perhaps surprisingly, each of these models can be converted to another without providing any extra computational power. The time and memory consumption of these alternate models may vary. What all these models have in common is that the machines operate deterministically.
文献中提出了许多不同于标准的'''<font color="#ff8000">多带图灵机Multi-tape Turing machines </font>'''的机器模型，例如'''<font color="#ff8000"> 随机存取机Random access machine</font>'''。也许令人惊讶的是，这些模型中的每一个都可以转换成另一个模型，而不需要提供任何额外的计算能力。这些替代模型的时间和内存消耗可能会有所不同。所有这些模型的共同点是，这些机器都是以确定的方式运行的。
However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems.
However, some computational problems are easier to analyze in terms of more unusual resources. For example, a non-deterministic Turing machine is a computational model that is allowed to branch out to check many different possibilities at once. The non-deterministic Turing machine has very little to do with how we physically want to compute algorithms, but its branching exactly captures many of the mathematical models we want to analyze, so that non-deterministic time is a very important resource in analyzing computational problems.
然而，一些计算问题更容易用更多不寻常的资源来分析。例如，'''<font color="#ff8000">非确定型图灵机 </font>'''是一个允许同时检查许多不同可能性的计算模型。'''<font color="#ff8000">非确定型图灵机 </font>'''对我们物理上想要的计算算法没有什么影响，但是它的分支精确地捕获了我们想要分析的许多数学模型，因此非确定性时间是分析计算问题的一个非常重要的资源。
===Complexity measures复杂性度量===
===Complexity measures复杂性度量===