T Humbert
email: thomas.humbert@cea.fr

C Josserand

C Touzé

O Cadot

A phenomenological model for predicting the effect of damping on wave turbulence spectra in vibrating plates

Thin plates vibrating at large amplitudes may exhibit a strongly nonlinear regime that has to be studied within the framework of wave turbulence. Experimental studies have revealed the importance of the damping on the spectra of wave turbulence, which precludes for a direct comparison with the theoretical results, that assumes a Hamiltonian dynamics. A phenomenological model is here introduced so as to predict the effect of the damping on the turbulence spectra. Self-similar solutions are found and the cut-off frequency is expressed as function of the damping rate and the injected power.

The large amplitude vibrations of thin plates are well described by the Wave Turbulence (WT) theory. The out-of-equilibrium solutions are found from the kinetic equations [START_REF] Nazarenko | Wave Turbulence[END_REF], which admit two different solutions [START_REF] Düring | Weak turbulence for a vibrating plate: can one hear a Kolmogorov spectrum?[END_REF]:

• The so-called Rayleigh-Jeans solution where energy is equiparted along all possible lengthscales.

In this case the the density of energy E RJ (ω) is a constant with respect to the frequency.

• The Kolmogorov-Zacharov (KZ) solution with an energy flux cascading from the largest to the smallest wavelength. In this case the density of energy reads :

E KZ (ω) = Aε 1 3 log 1 3 ω ω , (1)
with A a constant, ε the (conserved) energy flux and ω a cut-off frequency.

Numerous experiments have underlined the effect of damping [START_REF] Humbert | Wave turbulence in vibrating plates: the effect of damping[END_REF][START_REF] Cadot | Wave turbulence in vibrating plates[END_REF]. In order to study its effect on the WT spectrum, a phenomelogical model is introduced, which describes the temporal and frequency dependence of the energy density E(ω). It reads:

∂E ∂t = ∂ ∂ω (ωE 2 ∂E ∂ω ) -γE, (2)
For γ = 0 (conservative case), the phenomenological model retrieves stationary (RJ and KZ spectra) as well as non-stationary solutions of the kinetic equation [START_REF] Humbert | Phenomenological model for predicting stationary and nonstationary spectra of wave turbulence in vibrating plates[END_REF].

Fig. 1(a) shows the stationary spectra of turbulence obtained from Eq. ( 2) for a damping law of the form γ = ξω 0.6 , with relative values of ξ (with respect to the smallest one) ranging from 1 to 5. Interestingly the solutions are self-similar and collapse on a single curve when rescaled by the cut-off frequency ω c , as shown in Fig. 1(b). This solution is different from the KZ spectrum for the conservative case -shown as a green dashed line in Fig. 1 Let us consider now a general damping rate expressed as γ = ξω λ , where the exponent λ controls the frequency dependence of the losses and ξ its amplitude. The self-similar solution for the spectrum can be expressed as:

E(ω) = ε 1/3 I f η ω ε y I ξ z , (3)
with z = -1 1+λ , y = 2 3(1+λ) , and f η solution of the differential equation:

∂ η (ηf 2 η ∂ η f η ) -f η η λ = 0, (4)
The solution for this differential equation is shown in Fig. 1

Figure 1 :

 1 Fig.1(a) shows the stationary spectra of turbulence obtained from Eq. (2) for a damping law of the form γ = ξω 0.6 , with relative values of ξ (with respect to the smallest one) ranging from 1 to 5. Interestingly the solutions are self-similar and collapse on a single curve when rescaled by the cut-off frequency ω c , as shown in Fig.1(b). This solution is different from the KZ spectrum for the conservative case -shown as a green dashed line in Fig.1(b)-showing undoubtedly the effect of the damping.

  (b) as a red dashed line and matches exactly with the direct simulation. Finally one is able to predict the cut-off frequency as function of the damping, and the injected flux as :ω c = ε constitutes the main result of the present study.


Damien Woods
email: d.woods@cs.ucc.ie

J Paul Gibson

Lower bounds on the computational power of an optical model of computation

This work is concerned with the computational complexity of a model of computation that is inspired by optical computers. We present lower bounds on the computational power of the model. Parallel time on the model is shown to be at least as powerful as sequential space. This gives one of the two inclusions that are needed to show that the model verifies the parallel computation thesis. As a corollary we find that when the model is restricted to simultaneously use polylogarithmic time and polynomial space, its power is lower bounded by the class NC. By combining these results with the known upper bounds on the model, we find that the model verifies the parallel computation thesis and, when suitably restricted, characterises NC.

Introduction

