Automata Theory 简明教程

Turing Machine Introduction

图灵机是一种接受设备，它接受由类型 0 语法生成的语言（递归可枚举集合）。它是由艾伦·图灵于 1936 年发明的。

A Turing Machine is an accepting device which accepts the languages (recursively enumerable set) generated by type 0 grammars. It was invented in 1936 by Alan Turing.

Definition

图灵机 ™ 是一种数学模型，它由一条分成小格子的无限长胶带组成，输入内容写在胶带上。它包含一个用来读取输入胶带磁头的。状态寄存器存储图灵机的状态。在读取输入符号之后，它会用其他符号替换该符号，改变其内部状态，并向右或向左移动一个单元格。如果 TM 达到最终状态，则接受输入字符串，否则拒绝。

A Turing Machine ™ is a mathematical model which consists of an infinite length tape divided into cells on which input is given. It consists of a head which reads the input tape. A state register stores the state of the Turing machine. After reading an input symbol, it is replaced with another symbol, its internal state is changed, and it moves from one cell to the right or left. If the TM reaches the final state, the input string is accepted, otherwise rejected.

TM 可以形式上描述为一个 7 元组 (Q，X，∑，δ，q0，B，F)，其中 −

A TM can be formally described as a 7-tuple (Q, X, ∑, δ, q0, B, F) where −

  1. Q is a finite set of states

  2. X is the tape alphabet

  3. ∑ is the input alphabet

  4. δ is a transition function; δ : Q × X → Q × X × {Left_shift, Right_shift}.

  5. q0 is the initial state

  6. B is the blank symbol

  7. F is the set of final states

Comparison with the previous automaton

下表展示了图灵机与有限状态机和下推自动机的不同之处。

The following table shows a comparison of how a Turing machine differs from Finite Automaton and Pushdown Automaton.

Machine

Stack Data Structure

Deterministic?

Finite Automaton

N.A

Yes

Pushdown Automaton

Last In First Out(LIFO)

No

Turing Machine

Infinite tape

Yes

Example of Turing machine

图灵机 M = (Q，X，∑，δ，q0，B，F) 带有

Turing machine M = (Q, X, ∑, δ, q0, B, F) with

  1. Q = {q0, q1, q2, qf}

  2. X = {a, b}

  3. ∑ = {1}

  4. q0 = {q0}

  5. B = blank symbol

  6. F = {qf }

δ 由 − 给出

δ is given by −

Tape alphabet symbol

Present State ‘q0’

Present State ‘q1’

Present State ‘q2’

a

1Rq1

1Lq0

1Lqf

b

1Lq2

1Rq1

1Rqf

这里的转移 1Rq1 表示写入符号是 1，胶带向右移动，下一个状态是 q1。同样，转移 1Lq2 表示写入符号是 1，胶带向左移动，下一个状态是 q2。

Here the transition 1Rq1 implies that the write symbol is 1, the tape moves right, and the next state is q1. Similarly, the transition 1Lq2 implies that the write symbol is 1, the tape moves left, and the next state is q2.

Time and Space Complexity of a Turing Machine

对于图灵机，时间复杂度指代机器针对某些输入符号初始化时，磁带移动次数的度量，空间复杂度是指磁带上书写单元格的数量。

For a Turing machine, the time complexity refers to the measure of the number of times the tape moves when the machine is initialized for some input symbols and the space complexity is the number of cells of the tape written.

时间复杂度所有合理函数 −

Time complexity all reasonable functions −

T(n) = O(n log n)

T(n) = O(n log n)

TM 的空间复杂性 −

TM’s space complexity −

S(n) = O(n)

S(n) = O(n)