Turing Machine




A Turing Machine is 5-tuple M=(K,Σ,δ,s,H)

图灵机的当前状态可表示为 K×(Σ{})×((Σ{})(Σ{,}){e})

A configuration is a member of K×(Σ{})×((Σ{})(Σ{,}){e}), and we say (q1,w1a1u1)M(q2,w2a2u2) if

  1. writing: δ(q1,a1)=(q2,a2), a2Σ{}, w2=w1, u2=u1
  2. moving left: δ(q1,a1)=(q2,), w1=w2a2 and u2=a1u1
  3. moving right: δ(q1,a)=(q2,), w2=w1a1, u1=a2u2
    Similarly, we have the (q1,w1a1u1)M(q2,w2a2u2).

  1. formal definition M=(K,Σ,δ,s,H)
  2. Implemental-level description(diagram)
  3. high-level description "pseudo code"


what is overline a

If aΣ is any symbol, we can sometimes eliminate multiple arrows and labels by using a to mean "any symbol except a."


Recoganize Language 识别语言

Let M=(K,Σ0,Σ,δ,s,{y,h}) be a TM, we say M decides a language LΣ0 if

  1. for every wL, (s,w)M(y,), M accepts w
  2. for every wL, (s,w)M(n,), M rejects w

A language L is recursive(decidable) if it is decided by some Turing Machine.

半判定 semidecide and L(M)

L(M)={wΣo:(s,w)M(h,) for some hH}
we can said that M semidecides L(M)

Theorem: If L is recurisive, L must be recursively enumerable

Theorem: If L is recurisive, L must be recursive

	s(semidecide) --> re(recursively enumerable)
	re --> s
	d(decide) --> rl(recurive language)
	rl --> d
	rl --充分条件--> re
	subgraph 决定 

Compute function 表示函数

Let M=(K,Σ,δ,s,{h}) be a Turing machine, let Σ0Σ{,} be an alphabet, and let wΣ0. Suppose that M halts on input w, and that (s,w)M(h,y) for some yΣ0. Then y is called the output of M on input w, and is denoted M(w).
Now let f be any function from Σ0 to Σ0. We say that M computes function f if, for all wΣ0, M(w)=f(w). A function f is called recursive, if there is a Turing machine M that computes f.

证明 recursive / recursively enumerable / non-recursive / not recursively enumerable 的方法

  • 证明 recursive
    1. 定义法:构造对应的 TM
    2. 归约法:A known recursive language
  • 证明 recursively enumerable
    1. 定义法:构造对应的 TM
    2. 归约法:A known recursively enumerable language
  • 证明 non-recursive
    1. 归约法:known recursively enumerable language A
  • 证明 not recursively enumerable
    1. If A and A¯ is recursively enumerable, then A is recursive
    2. 归约法:known not recursively enumerable language A



Non-determinstic Turing Machine

a non-deterministic Turing Machine (NTM) is 5-tuple (K,Σ,Δ,s,H)

A NTM M with input alphabet Σ0 semidecides LΣ0 if for any wΣ0

  • wL iff (s,w)M(h,)
  • if wL some branch halts
  • if wL no branch halts

A NTM M=(K,Σ0,Σ,Δ,s,{y,n}) with input alphabet Σ0 decides a language LΣ0 if

  1. there is a natrual number N, depending on M and w such that there is no configuration C satisfying (s,w)MNC
  2. wL iff (s,w)M(y,)
Theorem: A NTM can be simulated by a DTM