Over the years, optical computers were designed and built to emulate conventional microprocessors (digital optical computing), and for image processing over continuous wavefronts (analog optical computing). Here we are interested in the latter class: optical computers that store data as images. Numerous physical implementations exist and example applications include fast pattern recognition and matrix-vector algebra [START_REF] Goodman | Introduction to Fourier optics[END_REF][START_REF] Vanderlugt | Optical Signal Processing[END_REF]. There have been much resources devoted to designs, implementations and algorithms for such optical information processing architectures (for example see [1, 3, 5, 7, 10-13, 20, 22, 28] and their references). However the computational complexity theory of optical computers (that is, finding lower and upper bounds on computational power in terms of known complexity classes) has received relatively little attention when compared with other nature-insired computing paradigms. Some authors have even complained about the lack of suitable models [START_REF] Feitelson | Optical Computing: A survey for computer scientists[END_REF][START_REF] Louri | Complexity analysis of optical-computing paradigms[END_REF].

The computational model that we study was originally put forward by Naughton and is called the continuous space machine (CSM) [14-16, 23, 27]. The CSM is inspired by classical Fourier optical computing architectures and uses complexvalued images, arranged in a grid structure, for data storage. The program also resides in images. The CSM has the ability to perform Fourier transformation, complex conjugation, multiplication, addition, thresholding and resizing of images. It has simple control flow operations and is deterministic. We analyse the model in terms of seven complexity measures inspired by real-world resources.

A rather general variant of the model was previously shown [START_REF] Woods | An optical model of computation[END_REF] to decide the membership problem for all recursively enumerable languages, and as such is unreasonable in terms of implementation. Also, the growth in resource usage was shown for each CSM operation, which in some cases was unreasonably large [START_REF] Woods | Complexity of continuous space machine operations[END_REF]. These results motivated the definition of the C 2 -CSM, a restricted CSM that uses discrete-valued images. We have given upper [START_REF] Woods | Upper bounds on the computational power of an optical model of computation[END_REF] and lower [START_REF] Woods | Lower bounds on the computational power of an optical model of computation[END_REF] bounds on the computational power of the C 2 -CSM by showing that it verifies the parallel computation thesis. This thesis [START_REF] Chandra | Alternation. In 17th annual symposium on Foundations of Computer Science[END_REF][START_REF] Goldschlager | Synchronous parallel computation[END_REF][START_REF] Greenlaw | Limits to parallel computation: P-completeness theory[END_REF][START_REF] Karp | Parallel algorithms for shared memory machines[END_REF][START_REF] Parberry | Parallel complexity theory[END_REF][START_REF] Van Emde | Machine models and simulations[END_REF] states that parallel time corresponds, within a polynomial, to sequential space for reasonable parallel models. Furthermore we have characterised the class NC in terms of the C 2 -CSM. These results are collected together in [START_REF] Woods | Computational complexity of an optical model of computation[END_REF].

Here we present one of the two inclusions that are necessary in order to verify the parallel computation thesis; we show that the languages accepted by nondeterministic Turing machines in S(n) space are accepted by

C 2 -CSMs computing in time O(S(n) + log n) 4 . NSPACE(S(n)) ⊆ C 2 -CSM-TIME(O(S(n) + log n) 4 )
For example polynomial time C 2 -CSMs accept the PSPACE languages. Also we show that C 2 -CSMs that simultaneously use polynomial space and polylogarithmic time accept the class NC.

NC ⊆ C 2 -CSM-SPACE, TIME(n O(1) , log O(1) n)
These inclusions are established via C 2 -CSM simulation of index-vector machines.

The CSM

We begin by describing the model in its most general sense, this brief overview is not intended to be complete and more details are to be found in [START_REF] Woods | Computational complexity of an optical model of computation[END_REF].

CSM

A complex-valued image (or simply, image) is a function f : [0, 1) × [0, 1) → C, where [0, 1) is the half-open real unit interval. We let I denote the set of complexvalued images. Let N + = {1, 2, 3, . . .}, N = N + ∪ {0}, and for a given CSM M let N ⊂ I be a countable set of images that encode M 's addresses. Additionally, for a given M there is an address encoding function E : N → N such that E is Turing machine decidable, under some reasonable representation of images as words. An address is an element of N × N. Addresses whose contents are not specified by P in a CSM definition are assumed to contain the constant image f (x, y) = 0. We interpret this definition to mean that M is (initially) defined on a grid of images bounded by the constants Ξ and Y, in the horizontal and vertical directions respectively. The grid of images may grow in size as the computation progresses.

Definition 1 (CSM).

