# Simulation of Turing Machine with uEAC-Computable Functions

Authors: Yilin Zhu; Feng Pan; Lingxi Li; Xuemei Ren; Qi Gao
Journal: Mathematical Problems in Engineering
 (2015)

---

## Abstract

The micro-Extended Analog Computer (uEAC) is an electronic implementation inspired by Rubel’s EAC model. In this study, a fully connected uEACs array is proposed to overcome the limitations of a single uEAC, within which each uEAC unit is connected to all the other units by some weights. Then its computational capabilities are investigated by proving that a Turing machineM can be simulated with uEAC-computable functions, even in the presence of bounded noise.


---

## Body

## 1. Introduction

Analog computer almost disappeared since the blossom of digital computer in the second half of the last century. Actually, the first “computer” in the world, the Antikythera mechanism [1], which was used to predict astronomical positions and eclipses, was an analog computer. Recently analog computer is again regaining interest, and this stems partly from the development of various unconventional computational techniques, such as quantum computation, DNA computation, and cellular automaton.The first significant paradigm of analog computer is the General Purpose Analog Computer (GPAC) [2] introduced by Shannon as mathematical model of the Differential Analyzer [3]. Shannon proved that GPAC was able to generate differentially algebraic functions, such as polynomials, the exponential functions, the trigonometric functions and sums, products, and compositions of them. More generally, he claimed that a function could be generated by a GPAC if it satisfied some algebraic differential equations. Rubel showed that the Dirichlet problem on the disc cannot be solved by a GPAC and he defined the Extended Analog Computer (EAC) [4], which was able to directly compute partial differential equations, solve the inverse of functions, and implement spatial continuity. Mycka pointed out that the set of GPAC-computable functions was a proper subset of EAC-computable functions [5]. Graca et al. proved that Turing machine could be robustly simulated by flows defined by polynomial ordinary differential equations (ODEs) [6] and pointed out that the solution of the initial value problems defined by some ODEs was computable by GPAC; hence, it followed that GPACs could simulate Turing machines. Piekarz compared the computational capabilities of the EAC and partial recursive functions and proved that EAC could generate any partial recursive function defined over N [7].In his paper that proposed the EAC model, Rubel stressed that the EAC was a conceptual computer and whether it could be realized by actual physical, chemical, or biological devices was not known. However, researches into the continuous-valued Lukasiewicz logic as a computational paradigm led to an electronic implementation of the EAC [8]. Mills and colleagues designed and built an electronic implementation inspired by Rubel’s EAC model, called the micro-Extended Analog Computer (uEAC) [9, 10], after a decade’s research [11–13]. Moreover, Mills introduced the Δ-digraph [10], a diagrammatic tool, to demonstrate the relationship of the nature, Rubel’s EAC model, and uEAC, and, particularly, he related the EAC model to uEAC by dividing the “black boxes” of the EAC model into explicit functions and implicit functions. The current version of uEAC was designed in 2005 at Indiana University [10, 14] and had been applied to letter recognition [15, 16], exclusive-OR (XOR) problem [10, 17], Cyclotron Beam Control [18], and biologically derived circuit pattern construction [19], and so forth. It mainly consists of a conductive sheet in which currents can be injected and read at different locations, analog-to-digital and digital-to-analog converters that are used to interface the conductive sheet to the onboard controller, a microprocessor that controls the input/output array and emulates Lukasiewicz logic array (LLA) functions. The topology of the conductive sheet, the material from which it is constructed, and the boundary-valued LLA functions determine the computation of the uEAC forms. In the present study, a fully connected single-input, single-output uEACs array is proposed and its computational capabilities are investigated by showing that any Turing machine M can be simulated with uEAC-computable functions, even in the case that some noise is added to the initial configuration of M or during the iteration of the system. Turing machine [20] is the standard paradigm for digital computation since the work of Turing in the 1930s; we will prove the main result of this paper by constructing a robust simulation of Turing machine M with uEAC-computable functions.The paper can be outlined as follows. Section2 provides some basic notations about Turing machine, Rubel’s EAC model, and the uEAC. The fully connected uEACs array is presented and discussed in detail in Section 3. Section 4 states the main result of this paper: a Turing machine M can be robustly simulated by uEAC-computable functions, even in the presence of bounded noise. We prove the theorem in Section 5 by constructing a robust Turing machine M simulation with uEAC-computable functions. Some conclusions and suggestions are given in Section 6.


