Turing machine aA Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules tape head transition function (a table of instructions an action table) a state register Reference Elements of the theory of computation Harry lewis Introduction to Theory of Computation, Michael Sipser 2021年1月27日星期三上海交通大学计算机系 BASICS实验室 22
2021年1月27日星期三 上海交通大学计算机系BASICS实验室 22 Turing Machine ◼ A Turing machine is a theoretical device that manipulates symbols on a strip of tape according to a table of rules ◼ tape ◼ head ◼ transition function (a table of instructions, an action table) ◼ state register ◼ Reference ◼ Elements of the theory of computation, Harry Lewis ◼ Introduction to Theory of Computation, Michael Sipser
Turing Machine Offset print raised for a mark electric eye looking Eraser at tape sayare Offset-printing eraser roller tractor hole indexing hole TAPE n0o000 mark on tape blank square motors mark in process of erasure HEAD scanned I Ourrent Ourrent symbolTABLE state A state B state C M Print, Erase 4Left, Right Write Move Next Write Mowe Next Write Move Next symbol. tape state tape symb is0| RB L B tape symbol is 1 1 N HALT Control unit A fanciful mechanical Turing machine's TAPE and HEAD. The TABLE instructions might be on another read only"tape, or perhaps on punch-cards. Usually a" finite state machine"is the model for the TABLE 2021年1月27日星期三 BASICS 23
Turing Machine 2021年1月27日星期三 BASICS 23
入- Calculus Computation as Term Rewriting Term t:= X variable tt application λ x, t abstraction Reduction (Axt)s→>t{s/x Examples: (λxXx)(X×x)→>(AXX)(Xx) u(λ×t)s)→>u(t{sX}) (Axf(××)(xxf(××)→f(xf(x×)(x.f(x×) 2021年1月27日星期三上海交通大学计算机系 BASICS实验室
2021年1月27日星期三 上海交通大学计算机系BASICS实验室 24 -Calculus ◼ Computation as Term Rewriting ◼ Term t := x variable tt’ application x.t abstraction ◼ Reduction (x.t)s → t{s/x} Examples: (x.xx) (x.xx) → (x.xx) (x.xx) u((x.t)s) → u(t{s/x}) (x.f(xx)) (x.f(xx)) → f((x.f(xx)) (x.f(xx)))
Fixed point theorem For all lambda expressions f there exists X such that fx=x Pro. Suppose W≡x( xX) and X≡WW X≡WW≡(XF(XXW=F(WW)≡F
Fixed Point Theorem ◼ For all lambda expressions F there exists X such that FX=X. Proof. Suppose W ≡ x.F(xx) and X≡WW. X ≡ WW ≡ (x.F(xx))W = F(WW) ≡ FX
Recursive function Computable Functions as Recursive Functions Basic idea Some initial functions Some rules to compose new functions Composition Recursion Minimalization 2021年1月27日星期三上海交通大学计算机系 BASICS实验室
2021年1月27日星期三 上海交通大学计算机系BASICS实验室 26 Recursive Function ◼ Computable Functions as Recursive Functions ◼ Basic Idea ◼ Some initial functions ◼ Some rules to compose new functions ◼ Composition ◼ Recursion ◼ Minimalization