Dear Professor Derek Abbot, Some researches are going ahead. One of the title is as below.

"Real-Time Computing Without Stable States: A New Framework for Neural Computation Based on Perturbations"

Hi Derek,

I haven't had time to check out @Afaq's reference, which certainly sounds interesting, but from my perspective the problem that you have defined may, or may not have stable states anyway. Let me explain.

First of all, a billiard ball computer may well be performing a computation (I will define what I mean by a computer soon), however the issue with this mode of computation is that without added constraints on the trajectories it is known that the collisions are exponentially (I think, exponentially, but I haven't checked actually) sensitive to slight variations - especially when considering multiple (cascaded) collisions, hence it is unlikely that a stable computation will result.

Having said that, I do not see the fact that the balls are moving as being in any way contrary to a stable solution. One could certainly consider billiard balls with tracks (in fact I have seen ball bearing versions of this) that define their states. In such a 'track based' approach, of course electrons are doing exactly the same thing. Or even more generally, driven states that are occupied or unoccupied (e.g. Floquet states) that dynamically enable the computation.

Neural networks as @Afaq mentions have dynamically changing connectivity, so of course the states are varying throughout the computation.

In adiabatic versions of computation, the states themselves change, although of course they are locally (instantaneously) stable.

A quantum computation has a varying accessible Hamiltonian, although there one might argue that the simply because the accessed states might in general be a subset of the total number of states, then in fact the states are (usually) stable.

Actually, any system with dynamical evolution and possibly changing number of particles (e.g. a phase transition) would probably more strongly satisfy your criterion of a computer without stable states.

So I want to suggest a definition for a computation.

A computation is a mapping such that y = F(x), where y \in Y is a solution to the problem defined in the solution space Y, x \in X is a vector containing the initial conditions of the problem to be solved. Note that X need not be the same space as Y

A computer is defined to be physical system that performs an operation, and in particular can be used to simulate y_1 = G(x_1) where x_1 and y_1 are states of the computer such that x_1 ~x and y_1 ~ y. Note that implicitly x_1 and y_1 must be states of the computer and hence are in the same space, however the mapping onto X and Y must be obvious.

By 'simulate y_1 = G(x_1)' I mean that the result y_1 should be equivalent to y with probability greater than chance. This restriction takes into account probabilistic computers and digitisation type errors.

This definition allows us to start to attack your problem in a formal way, I believe.

To ensure that the mapping from the input and output space is correct, then it seems intuitive to me that the initial and final states of the computer should be stable, or at the very least specified as a result of the computation. The counter argument here is that if the initial mapping is not correct (note that I am specifically saying correct and not stable) then the problem being solved may not be known. Conversely if the output mapping is not specified then I will "not know what the answer means" (sorry, can't help quoting Deep Thought here!).

However, even if the result is comprised of varying states, it should in principle be possible to provide the output as a vector composed of both the solution and a mapping of that solution to some fiducial basis.

With this in mind, it does not seem necessary to me that the states be necessarily stable, especially where probabilistic solutions are required.

I can define state in a lot of ways --- how hard am I allowed to squint?

e.g., Process calculi are defined purely based on observable input/output --- couldn't we do the same and define the state by what's gone in and what's come out at any particular point?

Dear Professor Derek Abbot, Looking to the debate, I also want to give my opinion regarding your question and stable state. For me state is initial condition. This initial condition may be of any kind impulse, transient,steady state, random, discrete, analog, time-varying, time-invariant, linear, non-linear. The State variable approach of system analysis allows to model any of these kinds as initial condition (state). Therefore, in my opinion computation is possible without any stable states. However, I will think about your direct question related to the ball.

@Peter --- a process calculus is basically defining a machine in terms of observability of transitions, so yes (roughly) state is history. I was really just thinking of this as a example of your glasses.

Actually, @Andrew's post made me think of is stability as a form of persistence in some topological space. Even a probabilistic machine would require that we be "close enough", the definition of "close" would give us the topology. From this perspective, it doesn't matter if we have increasing particles, transitions would be observable as shifts in persistent subspaces. Your wonderful glasses would allow us to see persistence of this sort.

I think the answer is that you need a "topological constraint" to get to a final output. This could either be some notion of "track" (like the wires of an analogue computer, or the ball bearing track that Andrew mentioned), or some notion of (stable) state. I honestly have a hard time believing someone hasn't addressed this from a sound footing that at least this crank on ResearchGate doesn't have.

Hi Guys,

I agree that we seem to be struggling here around the definition of state. As noticed, my personal approach is to look to systems that I think I understand and extrapolate and abstract as needed, so of course I look to quantum. Nevertheless, I don't think that quantum is required here, and Afaq's post regarding neural is definitely not quantum, but should also satisfy all of Derek's problems.

So returning to my earlier definition, I would suppose that states are what are actually operated on. So in the context of an AND gate for example, we have two states going in, and one state that comes out. In the canonical AND gate, the states are voltage levels and they need to be stable enough compared with threshold voltages. Also note that in general we would expect that the output is ultimately the same level as one of the inputs so that operations can be cascaded. So conventional digital computing would seem to satisfy the criterion of stable states.

But I really don't think that this is necessary, and the topological argument is one approach, but personally I find the adiabatic approach more compelling (but perhaps it is simply that I am more familiar with it).

In adiabatic quantum computing, you encode your problem space in a Hamiltonian such that the solution you want is the ground state of this Hamiltonian. This encoding can typically be performed in polynomial time. Call this H_s. You have some initial Hamiltonian H_0, where you can initialise into the ground state. The operation of the computation is to evolve the system according to the Hamiltonian H = \alpha H_s + (1 - \alpha) H_0, for adiabatically (slowly) varying \alpha. To retrieve the answer you measure the final ground state.

Now in this context, the states are all varying in energy in highly non-trivial fashions. At any instant, however, they are of course stable, but the nature of the states at all stages of the evolution are in general varying. Also note that the comment about perturbations made above still holds. Provided the energy gap between states is large compared to the energy perturbations, you suppress noise.

Certainly this approach is qualitatively different from the conventional circuit model, but it is equally a computation (in fact it is formally equivalent to the circuit model of quantum computation).

Now starting from this, we can also consider an operation that might have a combination of adiabatic and nonadiabatic steps. It will be highly sensitive to noise, but there's no reason why it shouldn't work. We can even go further, and consider operations in which the number of states varies as a function of time either by introducing extra particles, or nonlinear eigenstates. Definitely complicated, probably weird, but not inconceivable.

All the best

Andy

Http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.5.8123&rep=rep1&type=pdf

The question makes me wondering if the author is not actually starting (or referring to) a discussion about non-conventional computation. In such a way, we need to face the challenge (and advantages) of a non-deterministic domain, an orthogonal one in relation to what we typically learn in computation theory. Two sources of research inspiration in this area are Analog Computation (what the guys did until 50's to achieve a powerful calculator machine) and Quantum Mechanics.

Besides these two lines of research, we can also think about the scenarios when we try to define a state for a system which deals with a very high number of input variables. Although we are strictly talking about conventional computation in this case, from the practical perspective, we quickly have to deal with the issue called "states explosion". Besides the complexity in modeling such cases, a high processing capability is required if we really want a full-deterministic computing device. Regarding this topic, an interesting line of research is Virtual Finite State Machine which personally I have been using for 4 years in order to achieve high reliability in the domain of embedded systems with hundred or thousands of possible input "states".

Returning to the original question, my current answer is "yes", but in the domain of non-conventional computation. I can change my answer if the author gives additional details in his question :)

Dear Professor Derek Abbot,

What about Oscillator?