## 2. Preliminaries

### 2.1. Turing Machine

A Turing machine can be seen as a state machine; at each moment the machine is in one of a finite number of states. It has an infinite one-dimensional tape which is divided into cells and accessed by a read-write head. By infinite one-dimensional tape, we mean that the cells are arranged in a left-right orientation, and the tape has a leftmost cell and stretches infinitely far to the right. Each cell contains one symbol; the read-write head can move left and right along the tape to scan successive cells.The action of a Turing machine is determined completely by (1) the current state of the machine, (2) the symbol in the cell being scanned by the head, and (3) a table of transition rules. At each step, the machine reads the symbol under the head and then checks the transition rule and executes two operations: writing a new symbol into the current cell under the head of the tape and moving the head one position to the left or to the right or making no move. The tape head moves in the following manner: R means moving one cell to the right, L means moving one cell to the left if there are cells to the left, and N means not to move. If the machine reaches a situation in which no transition rule will be carried out, then the machine halts.Definition 1.
A single tape Turing machine is4-tuple  M=Q,Σ,δ,q0, where(i)
Qis a nonempty finite set of states;(ii)
Σ is the tape alphabet that describes the contents of cells of the tape;(iii)
δ:Q×Σ→Q×Σ×{L,N,R} is the transfer function;(iv)
q0∈Q is the initial state.Example 2.
Consider an example of single tape Turing machineM={q0,q1,q2},Σ,δ,q0 with three states {q0,q1,q2} and q0 is the initial state. As discussed above, let B be a blank symbol and Σ={1,B}. The transfer function δ is given by Table 1.
Given the inputω=1mBB1n, the computation performed by the machine is(1)q0,/1mBB1n,q0,1/1m-1BB1n,q0,12/1m-2BB1n,⋮q0,1m/BB1n,q1,1mB/B1n,q2,1mB1/1n,q2,1mB1B/1n-1,where the symbol “/” marks the position of the read-write head.Table 1
Transfer functionδ of the Turing machine M.
δ
1
B
q
0
q
0
,
1
,
R
q
1
,
B
,
R
q
1
q
1
,
1
,
R
q
2
,
1
,
R
q
2
q
2
,
B
,
N
q
2
,
B
,
RIn Figure1, states of the Turing machine {q0,q1,q2} are represented by circles, with the concentric circle being the initial state q0. A transition is represented as a labeled arrow with 3 tuples; the first term is the content of the cell under the read-write head, the second one is the content of the cell after this transition, and the third one is the movement of the read-write head.Figure 1
The computation performed by the Turing machineM.


### 2.2. Rubel’s EAC Model and the uEAC

