Wikipedia:Sandbox

Neural Automata (NA) are neural networks that emulate either any particular Turing Machine (TM) or the Universal Turing Machine (UTM) in general. Therefore, they are capable of executing arbitrary partially computable functions.

General Introduction

NA ultimately present a theoretical framework for dissecting symbolic representations and computations (i.e. neural code) directly from neuronal data. Thus the ultimate question of this framework is as follows: assuming that the brain performs computations then how to understand these computations in the light of TM and how are these implemented in the brain? This is achieved by employing algebraic representation theory, which allows to map TM to biologically plausible neural network models and subsequently compare (or correlate) the observables of the model with neuronal data (e.g. from central pattern generators); see Figure 1. Moreover, the symbols and computations are mapped onto the neural network’s activation functions, synapses and network architecture, which implies that theoretical principles can be developed to unravel how memory and computations are achieved by neurophysiological processes.

Aim: Mapping Turing machines to biologically plausible neural network to ultimately extract the neural code.

Representation of Turing Computations in NA

Algebraic representation theory together with [[Vector Symbolic Architectures]] (VSA) enables the passage from a symbolic space (${\textstyle S}$) to a vectorial space (${\textstyle V}$). This is necessary since the space of symbols is not endowed with sufficient mathematical structure and indeed measurements and observables are real numbers. Abstractly, one defines a map, ${\textstyle \pi :S\rightarrow V}$, that allows to combine different elements of the symbolic space (i.e. ${\textstyle s\in S}$) and represent them uniquely in terms of the canonical elements of the basis vectors of the vectorial space (${\textstyle \pi (s)\in V}$). Moreover, Turing computations (${\textstyle \lambda :S\rightarrow S}$) defined on the space of symbols can also be realized via some representation (${\textstyle \Lambda :V\rightarrow V}$) defined on the vector space. Finally, it is crucial that the map ${\textstyle \pi }$ is structure-preserving by satisfying the commutative diagram shown in Figure 2. In other words, this mapping is well-defined if it satisfies the relation ${\textstyle \Lambda (\pi (s))=\pi (\lambda (s))}$.

File:Comdiag.png

Commutative map and structure preserving map ${\textstyle \pi }$.

Specific Implementation of NA

NA have been introduced by G. Carmantini, P. beim Graben, M. Desroches, and S. Rodrigues as parsimonious, transparent and modular neural network implementations of Nonlinear Dynamical Automata (NDA). This makes them contrasting with Google DeepMind’s Neural Turing Machines (NTM), which are actually neural implementations of conventional von Neumann computers, requiring gradient descent learning of at least 60,000 parameters.

The construction of NA relies essentially on fundamental insights of automata and dynamical systems theory. The complete mapping is shown in Figure 3. In a first step, NDA are built from symbolic dynamics, shift spaces, and Gödel encodings, as a particular instance of VSA, making NA completely transparent and hence explainable.

A complete mapping from Turing machines to neural networks.

In a second step, the resulting nonlinear dynamics is mediated by piecewise affine-linear maps that are defined over fractal domains of an appropriately constructed state space. This state space is given as the unit square embedded into a two-dimensional real vector space. Each dimension Gödel-encodes the tape of a Turing machine in one direction from its read/write head.

In a final third step, the NDA is implemented as a recurrent neural network, comprising three modules. The machine configuration layer consists of two neurons with activation space ${\textstyle [0,1]}$ representing the machine configuration in the unit square. The branch selection layer carries out a classification task for deciding which branch of the piecewise affine-linear NDA map is required for the next computation. The linear transformation layer stores the parameters of the NDA map and transforms the present state of the machine configuration layer to its successor.

Compared to previous neural implementations of TM in computational neuroscience, NA are much more parsimonious, implemented with only some 200 neural units. They do not require any training as their architecture and synaptic connectivity are explicitly and transparently constructed from the TM’s transition table.

NA are different from Neural Field Automata (NFT), which implement NDA by means of Dynamic Neural Fields (DNF).

Example

In the introductory publications,, NA have been used to construct [[central pattern generator]]s (CPG) as finite-state automata, and a diagnosis-repair parser for ambiguous context-free grammars from an interacting automata network (IAN) in a modular way. Together with neural observation models, they allow for correlation analyses with neurophysiological data from cognitive neuroscience, e.g. simulated ERP, MEG, or fMRI.

The animated Figure [fig:4] shows the dynamics exhibited by the machine configuration layer for the processing of the linguistic example in . It refers to a psycholinguistic experiment conducted in German language using event-related brain potentials (ERP). Since German allows for relatively free word order, sentences are not restricted to the canonical subject-verb-object rule (SVO) of English. Thus, two kinds of experimental conditions (1) control sentences with “normal” SO structure and (2) sentences with deviant OS structure have been presented to the subjects of the study. In the ERP experiment a late positivity (P600), reflecting a “garden path” caused by syntactic diagnosis and repair processes for OS sentences has been reported.

In the simulation, one neural unit encodes the content of the stack, the other one that of the remaining input of a pushdown automaton processing a context-free grammar (for details see . In analogy to the ERP study, many realizations of the NA dynamics have been simulated, starting from randomly prepared initial conditions. The moving rectangles shown in Figure [fig:4], represent the envelopes of clouds of individual microstates that can be regarded as neural macrostates.

Figure 4 presents synthetic ERPs of the simulation from Figure [fig:4] ,. These are mean activations of the NA, averaged over all network units and over all realizations.

Synthetic ERP of an NA, processing canonical SO sentences (“normal”) versus deviant OS sentences (“garden path”).

Obviously the network observable indicates a difference when processing deviant OS sentences in comparison to “normal” SO sentences.

The results shown in Figure 4 could be used for further correlation analysis between neurophysiological observables and simulated data from NA.