Recursive function The Zero function The successor function f(×)=x+1 The projection function f(X1r…Xxni)=X Substitution/composition f(y1n…,yn)=fg(1)…g(Xn), where y;=g(X) 2021年1月27日星期三 BASICS 27
Recursive Function ◼ The Zero function f(x) = 0 ◼ The Successor function f(x) = x+1 ◼ The Projection function f(x1 , …, xn , i) = xi ◼ Substitution/composition f(y1 , …, yn )=f(g(x1 ), …, g(xn )), where yi=g(xi ) 2021年1月27日星期三 BASICS 27
Recursive function Recursion h(x, 0)=f(x); h (x,y+1=g, y, h(x, y eg.xy:X+0=X;X+(y+1)=(X+y)+1 Minimization the least y such that y(f(x,y)=0)≈ f(x, y) is defined for all Z<y,and f(x,y)=0 undefined if otherwise 2021年1月27日星期三 BASICS 28
Recursive Function ◼ Recursion h(x, 0) = f(x); h(x, y+1) = g(x, y, h(x, y)) e.g. x+y: x+0=x; x+(y+1)=(x+y)+1 ◼ Minimization 2021年1月27日星期三 BASICS 28
Ackermann Function The ackermann function is defined as follows (0,y)cy+1, v(x+1,0)≈v(X,1), v(X+1,y+1)~(X,v(X+1,y) The ackermann function is not primitive recursive It grows faster than all the primitive recursive functions 2021年1月27日星期三 BASICS
Ackermann Function 2021年1月27日星期三 BASICS 29 The Ackermann function is not primitive recursive. It grows faster than all the primitive recursive functions
Church Turing Thesis a fact a equivalence in terms of expressive power Church turing Thesis The computable functions are precisely the recursive functions Logical foundation of computation Computation as logical object 2021年1月27日星期三上海交通大学计算机系 BASICS实验室
2021年1月27日星期三 上海交通大学计算机系BASICS实验室 30 Church Turing Thesis ◼ Fact ◼ Equivalence in terms of expressive power ◼ Church Turing Thesis ◼ The computable functions are precisely the recursive functions ◼ Logical foundation of computation ◼ Computation as logical object
Concurrent system All Systems are Concurrent systems Concurrency is an Intrinsic Property Concurrency is a Property rather than a Definition 2021年1月27日星期三上海交通大学计算机系 BASICS实验室 31
2021年1月27日星期三 上海交通大学计算机系BASICS实验室 31 Concurrent System ◼ All Systems are Concurrent Systems ◼ Concurrency is an Intrinsic Property ◼ Concurrency is a Property Rather Than a Definition