113
个编辑
更改
跳到导航
跳到搜索
第50行：
第50行： − − Every part of the machine (i.e. its state, symbol-collections, and used tape at any given time) and its actions (such as printing, erasing and tape motion) is finite, discrete and distinguishable; it is the unlimited amount of tape and runtime that gives it an unbounded amount of storage space. − − 第65行：
第61行： − − In addition, the Turing machine can also have a reject state to make rejection more explicit. In that case there are three possibilities: accepting, rejecting, and running forever. Another possibility is to regard the final values on the tape as the output. However, if the only output is the final state the machine ends up in (or never halting), the machine can still effectively output a longer string by taking in an integer that tells it which bit of the string to output. 第77行：
第71行： − 第132行：
第125行： − − − In the words of van Emde Boas (1990), p. 6: "The set-theoretical object [his formal seven-tuple description similar to the above] provides only partial information on how the machine will behave and what its computations will look like." − − For instance, − − * There will need to be many decisions on what the symbols actually look like, and a failproof way of reading and writing symbols indefinitely. − − * The shift left and shift right operations may shift the tape head across the tape, but when actually building a Turing machine it is more practical to make the tape slide back and forth under the head instead. − − * The tape can be finite, and automatically extended with blanks as needed (which is closest to the mathematical definition), but it is more common to think of it as stretching infinitely at one or both ends and being pre-filled with blanks except on the explicitly given finite fragment the tape head is on. (This is, of course, not implementable in practice.) The tape ''cannot'' be fixed in length, since that would not correspond to the given definition and would seriously limit the range of computations the machine can perform to those of a [[linear bounded automaton]] if the tape was proportional to the input size, or [[finite state machine]] if it was strictly fixed-length. − − Definitions in literature sometimes differ slightly, to make arguments or proofs easier or clearer, but this is always done in such a way that the resulting machine has the same computational power. For example, the set could be changed from <math>\{L,R\}</math> to <math>\{L,R,N\}</math>, where ''N'' ("None" or "No-operation") would allow the machine to stay on the same tape cell instead of moving left or right. This would not increase the machine's computational power. −
无编辑摘要
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
在四元组模型中，擦除或写入符号（a<sub>j1</sub>)）和向左或向右移动读写头（d<sub>k</sub>）被指定为独立的指令。该表告诉机器（ia）擦除或写入一个符号，或者（ib）向左或向右移动读写头，然后（ii）按规定承担相同或新的状态，但在同一指令中不能同时执行（ia）和（ib）。在某些模型中，如果表中没有当前符号和状态组合的条目，那么机器将暂停; 其他模型要求填充所有条目。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
机器的每一部分（即它的状态、符号收集和在任何特定时间使用的纸带）和它的行动（如打印、擦除和纸带运动）都是有限的、离散的和可区分的；是无限的纸带和运行时间给了它无限制的存储空间。
在Hopcroft和Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：
在Hopcroft和Ullman之后，单纸带图灵机可以被正式定义为一个七元组M=⟨Q,Г,b,Σ,δ,q_0,F⟩，其中：
* Г是有限的、非空的纸带''字母符号集''；
* Г是有限的、非空的纸带''字母符号集''；
* bᕮГ，是''空白符号''（唯一允许在计算过程中的任何步骤无限频繁地出现在纸带上的符号）；
* bᕮГ，是''空白符号''（唯一允许在计算过程中的任何步骤无限频繁地出现在纸带上的符号）；
* F⊆Q是''最终状态''或''接受状态''的集合。初始纸带内容被认为是''接受''由M如果它最终停止在一个状态 F.
* F⊆Q是''最终状态''或''接受状态''的集合。初始纸带内容被认为是''接受''由M如果它最终停止在一个状态 F.
* δ: （Q \ F) Χ Г Χ {L, R}是一个偏函数，称为''转移函数''，其中 L 是左移，R 是右移。如果在当前状态和当前纸带符号上未定义，则机器停止；直观地，转移函数指定了从当前状态转移的下一个状态，哪个符号覆盖读写头指向的当前符号，以及下一个读写头运动。
* δ: （Q \ F) Χ Г Χ {L, R}是一个偏函数，称为''转移函数''，其中 L 是左移，R 是右移。如果在当前状态和当前纸带符号上未定义，则机器停止；直观地，转移函数指定了从当前状态转移的下一个状态，哪个符号覆盖读写头指向的当前符号，以及下一个读写头运动。
此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
此外，图灵机还可以有拒绝状态，使拒绝更加明确。在这种情况下，有三种可能性：接受、拒绝和永远运行。另一种可能性是将磁带上的最终值视为输出。然而，如果唯一的输出是机器最终所处的状态（或永远不停止），机器仍然可以有效地输出一个较长的字符串，通过输入一个整数，告诉它要输出字符串的哪一位。
三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
三状态繁忙的海狸（busy beaver）七元组是这样的:（关于繁忙的海狸相关的资料可以搜索“图灵机实例”了解）
* Q={A, B, C, HALT}(状态);
* Q={A, B, C, HALT}(状态);
* Г= {0, 1}(纸带符号);
* Г= {0, 1}(纸带符号);
==可视化或实现图灵机所需的其他细节==
==可视化或实现图灵机所需的其他细节==
用Van Emde Boas (1990)的话来说: “集合论对象(类似于上面的七元组描述形式)只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”
用Van Emde Boas (1990)的话来说: “集合论对象(类似于上面的七元组描述形式)只提供了关于机器将如何运行以及它的计算将是什么样子的部分信息。”
例如，
例如，
* 符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无穷尽地读写符号。
* 符号到底是什么样子的，需要有很多决策，也需要有一种万无一失的方法来无穷尽地读写符号。
* 左移和右移操作可能会使读写头在纸带上移动，但在实际构建图灵机时，更实际的做法是让纸带在读写头下来回滑动。
* 左移和右移操作可能会使读写头在纸带上移动，但在实际构建图灵机时，更实际的做法是让纸带在读写头下来回滑动。
* 纸带可以是有限的，并根据需要自动延伸出空白（这是最接近数学定义的），但更常见的是将其视为在一端或两端无限延伸，除了读写头所在的明确给定的有限片段外，都会被预先填充空白。(当然，这在实践中是无法实现的。)纸带的长度不能是固定的，因为那不符合给定的定义，而且会严重限制机器可以执行的计算范围，如果纸带与输入大小成正比，则为线性有界自动机的计算范围，如果纸带是严格的固定长度，则为有限状态机的计算范围。
* 纸带可以是有限的，并根据需要自动延伸出空白（这是最接近数学定义的），但更常见的是将其视为在一端或两端无限延伸，除了读写头所在的明确给定的有限片段外，都会被预先填充空白。(当然，这在实践中是无法实现的。)纸带的长度不能是固定的，因为那不符合给定的定义，而且会严重限制机器可以执行的计算范围，如果纸带与输入大小成正比，则为线性有界自动机的计算范围，如果纸带是严格的固定长度，则为有限状态机的计算范围。
===其他定义===
===其他定义===
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。
文献中的定义有时会稍有不同，以使论证或证明更容易或更清晰，但这总是以使所产生的机器具有相同的计算能力的方式进行。例如，集合可以从 <math>\{L,R\}</math> 改为 <math>\{L,R,N\}</math>其中N("无 "或 "无操作")将允许机器停留在同一纸带单元上，而不需要左右移动。这样不会增加机器的计算能力。