1.复杂网络的计算能力是超越图灵机的？

忘了从哪儿看到这样一个说法：图灵机原则上就能计算所有可计算的问题。而复杂相互作用网络中最简单的元胞自动机理论上与图灵机等价，那么更复杂的网络似乎是超越图灵机的。

是吗？

答案：是的，从自维基百科看到了这样一段话：Work by Hava Siegelmann and Eduardo D. Sontag has provided a proof that a specific recurrent architecture with rational valued weights (as opposed to the commonly used floating point approximations) has the full power of a Universal Turing Machine (Siegelmann,  H.T. ;  Sontag,   E.D.   (1991) .  Turing   computability   with   neural   nets .   ;Appl.   Math .  ;Lett.  4 (6): 77–80)  using a finite number of neurons and standard linear connections. They have further shown that the use of irrational values for weights results in a machine with super-Turing（超图灵） power.

我不知道它能不能做经典理论中的不可计算的问题？
如果能，那么像人脑这样的复杂相互作用构成的网络能计算的（而图灵机不能的）东西，是超越可计算理论的，还是只是对不可计算问题近似求解呢？


2.人脑有没有超越“计算”的东西？
按目前的观点，大脑中的神经网络可以看成很多简单自动机（比如说IF模型、HH模型等）的并行。这样一个自动机构成的网络的“计算”能力是不是超越目前的“可计算”理论？

上升到哲学上的话，问题是这样的：人脑能不能通过计算机模拟，人脑有没有超越“计算”的东西存在（比如说意识）？


3.自动机网络的计算能力如何度量？如何设计合理有效的算法？
我们的问题也可以更实际一点，简单一点，在可计算理论中也许可以有这样一个实际的问题：自动机构成的网络的计算能力如何度量？

自动机网络怎么设计算法去解决特定的问题？据我所知并行程序设计是很难的，好像目前还没有什么通用的算法。

［本来是看到唐常杰老师的关于可计算理论的博文时，一时兴起问的问题，整理记录下来，也许对自己对别人还有点参考价值。很多东西都只是知道一个概念，不了解具体细节，观点也许有些大、空、笼统，还有可能搞错。另外这些问题是些很数学、还有点哲学的问题。至于答案，或许就在明天，或许再过几个世纪，或许不是人类自身能解答的。欢迎大家随意评论。］

相关专题：复杂网络研究
转载本文请联系原作者获取授权，同时请注明本文来自王龙飞科学网博客。
链接地址：https://blog.sciencenet.cn/blog-335776-288651.html


下一篇：读《人工智能哲学》