In our grid notation the first and second elements of an address tuple refer to the horizontal and vertical axes of the grid respectively, and image (0, 0) is located at the lower left-hand corner of the grid. The images have the same orientation as the grid. For example the value f (0, 0) is located at the lower left-hand corner of the image f .

In Definition 1 the tuple P specifies the CSM program using programming symbol images ζ j that are from the (low-level) CSM programing language [START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | An optical model of computation[END_REF]. We refrain from giving a description of this programming language and instead describe a less cumbersome high-level language [START_REF] Woods | Computational complexity of an optical model of computation[END_REF]. Figure 1 gives the basic instructions of this high-level language. The copy instruction is illustrated in Figure 3. There are also if/else and while control flow instructions with conditions of the form (f ψ == f φ ) where f ψ and f φ are binary symbol images (see Figures 2(a Address sta is the start location for the program so the programmer should write the first program instruction at sta. Addresses a and b define special images that are frequently used by some program instructions. The function E is specified by the programmer and is used to map addresses to image pairs. This enables the programmer to choose her own address encoding scheme. We typically don't want E to hide complicated behaviour thus the computational power of this function should be somewhat restricted. For example, we put such a restriction on E in Definition 7. Configurations are defined in a straightforward way as a tuple c, e where c is an address called the control and e represents the grid contents.

Complexity measures

Next we define some CSM complexity measures. All resource bounding functions map from N into N and are assumed to have the usual properties [START_REF] Balcázar | Structural complexity, vols I and II[END_REF]. Logarithms are to the base 2.

Definition 2. The time complexity of a CSM M is the number of configurations in the computation sequence of M , beginning with the initial configuration and ending with the first final configuration. Definition 3. The grid complexity of a CSM M is the minimum number of images, arranged in a rectangular grid, for M to compute correctly on all inputs.

For example suppose M accepts language L, then the grid complexity of M is the minimum number of images accessible by M and arranged in a rectangular grid, such that M accepts exactly L.

h(i1;i2)

: replace image at i2 with horizontal 1D Fourier transform of i1. v(i1;i2)

: replace image at i2 with vertical 1D Fourier transform of image at i1. * (i1;i2)

: replace image at i2 with the complex conjugate of image at i1.

• • • (i1,i2;i3)
: pointwise multiply the two images at i1 and i2. Store result at i3. +(i1,i2;i3) : pointwise addition of the two images at i1 and i2. Store result at i3. ρ(i1,z l ,zu;i2) : filter the image at i1 by amplitude using z l and zu as lower and upper amplitude threshold images, respectively. Place result at i2. [ξ 1 , ξ 2 , η 1 , η 2 ] ← [ξ1, ξ2, η1, η2] : copy the rectangle of images whose bottom left-hand address is (ξ1, η1) and whose top right-hand address is (ξ2, η2) to the rectangle of images whose bottom left-hand address is (ξ 1 , η 1 ) and whose top right-hand address is (ξ 2 , η 2 ). See illustration in Figure 3. Let S : I × (N × N) → I, where S(f (x, y), (Φ, Ψ )) is a raster image, with ΦΨ constant-valued pixels arranged in Φ columns and Ψ rows, that approximates f (x, y). If we choose a reasonable and realistic S then the details of S are not important.

Definition 4. The spatialRes complexity of a CSM M is the minimum ΦΨ such that if each image f (x, y) in the computation of M is replaced with S(f (x, y), (Φ, Ψ )) then M computes correctly on all inputs. Definition 5. The dyRange complexity of a CSM M is the ceiling of the maximum of all the amplitude values stored in all of M 's images during M 's computation.

We also use complexity measures called amplRes, phaseRes and freq [START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | An optical model of computation[END_REF]. Roughly speaking, the amplRes of a CSM M is the number of discrete, evenly spaced, amplitude values per unit amplitude of the complex numbers in the range of M 's images. The phaseRes of M is the total number (per 2π) of discrete evenly spaced phase values in the range of M 's images. freq is a measure of the optical frequency of M 's images.

Often we wish to make analogies between space on some well-known model and CSM 'space-like' resources. Thus we define the following convenient term. Definition 6. The space complexity of a CSM M is the product of all of M 's complexity measures except time.

More details on the complexity measures are be found in [START_REF] Woods | An optical model of computation[END_REF].

C 2 -CSM

In previous work [START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | Complexity of continuous space machine operations[END_REF] we investigated the growth of complexity resources over time, with respect to CSM operations. As expected, under certain operations some measures do not grow at all. Others grow at rates comparable to massively parallel models. By allowing operations like the Fourier transform we are mixing the continuous and discrete worlds, hence some measures grow to infinity in one timestep. This gave strong motivation for the C 2 -CSM, a restriction of the CSM.

Definition 7 (C 2 -CSM). A C 2 -CSM is a CSM whose computation time is de- fined for t ∈ {1, 2, . .

. , T (n)} and has the following restrictions:

-For all time t both amplRes and phaseRes have constant value of 2.

-For all time t each of grid, spatialRes and dyRange is O(2 t ) and space is redefined to be the product of all complexity measures except time and freq. -Operations h and v compute the discrete Fourier transform (DFT) in the horizontal and vertical directions respectively. -Given some reasonable binary word representation of the set of addresses N , the address encoding function E : N → N is decidable by a logspace Turing machine.

3 Index-vector machines and representations

Here we introduce vector machines, and the variant that we simulate called index-vector machines. We then describe our image representation of vectors. The vector machine model was originally described by Pratt, Rabin and Stockmeyer [START_REF] Pratt | A characterisation of the power of vector machines[END_REF], here we mostly use the conventions of Pratt and Stockmeyer [START_REF] Pratt | A characterisation of the power of vector machines[END_REF]. A vector V is a binary sequence that is infinite to the left only and is ultimately constant (after a finite number of bits every bit to the left is either always 0 or always 1). An ultimately 0 sequence represents a positive number and an ultimately 1 sequence represents a negative number [START_REF] Pratt | A characterisation of the power of vector machines[END_REF][START_REF] Balcázar | Structural complexity, vols I and II[END_REF]. The non-constant part (denoted v) represents a positive binary integer in the usual way, with the rightmost vector bit representing the least significant integer bit. The negative integer -n is represented by the bitwise complement of the vector representing n. The length of V is denoted |V |, and is the length of the non-constant part of V . A vector machine (program) is a list of instructions where each is of the form given in the following definition.

Definition 8 (Vector machine instructions and their meanings [START_REF] Balcázar | Structural complexity, vols I and II[END_REF]).

Vector instruction

Meaning Vi := x Load the positive constant binary number x into vector Vi. V k := ¬Vi Bitwise parallel negation of vector Vi.

V k := Vi ∧ Vj
Bitwise parallel 'and' of two vectors.

V k := Vi ↑ Vj
If Vj is ultimately 0 (resp. 1) then shift Vi to the left (resp. right) by the distance given by the binary number vj and store the result in

V k . If Vj = 0 then Vi is copied to V k . V k := Vi ↓ Vj
If Vj is ultimately 0 (resp. 1) then shift Vi to the right (resp. left) by the distance given by the binary number vj and store the result in

V k . If Vj = 0 then Vi is copied to V k . goto m if Vi = 0
If Vi = 0 then branch to the instruction labelled m. goto m if Vi = 0

If Vi = 0 then branch to the instruction labelled m.

Instructions are labelled to facilitate the goto instruction. Configurations, (accepting) computations and computation time are all defined in the obvious way. Computation space is the maximum over all configurations, of the sum of the lengths of the vectors in each configuration. A language accepting vector machine on input w has an input vector of the form ...000w where w ∈ 1{0, 1} * . In this work we consider only deterministic vector machines. See [START_REF] Balcázar | Structural complexity, vols I and II[END_REF] for details. Definition 9 (Index-vector machines [START_REF] Pratt | A characterisation of the power of vector machines[END_REF]). A vector machine is of class V I (equivalently, an index-vector machine) if its registers are partitioned into two disjoint sets, one set called index registers and the other called vector registers, such that (i) each Boolean operation in the program involves either only index registers or only vector registers; and (ii) each shift instruction is of the form

V 1 := V 2 ↑ I, V 1 := V 2 ↓ I, I := J ↑ 1, I := J ↓ 1
where V 1 and V 2 are vector registers, and I and J are index registers. For language recognition the input register is a vector register.

It is straightforward to prove the following lemma by induction on t.

Lemma 1 ([19]

). Given index-vector machine M ∈ V I with n as the maximum input length, there is a constant c such that vector length in index (respectively vector) registers is bounded above by c+t (respectively 2 c+t +n) after t timesteps.

Pratt and Stockmeyer's [START_REF] Pratt | A characterisation of the power of vector machines[END_REF] main result is a characterisation of the power of index-vector machines. The characterisation is described by two inclusions, proved for time bounded index-vector machines and space bounded Turing machines: In other words, index-vector machines verify the parallel computation thesis and are a member of the second machine class [START_REF] Van Emde | Machine models and simulations[END_REF]. Modulo a polynomial, deterministic and nondeterministic vector machines have equal power [START_REF] Pratt | A characterisation of the power of vector machines[END_REF].

NSPACE(S(n)) ⊆ V I -TIME(O(S(n) + log n) 2 ) (1) V I -TIME(T (n)) ⊆ DSPACE(O(T (n)(T (n) + log n))) (2)

Image representation of vectors

Let v i ∈ {0, 1} * denote the non-'ultimately constant' part of vector V i . If the ultimately constant part of V i is 0 ω (respectively 1 ω ) then let sign(v i ) = 0 (respectively let sign(v i ) = 1). In this work we use binary symbol images, number images and binary list images. These represent binary symbols, numbers from {0, ± 1 2 , ±1, ± 3 2 , . . .}, and binary words in a straight-forward way that is illustrated in Figure 2. Further details are to be found in [START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | An optical model of computation[END_REF].

The vector V i is represented by three images: v i , |v i | and sign(v i ). The image v i is the binary list image representation of v i . Image |v i | is the natural number image represention of |v i | (the length of v i ). Accessing these images respectively incurs spatialRes and dyRange costs that are linear in |v i |. Image sign(v i ) is f 0 (the binary symbol image representing 0) if sign(v i ) = 0 and f 1 if sign(v i ) = 1. We use the same representation scheme for vector program constants. The simulation uses natural number images as addresses, which are clearly reasonable in the sense of the C 2 -CSM definition. Hence addressing incurs a (linear) dyRange cost.

Another issue to consider is the layout of the grid of images; where to place input, program constants (f 0 , f 1 , f -1 , f 1 2 , f 2 ), local variables, etc. There are only a constant number of such images hence there a number of layouts that work, a specific grid layout is given in [START_REF] Woods | Computational complexity of an optical model of computation[END_REF]. Rows 0 and 1 are used to store temporary images. The only images explicitly referred to by numerical addresses are in these two rows (the constant number of other addresses used in the simulation have identifier names from the outset). check this.

C 2 -CSM simulation of index-vector machines

In this section we prove that C 2 -CSMs are at least as powerful as index-vector machines (up to a polynomial in time). More precisely

V I -TIME(T (n)) ⊆ C 2 -CSM-TIME(O(T 2 (n))). (3)
To prove this we simulate each index-vector machine instruction in O(log |V max |) time where |V max | ∈ N is the maximum length of (the non-ultimately constant part of) any of the vectors mentioned in the instruction. Additionally we simulate the index-vector shifts in linear time. From Lemma 1 this time bound ensures that our overall simulation executes in quadratic time, which is sufficient for the inclusion given by Equation ( 3). The space bound on the simulation is

O(|V max | 3 ).
We begin by giving a straightforward simulation of vector assignment.

Theorem 1 (V i := x). The vector machine assignment instruction Proof. The images representing x are simply copied to those representing

V i := x is simulated by a C 2 -CSM in O(1) time, O (
V i : assignment(x, |x|, sign(x); v i , |v i |, sign(v i )) v i ← x |v i | ← |x| sign(v i ) ← sign(x) end // assignment
We require O(max(|x|, |v i |)) spatialRes to represent x and v i as binary list images. dyRange of O(|x|) is needed to represent |x| as a natural number image. No address goes beyond the initial grid limits hence we use constant grid.

A C 2 -CSM can quickly generate a list image g, where each list element is identical. We state the following lemma for the specific case that each list element is a binary symbol image f ψ . By simply changing the value of one input, the algorithm generalises to arbitrary repeated lists (with a suitable change in resource use, dependent only on the complexity of the new input image element).

Lemma 2 (generate list(f ψ , l; g)). A list image g that contains l list elements, each of which is a copy of input binary image f ψ , is generated in O(log l) time, O(l) grid, spatialRes and dyRange.

Proof (Sketch). The algorithm horizontally juxtaposes two copies of f ψ and rescales them to a single image. This juxtaposing and rescaling is repeated on the new image; the process is iterated a total of log l times to give a list of length 2 log l , giving the stated time bound. In constant time, the list image is then stretched to its full length across 2 log l images, l juxtaposed images are then selected and rescaled to a single output image g. O(l) spatialRes is necessary to store the list in a single image. O(l) grid is used to stretch the list out to its full length. Recall that we are using natural number images for addresses, hence O(l) dyRange is used to stretch the list across 2 log l images. The proof of the following straightforward lemma gives a program that decides which of two vectors is the longer in constant time. It also shows that we can decide the max or min of two integer images in constant time. . If the result is the zero image f 0 then V i is the longer vector and its representation is copied to the three output addresses, else the representation of V j is output. In a similar way we decide the min length of two vector images, the function header for min(•) has the format:

if ( sign(vi) == f1 ) then sign(v k ) ← f0 else sign(v k ) ← f1 end if end // ¬ Program 4.1: Simulation of V k := ¬V i . Theorem 2 (V k := ¬V i ). The vector machine negation instruction V k := ¬V i is simulated by a C 2 -CSM in O(log |v i |) time, O(|v i |)
min(v i , |v i |, sign(v i ), v j , |v j |, sign(v j ); shortest, |shortest|, sign(shortest)) Theorem 3 (V k := V i ∧ V j ). The vector machine instruction V k := V i ∧ V j is simulated by a C 2 -CSM in O(log max(|v i |, |v j |)) time, O(max(|v i |, |v j |, |v k |))
spatialRes, and O(max(|v i |, |v j |)) grid and dyRange.

Proof. Program 4.2 simulates ∧. It uses multiplication of vector images to simulate V i ∧ V j in parallel. However if |v i | = |v j |, we first pad the shorter vector image with zeros so that both have equal length. To find the longer and shorter of the two vectors we make use of the max(•) and min(•) routines given above.

:= V i ∧ V j .
The program requires O(log max(|v i |, |v j |)) time for the generate list(•) call (the worst case is when exactly one of the vectors is of length 0). The remainder of the program runs in O(1) time, including determining which vector is longer, padding of the shorter vector and parallel multiplication of vectors. The remaining resource usages on vector images in the theorem statement are for accessing and storing to a single image, and stretching to full length.

Next we give algorithms to simulate vector left shift and right shift. The main idea is to copy large numbers of images to simulate shifting. Proof (Sketch). The algorithm assumes that n is given as a natural number image. We simulate the shift by stretching v i out to its full length, placing n zero images to the right of the stretched v i , and then selecting all of v i along with the n zeros and rescaling back to one image. After the shift (in accordance with the definition of vector shift), 0s are to be placed in the rightmost positions.

An algorithm for right shift(•) would work similarly. However this time we select the leftmost |v i |n images of the stretched v i . If n |v i | the output is the representation of the zero vector. to give a constant time algorithm that makes use of the FT (to 'sum' the entire list in constant time). Not using the FT enables us to state Corollary 6. Proof (Sketch). The binary list image v i is padded with zeros so that is of length 2 log |vi| . The algorithm splits v i into a left half and a right half, adds both halves (in a one step parallel pointwise fashion), and repeats until the list is of length 1. A counter image keeps track of list length. The resulting image is thresholded below by f 0 and above by f 1 . If the result is the zero image then v i represents a list of zeros, otherwise v i represents a list with at least one 1.

Theorem 4 (V k := V i ↑ V j ). The vector machine instruction V k := V i ↑ V j is simulated by a C 2 -CSM in O(|v j |) time, O(|v i |+2 |vj |
Theorem 5 (goto m if V i = 0). The vector machine instruction goto m if

V i = 0 (or goto m if V i = 0) is simulated by a C 2 -CSM in O(log |v i |) time, O(|v i |) grid,
spatialRes, and dyRange.

Proof. Due to the vector machine number representation, there are exactly two representations for 0; the constant sequences . . . 000 and . . . 111. Using our C 2 -CSM representation of vectors, if |v i | = 0 then the vector V i is constant, and hence represents 0. We can test |v i | = 0 in constant time with an if statement.

However, it may be the case that |v i | = n > 0 and yet V i represents 0. In this case v i represents a list of 0s (respectively 1s) and sign(v i ) represents 0 (respectively 1). A sequential search through v i will require exponential time (worst case) and as such is too slow. Instead we use the log time technique given by the previous lemma. In the case that V i is ultimately 1 we make use of the ¬(•) program defined in Theorem 2. For the goto part of the instruction we merely note that gotos are simulated by ifs and whiles. Clearly the related instruction 'goto m if V i = 0' is simulated with the same resource usage.

Given a vector machine M there is a C 2 -CSM M that simulates M . In particular, if vector machine M decides a language L then we can easily modify our simulation of vector machines so that M decides L. Theorem 6. Let M be an index-vector machine that decides L ∈ {0, 1} * in time

T (n) for input length n. Then L is decided by a C 2 -CSM M in O(T 2 (n)) time, O(2 T (n)
) grid, spatialRes and dyRange.

Proof. By Lemma 1 M 's index-vectors have length O(T (n)), while unrestricted vectors have length O(2 T (n) ). From the above simulation theorems, any nonshifting instruction is simulated in time that is log of the length of the vectors. The remaining operations, right and left shift, are simulated in time that is linear in the length of their index-vector input. From these bounds it is straightforward to work out that M decides L in O(T 2 (n)) time and that each of grid, spatialRes and dyRange is O(2 T (n) ).

From the previous theorem M uses O(2 3T (n) ) space to decide L, hence our simulation uses space that is cubic in the space of M . Proof. The index-vector machine simulation used only constant grid and spa-tialRes in the vertical direction. Moreover we can rotate the grid layout and all images by 90 • , to obtain a simulation where grid and spatialRes are constant in the horizontal direction only.

Corollary 6. The C 2 -CSM without the DFT operations h and v verifies the parallel computation thesis.

Proof. Our C 2 -CSM simulation of index-vector machines did not use h nor v.

The thesis relates parallel time to sequential space, however in our simulations we explicitly gave all resource bounds. As a final result we show that the class of C 2 -CSMs that simultaneously use polynomial space and polylogarithmic time decide at least the languages in NC. Let C 2 -CSM-SPACE, TIME(S(n), T (n)) be the class of languages decided by C 2 -CSMs that use space S(n) and time T (n). It is known [START_REF] Karp | Parallel algorithms for shared memory machines[END_REF] that V I -SPACE, TIME(n O (1) , log O(1) n) = NC. From the resource overheads in our simulations:

V I -SPACE, TIME(O(2 T (n) ), T (n)) ⊆ C 2 -CSM-SPACE, TIME(2 O(T (n)) , T O(1) (n))
For the case of T (n) = log O(1) n we have our final result. Previously we have shown [START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | Upper bounds on the computational power of an optical model of computation[END_REF] that the converse inclusion also holds.

  A CSM is a quintuple M = (E, L, I, P, O), where E : N → N is the address encoding function, L = ((s ξ , s η ) , (a ξ , a η ) , (b ξ , b η )) are the addresses: sta, a and b, where a = b, I and O are finite sets of input and output addresses, respectively, P = {(ζ 1 , p 1 ξ , p 1η ), . . . , (ζ r , p r ξ , p rη )} are the r programming symbols ζ j and their addresses where ζ j ∈ ({h, v, * , •, +, ρ, st, ld, br, hlt} ∪ N ) ⊂ I. Each address is an element from {0, . . . , Ξ -1}×{0, . . . , Y-1} where Ξ, Y ∈ N + .

  ) and 2(b)).

Fig. 1 .Fig. 2 .

 12 Fig.1. CSM high-level programming language instructions. In these instructions i, z l , zu ∈ N × N are image addresses and ξ, η ∈ N. The control flow instructions are described in the main text.

Fig. 3 .

 3 Fig.3. Illustration of the instruction i ← [ξ, ξ + 3, η, η] that copies four images to a single image that is denoted i.

Fig. 4 .

 4 Fig. 4. Representing data by images. To represent the value ψ, the black point has value ψ. The white area denotes value zero. (a) Binary symbol image f ψ where ψ ∈ {0, 1}, or number image where ψ ∈ {0, ± 1 2 , ±1, ± 3 2 , . . .}, (b) binary list image where ψ ∈ {0, 1}. (c) Illustration of the instruction i ← [ξ, ξ + 3, η, η] that copies four images to a single image that is denoted i.

  1) grid, O(|x|) dyRange and O(max(|x|, |v i |)) spatialRes.

  grid and dyRange, and O(max(|v k |, |v i |)) spatialRes. Proof. Program 4.1 simulates V k := ¬V i . The program generates a list of -1s of length |v i |. This list image is then multiplied by v i ; changing each 1 in v i to -1 and leaving each 0 unchanged. Then we add 1 to each element in the resulting list. A simple if statement negates sign(v i ). Each call to the function generate list(•) requires O(log |v i |) time, otherwise time is constant. The remaining resource usages are for accessing vectors and rescaling them to their full length.

Lemma 3 (

 3 max(•) and min(•)). The max (or min) length of the vectors V i and V j is decided in O(1) time, O(1) grid, O(max(|v i |, |v j |)) spatialRes, O(max(|v i |, |v j |)) dyRange. Proof (Sketch). The function header for max(•) is formatted as follows: max(v i , |v i |, sign(v i ), v j , |v j |, sign(v j ); longest, |longest|, sign(longest)) The encoding of -|v i | is created by the instruction • • • (|v i |,f -1 ;-|v i |), then the max(•) algorithm thresholds the value |v j | -|v i | to the range [0, 1]

Lemma 4 (

 4 left shift(n, v i , |v i |, sign(v i ); v k , |v k |, sign(v k ))). A left shift of distance n 0 on a vector V i , to create vector V k , is simulated in O(1)time, O(|v i + n|) grid and dyRange, and O(max(|v i + n|, |v k |)) spatialRes.

  ) grid and dyRange, andO(max(|v k |, |v i | + 2 |vj | )) spatialRes.

Lemma 5 .

 5 A C 2 -CSM that does not use Fourier transformation decides whether or not a list (equivalently vector) image v i represents the word 0 |vi| in O(log |v i |) time, O(|v i |) grid, spatialRes and dyRange.

Corollary 1 .

 1 V I -TIME(T (n)) ⊆ C 2 -CSM-TIME(O(T 2 (n)))Let S(n) = Ω(log n). From the inclusion in Equation (1) we get:Corollary 2. NSPACE(S(n)) ⊆ C 2 -CSM-TIME(O(S 4 (n)))Combining this result with the upper bound on time bounded C 2 -CSM power[START_REF] Woods | Computational complexity of an optical model of computation[END_REF][START_REF] Woods | Upper bounds on the computational power of an optical model of computation[END_REF]:Corollary 3. NSPACE(S(n)) ⊆ C 2 -CSM-TIME(O(S 4 (n))) ⊆ DSPACE(O(S 8 (n)))To summarise, the C 2 -CSM satisfies the parallel computation thesis:Corollary 4. NSPACE(S O(1) (n)) = C 2 -CSM-TIME(S O(1) (n))This links space bounded sequential computation and time bounded C 2 -CSM computation. For example C 2 -CSM-TIME(n O(1) ) = PSPACE. We strengthen this result by restricting the C 2 -CSM. Let a 1D-C 2 -CSM be a C 2 -CSM with constant grid and spatialRes, in one of the vertical or the horizontal directions.Corollary 5. The 1D-C 2 -CSM verifies the parallel computation thesis.

Corollary 7 .

 7 NC ⊆ C 2 -CSM-SPACE, TIME(n O(1) , log O(1) n)

  ¬(vi, |vi|, sign(vi); v k , |v k |, sign(v k ))

	generate list(f-1, |vi|; list neg ones)	// generate list of -1s
	• • • (vi,list neg ones;-vi)	// change each 1 in vi to -1
	generate list(f1, |vi|; list ones)	// generate list of 1s
	+(-vi,list ones;v k )	// change -1s to 0s, 0s to 1s, & place in v k

  ∧ (vi, |vi|, sign(vi), vj, |vj |, sign(vj ); v k , |v k |, sign(v k ) ) max(vi, |vi|, sign(vi), vj , |vj |, sign(vj ); longest, |longest|, sign(longest)) min(vi, |vi|, sign(vi), vj, |vj |, sign(vj ); shortest, |shortest|, sign(shortest))

	if ( sign(longest) == f1 ) then
	• • • (f-1,|shortest|;-|shortest|)
	+(longest,-|shortest|;difference)
	generate list(f1, difference; pad)
	[1,|shortest|,1,1] ← shortest
	+(|shortest|,f1;|shortest|+1)
	[|shortest|+1,|longest|,1,1] ← pad
	padded shortest ← [1,|longest|,1,1]
	else
	[1,|longest|,1,1] ← f0
	[1,|shortest|,1,1] ← shortest
	padded shortest ← [1,|longest|,1,1]
	end if
	• • • (longest,padded shortest;v k )	// a single multiplication simulates vi ∧ vj
	• • • (sign(longest),sign(shortest);sign(v k ))
	|v k | ← |longest|
	end // ∧
	Program 4.2: Simulation of V k

Acknowledgements

We thank Tom Naughton for interesting discussions. During this work the first author was funded by the Irish Research Council for Science, Engineering and Technology.

Proof. Program 4.3 simulates the shift by stretching V i out to its full length; then selecting either part of V i , or V i and some extra zero images; and finally rescaling back to one image. The simulator's addresses are represented by natural number images whereas vectors are represented by binary list images. In order to perform the stretching the program converts the binary number defined by V j to a natural number image called shift distance.

The while loop efficiently generates a value of O(2 |vj | ) in O(|v j |) time. At different stages of the algorithm each of v i and v j are rescaled to their full length, across |v i | and |v j | images respectively. We get the value O(|v i | + 2 |vj | ) for grid since in the worst case V i is left shifted by the value 2 |vj | , and (when stretched) the resulting vector spans O(|v i | + 2 |vj | ) images. This upper bound also covers the right shift case (when V j is negative). Analogously we get the same value for spatialRes and dyRange (except |v k | is also in the spatialRes expression as it could contain some values before the program executes). The proof of the following lemma gives a log time algorithm to decide if a list or vector image represents a word that consists only of zeros. It is possible

The converse shift instruction (V