In Rubel’s definition, the EAC works on a hierarchy of levels, getting more versatile as one goes to higher levels in the hierarchy. At the lowest level0, it produces and manipulates real polynomials of any finite number of real variables (x1,x2,…,xk), while, at level 1 and higher, it produces differentially algebraic real-analytic functions (Cω). The outputs of the machine at level N-1 can be used as inputs at level N or higher. An important feature of the EAC is that it is “extremely well-posed,” which means that when the inputs at some level are modified by small errors, then the outputs differ from the original outputs only by a small amount on each compact set.Definition 3.
The functiony∈Cω is generated by EAC at level N≥1  (y∈EACN), if y is a function such that (i)
y(x1,x2,…,xk)=u1(x1,x2,…,xk)+u2(x1,x2,…,xk), where u1,u2∈EACN-1;(ii)
y(x1,x2,…,xk)=u1(x1,x2,…,xk)×u2(x1,x2,…,xk), where u1,u2∈EACN-1;(iii)
y(x1,x2,…,xk)=v(u1(x1,x2,…,xk), u2(x1,x2,…,xk),…,um(x1,x2,…,xk)), where v,u1,u2,…,um∈EACN-1;(iv)
y(x1,x2,…,xk)={xk+1,xk+2,…,xk+l}  =  {f1(x1,x2,…,xk),f2(x1,x2,…,xk),…,fl(x1,x2,…,xk)}, and {xk+1,xk+2,…,xk+l} is the solution of(2)y1x1,x2,…,xk,xk+1,xk+2,…,xk+l=0,y2x1,x2,…,xk,xk+1,xk+2,…,xk+l=0,⋮ylx1,x2,…,xk,xk+1,xk+2,…,xk+l=0,wheref1,f2,…,fl are Cω functions and y1,y2,…,yl∈EACN-1;(v)
y(x1,x2,…,xk)=Df(x1,x2,…,xk)=∂α1+α2+⋯+αnf/∂x1α1∂x2α2⋯∂xkαk, where f∈EACN-1;(vi)
y(x1,x2,…,xk)={Ω,Ω′}∈EACN+1/2, for any y′∈EACN defined on set Λ, where(3)Ω=x1,x1,…,xk∈Λ:y′x1,x1,…,xk>0,Ω′=x1,x1,…,xk∈Λ:y′x1,x1,…,xk≥0.Moreover, for any function(y,Ω) produced at level N and for any subset Ω∗ of Ω produced at level N-1/2, the function (y|Ω∗,Ω∗) can be produced at level N;(vii)
y(x1,x2,…,xk)=y∗, y∗ is a unique analytic continuation of y from Ω∩Ω∗ to all Ω∗, where (y,Ω)∈EACN and Ω∩Ω∗≠∅;(viii)
y(x1,x2,…,xk) is a solution of a set of differential functions of the form(4)Fx1,x2,…,xk:y′,y1′,y2′,…,yl′=0on setΩ  subject to certain boundary requirements, where Ω∈EACN-1/2, y′∈EACN-1, and y′,y1′,y2′,…,yl′ are partial derivatives of y;(ix)
for(x1,x2,…,xk)∈Ω and (x10,x20,…,xk0)∈γ,(5)yx10,x20,…,xk0=limx1,x2,…,xk→x10,x20,…,xk0⁡y′x,wherey′∈EACN-1, Ω∈EACN-1/2, and γ∈EACN-1/2 are subsets of ∂Ω.The EAC is an extension of Shannon’s GPAC. Rubel proved that everyCω-function that could be computed by a GPAC could also be computed by an EAC [4], and, moreover, Euler’s gamma function Γ(x) and Riemann zeta function ζ(s) can also be computed by an EAC [21], while the GPAC cannot solve these problems. Rubel stressed that the EAC was a conceptual computer and whether it could be realized by actual physical, chemical, or biological devices was not known, and most computer scientists also regarded the EAC as a machine that was theoretically impossible to be built. However, Mills and his colleagues designed and built an electronic implementation inspired by the EAC, the micro-Extended Analog Computer (uEAC), and the current version was designed in 2005. Readers who are interested in the hardware of the uEAC are referred to [8, 10, 14] for more details.Suppose that currentI is injected to the conductive sheet at location O. The distances from O to two arbitrary points i, j on the same radius are ri, rj, respectively, and Vij is the voltage between i and j. Without loss of generality, we suppose that j is located outside of i and there are m resistances between i and j, the length of every resistance is Δr (i.e., rj-ri=Δr·m), and we have(6)Vij=InR1+R2+⋯+Rm=In∑k=1mρ·Δrri+2k-1·Δr/2·2π/n.Let Δr→0; we have(7)Vij=Iρ2π∫rirjdrr=Iρ2πln⁡rjri,where ρ is the electrical resistivity of the conductive sheet. Let kij=ρ/2πln⁡rj/ri, then Vij=I·kij, and we note that kij is dependent on ρ, ri, and rj; in other words, once the current input locations and voltage output locations on the conductive material are fixed, kij is a positive constant and can be seen as a coefficient of the input current I and output voltage Vij. The output of uEAC is L(Vij), where L is the LLA basic function [22].The uEAC is based on the resistance property of the conductive sheet, which makes its input-output relation linear; thus a single uEAC unit is very limited when applied to nonlinear problems. In the next section, we present a fully connected uEACs array to expand the computation capabilities of uEAC.


## 2.1. Turing Machine

