3.1 Turing Machines

有一条无限长的tape,有一个可以读、写、左移、右移的tape head.



A Turing machine is a 7-tuple (Q,Σ,Γ,σ,q0,qaccept,qreject)(Q,\Sigma,\Gamma,\sigma,q_0,q_{accept},q_{reject}), where QQ, Σ\Sigma, Γ\Gamma are all finite sets, and

  1. QQ is the set of states,
  2. Σ\Sigma is the input alphabet not containing the blank symbol \square,
  3. Γ\Gamma is the tape alphabet, where Γ\square\in\Gamma and ΣΓ\Sigma\subseteq\Gamma,
  4. σ:Q×ΓQ×Γ×{L,R})\sigma:Q\times\Gamma\rightarrow Q\times \Gamma\times\{L,R\}) is the transition function
  5. q0Qq_0\in Q is the start state,
  6. qacceptQq_{accept}\in Q is the accept state, and
  7. qrejectQq_{reject\in}Q is the reject state, where qrejectqacceptq_{reject}\neq q_{accept}
定义(TM's computation)

TM在任意时刻下的全部信息称为configuration,包含:the current state, the current tape contents, and the current head location. 特殊地:

  • The start configuration is q0wq_0w.
  • In an accepting configuration, the state of configuration is qacceptq_{accept}.
  • In an rejecting configuration, the state of configuration is qrejectq_{reject}.
  • Accepting configurations and rejecting configurations are halting configurations.

A Turing machine M accepts input ww if a sequence of configurations C1,C2,...,CkC_1,C_2,..., C_k exists, where

  1. C1C_1 is the start configuration of MM on input ww
  2. each CiC_i yields Ci+1C_{i+1}, and
  3. CkC_k is an accepting configuration

Call a language Turing-recognizable if some TM accepts it.

wMw\in M时,MMww上停机接受

wMw\notin M时,MMww上停机拒绝或不停机


图灵机面对一个输入时,有accept, reject, looping三种可能的最终结果。如果一个TM对一个language种的输入总能回答accept or reject,那么称该TM decides该language.

Call a language Turing-decidable or simply decidable if some TM decides it.

wMw\in M时,MMww上停机接受

wMw\notin M时,MMww上停机拒绝

results matching ""

    No results matching ""