561
个编辑
更改
跳到导航
跳到搜索
第152行：
第152行： − 图灵机是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。图灵机器并不是一种实用的计算技术，而是一种计算机的通用模型，从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个图灵机器来解决这个问题。事实上，这就是教会图灵论点的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如RAM机器、Conway的生命游戏、元胞自动机或任何编程语言都可以在图灵机器上进行计算。由于图灵机易于数学分析，并且被认为与任何其他计算模型一样强大，图灵机是复杂性理论中最常用的模型。+ 第159行：
第159行： − 许多类型的图灵机被用来定义复杂性类，如确定性图灵机、概率图灵机、不确定图灵机、量子图灵机、对称图灵机和交替图灵机。它们在原则上都同样强大，但当资源(如时间或空间)被限制时，其中一些可能比其他的更强大。+ 第167行：
第167行： − 确定性图灵机是最基本的图灵机，它使用一组固定的规则来决定未来的动作。机率图灵机图灵机是一种具有额外随机位的确定性图灵机。做出概率决策的能力通常有助于算法更有效地解决问题。使用随机位的算法称为随机算法。非确定型图灵机图灵机是一种确定性图灵机，具有额外的非确定性特征，它允许图灵机在给定的状态下有多种可能的未来动作。查看非确定性的一种方法是，图灵机在每个步骤中分支成许多可能的计算路径，如果它在这些分支中的任何一个中解决了这个问题，就说它已经解决了这个问题。显然，这个模型并不意味着是一个物理上可实现的模型，它只是一个理论上有趣的抽象机器，它产生了特别有趣的复杂性类。例如，请参阅非确定性算法。+ − −
→Turing machine图灵机
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.
A Turing machine is a mathematical model of a general computing machine. It is a theoretical device that manipulates symbols contained on a strip of tape. Turing machines are not intended as a practical computing technology, but rather as a general model of a computing machine—anything from an advanced supercomputer to a mathematician with a pencil and paper. It is believed that if a problem can be solved by an algorithm, there exists a Turing machine that solves the problem. Indeed, this is the statement of the Church–Turing thesis. Furthermore, it is known that everything that can be computed on other models of computation known to us today, such as a RAM machine, Conway's Game of Life, cellular automata or any programming language can be computed on a Turing machine. Since Turing machines are easy to analyze mathematically, and are believed to be as powerful as any other model of computation, the Turing machine is the most commonly used model in complexity theory.
'''<font color="#ff8000"> 图灵机Turing machine</font>'''是一般计算机的数学模型。它是一种理论上的装置，可以操纵一条带子上的符号。图灵机器并不是一种实用的计算技术，而是一种计算机的通用模型，（适用于）从先进的超级计算机到有铅笔和纸的数学家。一般认为，如果一个问题可以用一个算法来解决，那么就存在一个图灵机器来解决这个问题。事实上，这正是'''<font color="#ff8000"> 丘奇-图灵论题Church–Turing thesis</font>'''的陈述。此外，众所周知，在我们今天已知的其他计算模型上可以计算的一切，例如'''<font color="#ff8000"> RAM机器、Conway的生命游戏、元胞自动机</font>'''或任何编程语言都可以在图灵机器上进行计算。由于图灵机易于数学分析，并且被认为与任何其他计算模型一样强大，'''<font color="#ff8000"> 图灵机Turing machine</font>'''是复杂性理论中最常用的模型。
Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.
Many types of Turing machines are used to define complexity classes, such as deterministic Turing machines, probabilistic Turing machines, non-deterministic Turing machines, quantum Turing machines, symmetric Turing machines and alternating Turing machines. They are all equally powerful in principle, but when resources (such as time or space) are bounded, some of these may be more powerful than others.
许多类型的'''<font color="#ff8000"> 图灵机Turing machine</font>'''被用来定义复杂性类，如'''<font color="#ff8000"> 确定性图灵机、概率图灵机、不确定图灵机、量子图灵机、对称图灵机和交替图灵机</font>'''。它们在原则上都同样强大，但当资源(如时间或空间)被限制时，其中一些可能比其他的更强大。
A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.
A deterministic Turing machine is the most basic Turing machine, which uses a fixed set of rules to determine its future actions. A probabilistic Turing machine is a deterministic Turing machine with an extra supply of random bits. The ability to make probabilistic decisions often helps algorithms solve problems more efficiently. Algorithms that use random bits are called randomized algorithms. A non-deterministic Turing machine is a deterministic Turing machine with an added feature of non-determinism, which allows a Turing machine to have multiple possible future actions from a given state. One way to view non-determinism is that the Turing machine branches into many possible computational paths at each step, and if it solves the problem in any of these branches, it is said to have solved the problem. Clearly, this model is not meant to be a physically realizable model, it is just a theoretically interesting abstract machine that gives rise to particularly interesting complexity classes. For examples, see non-deterministic algorithm.
'''<font color="#ff8000"> 确定性图灵机Turing machine</font>'''是最基本的图灵机，它使用一组固定的规则来决定未来的动作。'''<font color="#ff8000"> 概率图灵机Probabilistic Turing machine</font>'''是一种具有额外随机位的确定性图灵机。做出概率决策的能力通常有助于算法更有效地解决问题。使用随机位的算法称为'''<font color="#ff8000">随机算法</font>'''。'''<font color="#ff8000"> 非确定型图灵机Non-deterministic Turing machine</font>'''是一种确定性图灵机，具有额外的非确定性特征，它允许图灵机在给定的状态下有多种可能的未来动作。查看非确定性的一种方法是，图灵机在每个步骤中分支成许多可能的计算路径，如果它在这些分支的任何一个中解决了这个问题，就说它已经解决了这个问题。显然，这个模型并不意味着是一个物理上可实现的模型，它只是一个理论上有趣的抽象机器，它产生了特别有趣的复杂性类。例如，请参阅 '''<font color="#ff8000"> 非确定性算法Non-deterministic algorithm</font>'''。
===Other machine models其他机型===
===Other machine models其他机型===