A Turing machine can be seen as a state machine; at each moment the machine is in one of a finite number of states. It has an infinite one-dimensional tape which is divided into cells and accessed by a read-write head. By infinite one-dimensional tape, we mean that the cells are arranged in a left-right orientation, and the tape has a leftmost cell and stretches infinitely far to the right. Each cell contains one symbol; the read-write head can move left and right along the tape to scan successive cells.The action of a Turing machine is determined completely by (1) the current state of the machine, (2) the symbol in the cell being scanned by the head, and (3) a table of transition rules. At each step, the machine reads the symbol under the head and then checks the transition rule and executes two operations: writing a new symbol into the current cell under the head of the tape and moving the head one position to the left or to the right or making no move. The tape head moves in the following manner: R means moving one cell to the right, L means moving one cell to the left if there are cells to the left, and N means not to move. If the machine reaches a situation in which no transition rule will be carried out, then the machine halts.Definition 1.
A single tape Turing machine is4-tuple  M=Q,Σ,δ,q0, where(i)
Qis a nonempty finite set of states;(ii)
Σ is the tape alphabet that describes the contents of cells of the tape;(iii)
δ:Q×Σ→Q×Σ×{L,N,R} is the transfer function;(iv)
q0∈Q is the initial state.Example 2.
Consider an example of single tape Turing machineM={q0,q1,q2},Σ,δ,q0 with three states {q0,q1,q2} and q0 is the initial state. As discussed above, let B be a blank symbol and Σ={1,B}. The transfer function δ is given by Table 1.
Given the inputω=1mBB1n, the computation performed by the machine is(1)q0,/1mBB1n,q0,1/1m-1BB1n,q0,12/1m-2BB1n,⋮q0,1m/BB1n,q1,1mB/B1n,q2,1mB1/1n,q2,1mB1B/1n-1,where the symbol “/” marks the position of the read-write head.Table 1
Transfer functionδ of the Turing machine M.
δ
1
B
q
0
q
0
,
1
,
R
q
1
,
B
,
R
q
1
q
1
,
1
,
R
q
2
,
1
,
R
q
2
q
2
,
B
,
N
q
2
,
B
,
RIn Figure1, states of the Turing machine {q0,q1,q2} are represented by circles, with the concentric circle being the initial state q0. A transition is represented as a labeled arrow with 3 tuples; the first term is the content of the cell under the read-write head, the second one is the content of the cell after this transition, and the third one is the movement of the read-write head.Figure 1
The computation performed by the Turing machineM.


## 2.2. Rubel’s EAC Model and the uEAC

