The Finnish Artificial Intelligence Conference organized by the Finnish Artificial Intelligence Association and the University of Vaasa was held in Vaasa, Finland from August 19 to 23, 1996.
A paper published at the conference proved that the Turing machine is a recurrent neural network.
Yes, this was 26 years ago!
Let us take a look at this paper published in 1996.
Neural networks can be used for classification tasks to determine whether the input pattern belongs to a specific category.
It has long been known that single-layer feedforward networks can only be used to classify linearly separable patterns, that is, the more consecutive layers, the more complex the distribution of classes.
When feedback is introduced in the network structure, the perceptron output value is recycled, and the number of consecutive layers becomes infinite in principle.
Has the computing power been qualitatively improved? The answer is yes.
For example, you can construct a classifier to determine whether the input integer is prime.
It turns out that the size of the network used for this purpose can be finite, and even if the input integer size is not limited, the number of primes that can be correctly classified is infinite.
In this article, "a cyclic network structure composed of the same computational elements" can be used to complete any (algorithmically) computable function.
According to the basic axioms of computability theory, Turing machines can be used to implement computable functions. There are many ways to implement Turing machines.
Define programming language
. The language has four basic operations:
Here, V represents any variable with a positive integer value, j represents any line number.
It can be shown that if a function is Turing computable, it can be encoded using this simple language (see [1] for details) .
The neural network studied in this article consists of perceptrons, all of which have the same The structure of the perceptron number q can be defined as
. Among them, the perceptron output at the current moment (using 
represents) is calculated using n input 
.
Nonlinear function f can now be defined as
so that the function can Simply "cutting off" negative values, loops in a perceptron network means that perceptrons can be combined in complex ways.
Figure 1 The overall framework of the recurrent neural network, the structure is autonomous without external input, and the network behavior is completely determined by the initial state
In Figure 1 , the recursive structure is shown in a general framework: now 
and n are the numbers of perceptrons, and the connection from perceptron p to perceptron q is given by 
Scalar weight representation.
That is, given an initial state, the network state will iterate until it no longer changes, and the results can be read at the stable state or the "fixed point" of the network.
The following explains how the program
is implemented in the perceptron network. The network consists of the following nodes (or perceptrons):
. 
. 
and 
. Language
The implementation of the program includes the following changes to the perceptron network:
, use the following link to expand the network (assuming the node 
exists: 
, expand the network as follows: 
, expand the network as follows: 
, expand the network as follows: 
What needs to be proved now is that "the internal state of the network or the content of the network node" can be identified by the program state, while the network Continuity of state corresponds to program flow.
Define the "legal state" of the network as follows:
and The output of 
(as defined in 2.2) is zero (
);
has a unit output (
), all other instruction nodes have a zero output, and the
If the outputs of all instruction nodes are zero, the state is the final state . A legal network state can be directly interpreted as a program "snapshot" - if , the program counter is at line i, and the corresponding variable value is stored in in the variable node.
Changes in network status are activated by non-zero nodes.
First, focusing on the variable nodes, it turns out that they behave like integrators and the previous contents of the node are looped back to the same node.
The only connections from variable nodes to other nodes have negative weights - that's why nodes containing zeros don't change, because of non-linearity (2).
Next, the instruction node is explained in detail. Assume that the only non-zero instruction node is at time k---this corresponds to the program counter at line i in the program code .
If line i in the program is , then the behavior of the network taking one step forward can be expressed as ( Only affected nodes shown)
It turns out that the new network state is legitimate again. Compared to the program code, this corresponds to the program counter being moved to line i 1.
On the other hand, if line i in the program is 
, then the behavior of one step forward is
In this way, in addition to moving the program counter to the next line, the value of the variable V will also be decremented. If line i were
, the operation of the network would be the same except that the value of variable V is increased.
The conditional branch operation (IF GOTO 
j) at line i activates a more complex sequence of operations :
##Finally,
It turns out that in these After the step, the network state can again be interpreted as another program snapshot.
The variable value has been changed and the token has been moved to the new location as if the corresponding program line had been executed.
If the token disappears, the network state no longer changes - this can only happen if the program counter "exceeds" the program code, which means the program terminates.
The operation of the network is also similar to the operation of the corresponding program, and the proof is completed.
3 ModificationIt is easy to define additional streamlined instructions that can make programming easier, And the generated program is more readable and executes faster. For example, the unconditional branch (GOTO j) at line
This is a simple implementation and may not necessarily be optimal in an application.
3.2 Matrix formulation
The basic idea is to store the variable value and "program counter" in the process state s, and let the state transition matrix
Arepresent the node links between. The operation of the matrix structure can be defined as a discrete-time dynamic process
where the nonlinear vector-valued function 
is now defined element-wise as in (2).
The contents of the state transition matrixA are easily decoded from the network formula - the matrix elements are the weights between nodes.
This matrix formula is similar to the "concept matrix" framework proposed in [3].
Suppose you want to implement a simple function y=x, that is, input the value of the variable x Should be passed to the output variable y. Using language 
this can be encoded as (so that the "entry point" is now not the first line but the third line):
The generated perceptron network is shown in Figure 2.
The solid line represents a positive connection (weight is 1), and the dotted line represents a negative connection (weight is -1). Compared with Figure 1, the network structure is redrawn and simplified by integrating delay elements in the nodes.
Figure 2 Network implementation of a simple program
In matrix form , the program above would look like
The first two rows/columns in matrix A correspond to the variables connected to represent the two Links to the nodes Y and X, the next three lines represent the three program lines (1, 2, and 3), and the last two represent the additional nodes required for the branch instruction (3 ' and 3'').
Then there are the initial (before iteration) and final (after iteration, when the fixed point is found) states
If the value of the variable node will be kept strictly between 0 and 1, the operation of the dynamic system (3) will be linear and the function will have no effect at all.
In principle, linear systems theory can then be used in the analysis.
For example, in FIG. 3 , the eigenvalues of the state transition matrix A are shown.
Even if there are eigenvalues outside the unit circle in the above example, the nonlinearity makes the iteration always stable.
It turns out that the iteration always converges after 
steps, where 
.
Figure 3 "Characteristic value" of a simple program
The results show that Turing machines can be encoded as perceptron networks.
By definition, all computable functions are Turing computable - within the framework of computability theory, no more powerful computational system exists.
This is why, it can be concluded -
The recurrent perceptron network (shown above) is a Turing machine (yet another) form.
The advantage of this equivalence is that the results of computability theory are easy to obtain - for example, given a network and an initial state, it is impossible to judge the process Will it eventually stop.
The above theoretical equivalence does not say anything about computational efficiency.
The different mechanisms that occur in the network can make some functions better implemented in this framework compared to traditional Turing machine implementations (which are actually today's computers).
# At least in some cases, for example, a network implementation of an algorithm can be parallelized by allowing multiple "program counters" in the snapshot vector.
The operation of the network is strictly local, not global.
An interesting question arises, for example, whether the NP-complete problem can be attacked more effectively in a network environment!
Compared to the language
, the network implementation has the following "extensions":
, in which all numbers represented are rational numbers.
Compared with the original program code, the matrix formula is obviously a more "continuous" information representation than the program code - the parameters can be modified (often), but the iteration results are not will change suddenly.
This "redundancy" may be useful in some applications.
For example, when using a genetic algorithm (GA) for structural optimization, the random search strategy used in the genetic algorithm can be made more efficient: after the system structure changes, the continuous cost can be searched Local minima of functions use some traditional techniques (see [4]).
By learning the finite state machine structure through examples, as described in [5], it can be known that the method of iteratively enhancing the network structure is also used in this more complex situation.
Not only neural network theory may benefit from the above results - just looking at the dynamic system formula (3), it is obvious that all phenomena found in the field of computability theory are also known in simple terms Form exists - looking for non-linear dynamic processes.
For example, the undecidability of the halting problem is an interesting contribution to the field of systems theory: for any decision process represented as a Turing machine, there are dynamic systems of the form (3) that violate this process - It is not possible to construct a general stability analysis algorithm for e.g.
There are some similarities between the network structure presented and the recursive Hopfield neural network paradigm (see, e.g. [2]).
In both cases, the "input" is encoded as the initial state in the network, and the "output" is read from the final state of the network after iterations.
The fixed point of the Hopfield network is a pre-programmed pattern model, and the input is a "noise" pattern - the network can be used to enhance damaged patterns. The outlook (2) of the nonlinear function in
makes the number of possible states in the above-mentioned "Turing network" infinite.
Compared with the Hopfield network where the unit output is always -1 or 1, it can be seen that in theory, these network structures are very different.
For example, while the set of stable points in a Hopfield network is limited, programs represented by Turing networks often have an infinite number of possible outcomes.
The computational capabilities of Hopfield networks are discussed in [6].
Petri net is a powerful tool for event-based and concurrent system modeling [7].
Petri net consists of bits and transitions and the arcs connecting them. Each place may contain any number of tokens, and the distribution of tokens is called the mark of the Petri net.
If all of a transformation's input positions are occupied by markers, the transformation may trigger, removing a marker from each input location and adding a marker to each of its output locations.
It can be proved that extended Petri nets with additional suppressing arcs also have the capabilities of Turing machines (see [7]).
The main difference between the above-mentioned Turing net and Petri net is that the framework of Petri net is more complex and has a specially customized structure, which cannot be expressed by simple general form (3).
Reference
##1 Davis, M. and Weyuker, E.: Computability, Complexity, and Languages---Fundamentals of Theoretical Computer Science. Academic Press, New York, 1983.
2 Haykin, S.: Neural Networks. A Comprehensive Foundation. Macmillan College Publishing, New York, 1994.
3 Hyötyniemi, H.: Correlations---Building Blocks of Intelligence? In Älyn ulottuvuudet ja oppihistoria (History and dimensions of intelligence), Finnish Artificial Intelligence Society, 1995, pp. 199--226.
4 Hyötyniemi, H. and Koivo, H.: Genes, Codes, and Dynamic Systems. In Proceedings of the Second Nordic Workshop on Genetic Algorithms (NWGA'96), Vaasa, Finland, August 19--23, 1996.
5 Manolios, P. and Fanelli, R.: First-Order Recurrent Neural Networks and Deterministic Finite State Automata. Neural Computation 6, 1994, pp. 1155--1173.
6 Orponen, P.: The Computational Power of Discrete Hopfield Nets with Hidden Units. Neural Computation 8, 1996 , pp. 403--415.
7 Peterson, J.L.: Petri Net Theory and the Modeling of Systems. Prentice--Hall, Englewood Cliffs, New Jersey, 1981.
Reference materials:
//m.sbmmt.com/link/ 0465a1824942fac19824528343613213
The above is the detailed content of Turing machine is the hottest recurrent neural network RNN in deep learning? The 1996 paper proved it!. For more information, please follow other related articles on the PHP Chinese website!
![[Web front-end] Node.js quick start](https://img.php.cn/upload/course/000/000/067/662b5d34ba7c0227.png)
