You understanding is incorrect. Your "Church-Turing Thesis" is ill-stated.


所有跟贴·加跟贴·新语丝读书论坛

送交者: steven 于 2010-03-30, 01:00:13:

回答: 这就是你说的邱奇—图灵命题吧? 由 JFF 于 2010-03-29, 23:12:22:

In church turing thesis, effectively calculable means:
引用:

always gives some answer rather than ever give no answer;
always give the right answer and never give a wrong answer;
always be completed in a finite number of steps, rather than in an infinite number;
work for all instances of problems of the class.

Computable, decidable and solvable are equivalent here, meaning that it is possible to find an answer. There are a lot more uncomputable/undecidable/unsolvable problems than those solvable. A typical unsolvable problem is Halting problem.

Turing Machine, recursive function and unrestricted language are equivalent, hence anything that can be described by languages including natural languages which in context free, and is a proper subset of unrestricted language, is computable. Computable is not limited in numerical, but also symbolic.




所有跟贴:


加跟贴

笔名: 密码: 注册笔名请按这里

标题:

内容: (BBCode使用说明