In Rubel’s definition, the EAC works on a hierarchy of levels, getting more versatile as one goes to higher levels in the hierarchy. At the lowest level0, it produces and manipulates real polynomials of any finite number of real variables (x1,x2,…,xk), while, at level 1 and higher, it produces differentially algebraic real-analytic functions (Cω). The outputs of the machine at level N-1 can be used as inputs at level N or higher. An important feature of the EAC is that it is “extremely well-posed,” which means that when the inputs at some level are modified by small errors, then the outputs differ from the original outputs only by a small amount on each compact set.Definition 3.
The functiony∈Cω is generated by EAC at level N≥1  (y∈EACN), if y is a function such that (i)
y(x1,x2,…,xk)=u1(x1,x2,…,xk)+u2(x1,x2,…,xk), where u1,u2∈EACN-1;(ii)
y(x1,x2,…,xk)=u1(x1,x2,…,xk)×u2(x1,x2,…,xk), where u1,u2∈EACN-1;(iii)
y(x1,x2,…,xk)=v(u1(x1,x2,…,xk), u2(x1,x2,…,xk),…,um(x1,x2,…,xk)), where v,u1,u2,…,um∈EACN-1;(iv)
y(x1,x2,…,xk)={xk+1,xk+2,…,xk+l}  =  {f1(x1,x2,…,xk),f2(x1,x2,…,xk),…,fl(x1,x2,…,xk)}, and {xk+1,xk+2,…,xk+l} is the solution of(2)y1x1,x2,…,xk,xk+1,xk+2,…,xk+l=0,y2x1,x2,…,xk,xk+1,xk+2,…,xk+l=0,⋮ylx1,x2,…,xk,xk+1,xk+2,…,xk+l=0,wheref1,f2,…,fl are Cω functions and y1,y2,…,yl∈EACN-1;(v)
y(x1,x2,…,xk)=Df(x1,x2,…,xk)=∂α1+α2+⋯+αnf/∂x1α1∂x2α2⋯∂xkαk, where f∈EACN-1;(vi)
y(x1,x2,…,xk)={Ω,Ω′}∈EACN+1/2, for any y′∈EACN defined on set Λ, where(3)Ω=x1,x1,…,xk∈Λ:y′x1,x1,…,xk>0,Ω′=x1,x1,…,xk∈Λ:y′x1,x1,…,xk≥0.Moreover, for any function(y,Ω) produced at level N and for any subset Ω∗ of Ω produced at level N-1/2, the function (y|Ω∗,Ω∗) can be produced at level N;(vii)
y(x1,x2,…,xk)=y∗, y∗ is a unique analytic continuation of y from Ω∩Ω∗ to all Ω∗, where (y,Ω)∈EACN and Ω∩Ω∗≠∅;(viii)
y(x1,x2,…,xk) is a solution of a set of differential functions of the form(4)Fx1,x2,…,xk:y′,y1′,y2′,…,yl′=0on setΩ  subject to certain boundary requirements, where Ω∈EACN-1/2, y′∈EACN-1, and y′,y1′,y2′,…,yl′ are partial derivatives of y;(ix)
for(x1,x2,…,xk)∈Ω and (x10,x20,…,xk0)∈γ,(5)yx10,x20,…,xk0=limx1,x2,…,xk→x10,x20,…,xk0⁡y′x,wherey′∈EACN-1, Ω∈EACN-1/2, and γ∈EACN-1/2 are subsets of ∂Ω.The EAC is an extension of Shannon’s GPAC. Rubel proved that everyCω-function that could be computed by a GPAC could also be computed by an EAC [4], and, moreover, Euler’s gamma function Γ(x) and Riemann zeta function ζ(s) can also be computed by an EAC [21], while the GPAC cannot solve these problems. Rubel stressed that the EAC was a conceptual computer and whether it could be realized by actual physical, chemical, or biological devices was not known, and most computer scientists also regarded the EAC as a machine that was theoretically impossible to be built. However, Mills and his colleagues designed and built an electronic implementation inspired by the EAC, the micro-Extended Analog Computer (uEAC), and the current version was designed in 2005. Readers who are interested in the hardware of the uEAC are referred to [8, 10, 14] for more details.Suppose that currentI is injected to the conductive sheet at location O. The distances from O to two arbitrary points i, j on the same radius are ri, rj, respectively, and Vij is the voltage between i and j. Without loss of generality, we suppose that j is located outside of i and there are m resistances between i and j, the length of every resistance is Δr (i.e., rj-ri=Δr·m), and we have(6)Vij=InR1+R2+⋯+Rm=In∑k=1mρ·Δrri+2k-1·Δr/2·2π/n.Let Δr→0; we have(7)Vij=Iρ2π∫rirjdrr=Iρ2πln⁡rjri,where ρ is the electrical resistivity of the conductive sheet. Let kij=ρ/2πln⁡rj/ri, then Vij=I·kij, and we note that kij is dependent on ρ, ri, and rj; in other words, once the current input locations and voltage output locations on the conductive material are fixed, kij is a positive constant and can be seen as a coefficient of the input current I and output voltage Vij. The output of uEAC is L(Vij), where L is the LLA basic function [22].The uEAC is based on the resistance property of the conductive sheet, which makes its input-output relation linear; thus a single uEAC unit is very limited when applied to nonlinear problems. In the next section, we present a fully connected uEACs array to expand the computation capabilities of uEAC.


## 3. The Fully Connected uEACs Array

