3.3 The Definition of 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 {pp\{p|p is a polynomal with an integral root}\} is not decidable.

results matching ""

    No results matching ""