3.3 The Definition of Algorithm

直觉上的概念（algorithm）

a process according to which it can be determinded by a finite number of operations.

Hilbert's 10th problem: Given a polynomal equation, to devise an algorithm according to which it can be determined in a finite number of operations whether the equation has an integral root.

定义（algorithm （or Church-Turing thesis））

• Church提出algorithm是$\lambda$-calculus（递归函数论，从基本函数出发，能通过递归定义出的函数为算法）
• Turing提出algorithm是decidable TM
• 两者等价

Hilbert's tenth problem无解的图灵描述：

The language $\{p|p$ is a polynomal with an integral root$\}$ is not decidable.