We present a fully connected single-input, single-output uEACs array (see Figure2) in this section, within which each uEAC unit is connected to all the other units by some weights, and x corresponds to the external input variable, u to a state variable, and y to the output variable. In the uEACs array shown as in Figure 2, the output of the array y is not necessarily restricted to uEAC_1; it can be the output of any uEAC unit or a combination of the outputs of several units. Each uEAC unit weights and sums its inputs and updates its state as the following function: (8)uit+1=L∑j=1nωijujt+aixt,where n is the number of uEAC units, ωij, ai are fixed real valued weights, and L is the LLA function. It is important to distinguish this uEACs array model from the Analog Recurrent Neural Network (ARNN). In ARNN, the activation function of neurons is a saturated-linear function [23, 24], while, in the uEACs array, L is a piecewise linear function implemented by LLA basic functions. Another significant feature that distinguishes uEACs array from the ARNN is that uEAC is an actual programmable physical implementation inspired by Rubel’s EAC model, and, in this paper, the computational capability of such a fully connected uEACs array is studied. We can rewrite the mathematical model in vector form as(9)u~=LWu+Ax,where now u and A are vectors of size n and W is a real matrix of size n×n.Figure 2
Structure of the fully connected uEACs array.The state of this dynamic system at each instant is a real vector; that is,u(t)=(u1(t),u2(t),…,un(t))∈Rn. The ith coordinate of the vector represents the value of the ith uEAC units at time t. In particular, in the physical structure of uEAC, the term “real” corresponds to values of resistances, capacitances, and electrical field, which may not be directly measured, but they affect the dynamic behavior dramatically. For instance, everything on the earth obeys the exact value of gravitational acceleration G even though we are not able to measure it. We may replace G with a rational number and observe similar qualitative behavior in finite time simulation; nonetheless, the infinite-time characteristics depend on the true value. Another example is π. When modeling this uEACs array, some real values are involved, and, for finite time interval, one may replace these real values by some rational values, and the same qualitative behavior is observed, while the long-term characteristics depend on the true values.The array is said to be fully connected because there is a weight between every two uEAC units. The status of the weights can be seen either as unknown parameters to be estimated, or as constant after being optimized. This prompts two different views of this uEACs array. When the weights are considered as unknown parameters, the uEACs array is an adaptive topology that approximates some input-output mapping by means of parameter optimization. When the weights are considered constant, the uEACs array performs exact computation. We should note thatwij may equal 0, which means that there is no connection between units i and j. Thus this fully connected array can be seen as a general model of a variety of uEACs arrays, including those in which only a subset of the uEAC units are used. Moreover, all the units in this fully connected structure are in the same layer and compute in parallel. The number of uEAC units in the network is countable. We assume that the structure of the array, including the interconnection relationship of the uEAC units and the values of the interconnection weights, remains constant. What changes in time are the state values, that is, outputs of every uEAC unit, which are used in the next iteration.


## 4. Main Results

Before stating the main results of this paper, we introduce several useful notations. Forx∈R, x=min{s∈Z:s≥x}. Let (x1,x2,…,xn)∞=max1<i<n⁡xi, f∞=supx∈R⁡f(x), and f[k] denotes its kth iteration; that is, (10)f1=fx,f2=ffx,f3=fffx,…Definition 4.
A functionf:R→R is uEAC-computable if letting x be an arbitrary element in the domain of f and given an output precision 2-n, there is a uEACs array that is able to compute a rational approximation of f with precision 2-n.We should note that the exponential function, the trigonometric functions, and their compositions are uEAC-computable as basic analytic functions. We may now present the main result of this paper which states the computation capabilities of the uEACs array.Theorem 5.
For a Turing machineM, there is a uEACs array that can robustly simulate it.Actually, we will prove the following theorem.Theorem 6.
Letψ:N3→N3 be the transfer function of a Turing machine M; there is a uEACs array that is able to simulate M robustly in the following sense: let 0<ε<1/2 be some bounded noise added to the initial configuration of M; there is a uEAC-computable function f:R3→R3 that, for all x-0∈R3 satisfying x-0-x0∞≤ε, we have (11)fx-0-ψx0∞≤ε,where x0∈N3 represents an initial configuration of M.Ifx is a halting configuration of M, we have ψ(x)=x. We will prove this theorem by showing that f:R3→R3 can be obtained by composing some uEAC-computable functions, such as exponential function and trigonometric functions.


## 5. Robust Simulation of Turing Machine with uEAC-Computable Functions

