图灵完整性有多大用处?神经网络学习是否完整? [英] How useful is Turing completeness? are neural nets turing complete?

问题描述

在阅读一些有关递归神经网络的图灵完备性的论文(例如:具有神经网络的图灵可计算性，Hava T. Siegelmann和Eduardo D. Sontag，1991)时，我感到那里给出的证明是不太实用.例如，被引用的论文需要一个神经网络，该神经网络的神经元活动必须具有无穷大的准确性(以可靠地表示任何有理数).其他证明需要无限大小的神经网络.显然，这并不实际.

While reading some papers about the Turing completeness of recurrent neural nets (for example: Turing computability with neural nets, Hava T. Siegelmann and Eduardo D. Sontag, 1991), I got the feeling that the proof which was given there was not really that practical. For example the referenced paper needs a neural network which neuron activity must be of infinity exactness (to reliable represent any rational number). Other proofs need a neural network of infinite size. Clearly, that is not really that practical.

但是我现在开始怀疑，要求图灵完整性是否真的有意义.按照严格的定义，由于没有一个计算机系统能够模拟无限大的磁带，因此现在没有图灵完整的计算机系统.

But I started to wonder now if it does make sense at all to ask for Turing completeness. By the strict definition, no computer system nowadays is Turing complete because none of them will be able to simulate the infinite tape.

有趣的是，如果编程语言规范不完整，它们通常会经常打开.这一切都归结为一个问题，即它们是否始终能够分配更多的内存，以及函数调用堆栈的大小是否无限.大多数规范并没有真正指定这一点.当然，所有可用的实现方式在这里都受到限制，因此编程语言的所有实际实现方式都不是图灵完整的.

Interestingly, programming language specification leaves it most often open if they are turing complete or not. It all boils down to the question if they will always be able to allocate more memory and if the function call stack size is infinite. Most specification don't really specify this. Of course all available implementations are limited here, so all practical implementations of programming languages are not Turing complete.

因此，您可以说的是，所有计算机系统的功能都与有限状态机一样强大，而没有其他功能.

So, what you can say is that all computer systems are just equally powerful as finite state machines and not more.

这使我想到了一个问题:图灵这个术语完全有用吗?

And that brings me to the question: How useful is the term Turing complete at all?

再回到神经网络:对于神经网络的任何实际实现(包括我们自己的大脑)，它们将无法表示无限数量的状态，即通过严格定义图灵完备性，它们不是图灵完全的. 那么，神经网络图灵完善是否完全有意义?

And back to neural nets: For any practical implementation of a neural net (including our own brain), they will not be able to represent an infinite number of states, i.e. by the strict definition of Turing completeness, they are not Turing complete. So does the question if neural nets are Turing complete make sense at all?

关于它们是否像有限状态机一样强大的问题早在很早之前就得到了回答(明斯基，1954年，答案当然是:是)，而且似乎也更容易回答.也就是说，至少从理论上讲，这已经证明它们具有与任何计算机一样强大的功能.

The question if they are as powerful as finite state machines was answered already much earlier (1954 by Minsky, the answer of course: yes) and also seems easier to answer. I.e., at least in theory, that was already the proof that they are as powerful as any computer.

一些其他问题，这些问题更多地与我真正想知道的内容有关:

Some other questions which are more about what I really want to know:

• 是否有任何理论术语可以更具体地说明计算机的计算能力? (鉴于其有限的内存空间)

• Is there any theoretical term which can say something more specific about the computational power of a computer? (given its limited memory space)

您如何比较神经网络与计算机的实际实现的计算能力? (如上文所述，车削完整性没有用.)

How can you compare the computational power of practical implementations of neural nets with computers? (Turing-completeness is not useful as argumented above.)

推荐答案

指出数学模型是图灵完备的要点是要揭示该模型执行任何计算的能力，只要有足够的资源(即无限)，而不是显示模型的特定实现是否确实具有这些资源.非图灵完整模型即使在资源充足的情况下也无法处理一组特定的计算 ，这揭示了两个模型的运行方式有所不同，即使它们有限，资源.当然，要证明此属性，您必须假设模型能够使用无限量的资源，但是即使资源为有限.

The point of stating that a mathematical model is Turing Complete is to reveal the capability of the model to perform any calculation, given a sufficient amount of resources (i.e. infinite), not to show whether a specific implementation of a model does have those resources. Non-Turing complete models would not be able to handle a specific set of calculations, even with enough resources, something that reveals a difference in the way the two models operate, even when they have limited resources. Of course, to prove this property, you have to do have to assume that the models are able to use an infinite amount of resources, but this property of a model is relevant even when resources are limited.

这篇关于图灵完整性有多大用处?神经网络学习是否完整?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！