"认为人类的思维手段只局限于Turing machine" That is called Church-Turing thesis.


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

送交者: steven 于 2010-04-02, 12:29:19:

回答: 臭棋篓子其实是AI最难对付的棋手。 由 oo8 于 2010-04-02, 10:06:08:

You don't have to believe it, just there is no counter argument.

oo8 说道:

假定有一张1000x1000的五子棋盘,黑下正中天元,臭棋篓子执白下在了棋盘中任意一点上。对于人来说臭棋篓子已经输了,但是根据steven的理论由于棋盘如此之大,电脑无法穷举所有可能,所以还胜负未定。

This the real difference between human and computer is "non-deterministic" vs deterministic. In many cases, non-deterministic is far more efficient. Turing machine cares whether a problem is solvable, but it does not care if it can be solve efficiently. Pick board game as an example, the "dumbest" way is to exhaust all possibility: for go, we are talking about 10^171 game tree over 10^361 configuration. If the Turing machine enumerates traverses through the whole game tree, that means giving any configuration, we can say, whether there is a strategy to win/draw or not. To a Turing machine, this problem is solvable, and it is end of its job.

However, this is not tractable since there is no enough resource in the universe the complete the computation. The better approach is that we can some how tell if certain branches will likely to lead to winning. There is where human to place.

Human are far more efficient in this types of "non-deterministic" approach. The brain can perform association, which gives a hint. Better trained the people are able to come up with good hints that lead to victory, but so far, no computer can ever achieve this.

NP is important because beyond NP, those problems are intractable. Even though they can be solve, but when the problem size increase a little bit, the steps require to solve the problem increase exponentially (loosely speaking). NP however, it a good hint is generated, the hints can be verified efficiently.

In general, human is not better of than computer in terms of solving problems. There are specific class of problems particularly those inherit non-deterministic in nature, human are significantly better.




所有跟贴:


加跟贴

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

标题:

内容: (BBCode使用说明