For a Turing machineM with 10 symbols and m states, its tape contents can be represented as (12)⋯Bα-mα-m+1⋯α-1α0α1⋯αnB⋯,where αi are symbols on the tape and B is the blank symbol. Define the encoding functions as(13)y1=α0+α110+⋯+αn10n,y2=α-1+α-210+⋯+α-m10m-1.Let q be the current state of M and then the triple (y1,y2,q)∈N3 is the current configuration of M. We use a periodic function ω to read the symbols written on the tape; by trigonometric interpolation we may take(14)ωt=p0+∑h=14phcos⁡hπ5t+qhsin⁡hπ5t+p5cos⁡πt,where p0,p1,…,p5,q1,q2,…,q4 are coefficients that can be obtained by solving a system of linear equations. From the form of ω we can get that it is uEAC-computable as a composition of trigonometric functions. Note that ω is continuous in R, and, for every given ε, there is some ξε>0 that ∀n∈N, x∈[n-ξε,n+ξε] and we have ωx-nmod⁡10≤ε.Actually, when simulatingM, we are dealing with a series of approximations of (y1,y2,q), that is, (y-1,y-2,q-), in the following sense for given ε:(15)y1,y2,q-y-1,y-2,q-∞≤ε,and thus we need to keep the error under control during the iterations. An error control function can be defined as σ(x)=x-0.2sin⁡(2πx) to keep the error under control when reading symbols and states of the Turing machine, and it is a uniform contraction in a neighborhood of integers.Proposition 7 (see [6]).
Letn∈Z and ε∈[0,1/2); there is some contracting factor λε∈(0,1) that ∀δ∈[-ε,ε], σn+δ-n<λεδ.Another two uEAC-computable error control functionsu and u′ are defined as follows.Lemma 8 (see [6]).
Leta∈{0,1}, for any a-, y∈R satisfying a-a-≤1/4 and y>0; there is a function u:R2→R given by u(x,y)=1/πarctan⁡4yx-1/2+1/2 such that a-ua-,y<1/y.Lemma 9 (see [6]).
Leta∈{0,1,2}, for any a-, y∈R satisfying a-a-≤ε and y≥2; there is a function u′:R2→R given by (16)u′x,y=uσs+1x-12,3y·2uσsx2,3y-1+1such that a-u′a-,y<1/y, where(17)s=0ε≤1/4-log⁡4εlog⁡λεε>1/4.Without loss of generality, we suppose that the symbol being read byM is α0. By y1-y-1≤ε, we have(18)α0-ωσty-1≤ε,where t=log⁡ξε/ε/log⁡λε. Then ω(σ[t](y-1)) can be seen as an approximation of the symbol being currently read with error bounded by ε, and it is uEAC-computable. With the approximation of the current symbol, we can determine the next state by polynomial interpolation. Recall that M has m states and 10 symbols, let y be the symbol being currently read and q the current state, and the next state of M can be represented as(19)q∗=∑i=09∑j=1m∏r=0,r≠i9y-ri-r∏x=1,x≠jmq-xj-xqij,q-∗=∑i=09∑j=1m∏r=0,r≠i9σvy--ri-r∏x=1,x≠jmσvq--xi-xqij,where q-∗ is an approximation of q∗ satisfying q-∗-q∗≤ε and qij is the state that follows symbols i and state j. This map returns the next state of M and is also uEAC-computable. Using the similar construction, the symbol to be written on the tape, l∗, and the direction of the move of the head, d∗, can also be approximated with precision ε, respectively; that is, l-∗-l∗≤ε and d-∗-d∗≤ε.Letd=0 denote a move of the head to the left, let d=1 denote stay, and let d=2 denote a move to the right. In the absence of error, the next value of y1, that is, y1∗, is a function of y1, y2, l∗, and d∗,(20)y1∗=A11-d∗2-d∗2+A2d∗2-d∗+A3d∗1-d∗-2,where A1=ω(y2)+10(l∗+y1-ω(y1)), A2=l∗+y1-ω(y1), and A3=1/10(y1-ω(y1)). Consider the error, let D be an additional approximation of d∗ to be determined later, we define three functions A1′, A2′, and A3′ to approximate the tape contents after the head moves left, stays, and moves right, respectively, and then y1∗ can be approximated as(21)y-1∗=A1′1-D2-D2+A2′D2-D+A3′D1-D-2,where(22)A1′=σs+2ωσty-2+10σs+4l-∗+σs+4y-1-σs+4ωσty-1,A2′=σs+2l-∗+σs+2y-1-σs+2ωσty-1,A3′=110σs+1y-1-σs+1ωσty-1.If we take D=d-∗ directly, the error of the term ((1-D)(2-D))/2 will be amplified when multiplied by A1′. To obtain a sufficiently good approximation of y1∗, we have to guarantee that the error D-d∗ is bounded; this can be achieved with the following definition:(23)D=u′d-∗,12000y-1+12+2.By the definition ofu′, we get that D-d∗≤ϕ, where ϕ=1/(12000(y-1+1/2)+2). Then we can obtain sufficient good y-1∗ such that y-1∗-y1∗<ε. We should note that D, A1′, A2′, and A3′ are defined as a composition of uEAC-computable functions so they are also uEAC-computable. Similarly we can get some y-2∗ satisfying y-2∗-y2∗<ε. Putting together the maps defined above, we can define a uEAC-computable function g:R3→R3 as g(y-1,y-2,q-)=(y-1∗,y-2∗,q-∗), such that(24)ψy1,y2,q-gy-1,y-2,q-∞=y1∗,y2∗,q∗-y-1∗,y-2∗,q-∗∞≤ε.Let0≤δ≤ε and i∈N satisfying σ[i](ε)≤ε-δ. We can define a map f′(x)=σ[i](g(x))(for a 3-dimensional input x=(x1,x2,x3), σ(x)=(σ(x1), σ(x2),σ(x3))) that if x0∈N3 is an initial configuration of M and x-0-x0∞≤ε, we have(25)f′x-0-ψx0∞=σigx-0-ψx0∞≤ε-δ.By the triangle inequality, if x-0-x0∞≤ε, then, for a uEAC-computable function f satisfying f-f′∞≤δ, we have(26)fx-0-ψx0∞≤fx-0-f′x-0∞+f′x-0-ψx0∞≤δ+ε-δ=ε.From the discussion above we get that one can construct a robust Turing machine simulation with uEAC-computable functions.


## 6. Conclusion

uEAC is a novel electronic implementation inspired by Rubel’s EAC model. Based on the mathematical model of uEAC, we propose a fully connected uEACs array and investigate its computational capabilities. By proving that any Turing machine can be simulated with uEAC-computable functions, we conclude that the proposed uEACs array is at least as powerful as Turing machine.This work can be extended in several directions. The structure of the uEACs array, including the interconnection relationship of the uEAC units and the values of the interconnection weights, is not necessary to remain constant during the iteration. Ainslie et al. use genetic algorithm (GA) to evolve a uEAC to solve XOR problem [25], but their research is restricted to a single uEAC unit and it is hard to say that GA is the most suitable evolutionary algorithm for uEAC. The proposed uEACs array shows great advantages, while its optimization is much more difficult since we have to optimize the topology of the array and the particular structure of the single uEAC unit simultaneously. From the mathematical point of view, all the heuristic algorithms, such as particle swarm optimizer (PSO), ant colony algorithm, and simulated annealing algorithm (SA), can be used to optimize the uEACs array, but we must consider the computation complexity and efficiency of these algorithms. Zhu et al. proposed a comprehensive uEACs array optimization strategy based on particle swarm optimizer (PSO) [22], and the simulation results are promising.Moreover, in the definition of the fully connected uEACs array, we useuEAC_1,uEAC_2,…,uEAC_n to denote the uEAC units in the array, while it is still an open question: how many uEAC units are needed in the array to guarantee its computational capabilities? In other words, we employ an indeterminate item “n” to represent the number of uEAC units, but it is far from satisfied. A comprehensive analysis to determine the minimum “n” that guarantees the robust simulation of Turing machine is of great significance, and this is an emphasis of the future research. The conclusion of this paper can be rewritten as “a robust simulation of the transfer function of a Turing machine can be constructed with uEAC-computable functions.” Actually, when studying the computational capability of the uEACs array, two questions are considered. (1) Does a Turing machine can calculate any uEAC-computable function? (2) Is the function generated by a Turing machine also uEAC-computable? If the answers of these two questions are both yes, we can get a more concrete conclusion that the uEACs array and Turing machine are equivalent! This paper focuses on the second question while the first one can be seen as another valuable future research direction.



---

*Source: 236806-2015-11-19.xml*