Continue to Site

Welcome to our site!

Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

  • Welcome to our site! Electro Tech is an online community (with over 170,000 members) who enjoy talking about and building electronic circuits, projects and gadgets. To participate you need to register. Registration is free. Click here to register now.

Continious time loop computer

Status
Not open for further replies.

Jarek Duda

New Member
Let's take some NP-problem: we have a verifier which can quickly say that given input is correct or not, but there is huge number of possible inputs and we want to tell if there is a correct one (find it).

Imagine we have a chip with 'input' and 'output' in which is implemented (e.g. FPGA):

IF 'input' verifies the problem
- THEN send 'input' to 'output'
- ELSE send next possible 'input' (cyclically) to 'output'

such that this chip uses only basic logic gates - computations are made by some small number of layers - IT DOESN'T USE CLOCK (we can do it for some NP problems like 3SAT).

Now connect it's 'output' and 'input' to make a loop.

Such loop will be stable if it has found a solution (which can be transferred out).
If there would be a clock, in each cycle there would be checked one input. But without clock it should be pure hydrodynamics of electrons.
If there is a solution, other states would create fluctuations in time - should be less energetically preferred than the stable one - physics should quickly solve our problem.

I know - there can be a problem with nonlinearity of transistors? If yes, there are plenty of technologies, maybe some of them would handle with it?

If it would really work, cryptosytems we are currently use are in danger - it should easily break RSA or find a key which if used on a beginning of an encrypted file makes output with significant correlations...
 
There is always going to be a propagation delay, which will make it useless for the subset of NP problems involved in cryptoanalysis. Same as any other finite-state machine, it isn't going to solve NP-complete problems in anyone's lifetime.

There were clockless computers long before I was born - look up "Perceptron". Trying to make a Feynman processor simply by eliminating the clock is naive.
 
Probably You are right that it shouldn't be qualitatively faster, but I'm not sure of it.
This time it's continuous computer - we should think about it in terms of hydrodynamics (of electrons) - I imagine a river which goes around (because of pumps in the logical gates) and wants to minimize some energy of 'turbulences'. Because of this continiousness, it could have a tendency of finding some short path to the solution.

Motivation for perceptron was completely different. I've looked a bit and I didn't find anything similar to what I've presented. This idea comes from the idea of time-loop computers: there are some reasons to believe that physics can allow to make a prediction in microscale. If we could predict that in let say nanosecond will be absorbed a photon, we could transfer data back in time. If we would use it to close such causality loop, physics should stabilize if it can, to prevent paradoxes. If it's not possible it should break the weakest link - make that the prediction would go wrong:
Time-loop computers ? - sci.physics.foundations | Google Groups
 
Last edited:
The ultimate 'turbulence' is going to be the thermal interactions of whatever conductors or semiconductors that provide the framework for the electron gas to travel through.

In its simplest form, what you are looking at would be like an inverter with the input coupled to the output. It isn't going to have that "continuousness" necessary for this kind of computing. Because of thermal interactions (even if you don't observe the output) it is simply going to switch quickly between two discreet states, and not give a simultaneous dual-state condition that would be necessary as part of something that could solve, say, traveling salesman problems.
 
Last edited:
I completely agree that connecting (a good) NOT gate with itself should create oscillations ... and if You would made a chip as proposed for NP-problem with no input which could verify it - there should also occur some neverending oscillations (irregular this time).
These loops just cannot stabilize.
The question is about those which can stabilize - could they have a tendency to make it qualitatively faster than trying input by input in succeeding cycles, as we would classically do it?

About thermal interaction - manipulating the voltage, we could make something like simulated annealing, to help it with stabilizing.
 
I think you are missing some of the subtlety of things like perceptrons and neural networks. The outcome of this line of thought was exactly that. Here - look at this, it's a very simple example:
**broken link removed**
No clock, and the outputs are coupled to the inputs such that it reaches a stable state that gives a digital code corresponding to input voltages. Yes, they can be very fast.

I am very interested in simulated annealing, it's one of a few techniques that makes any headway in complex systems analysis. Unfortunately, it cannot be applied to the kinds of thermal interactions that collapse wavestates.
 
This digitizer still doesn't make a loop/feedback, but just makes the calculation once on given input. In artificial neural networks like perceptron, there are considered some feedbacks, but they rather use small corrections for training process. Natural NN are a bit closer - they have thousands of feedbacks in each neuron, for example to create/use synchronization mechanism (brainwaves). But they work on pretty digital impulses and as I said - NN has completely different motivation.

This loop computer wouldn't work by small corrections but on drastic ones. And is too nonlinear to be just wave collapse. But thanks of its continuity it could have some thermalisation properties which should help to stabilize.
 
It DOES make a loop, it DOES have feedback, and couldn't work without it. Read the text. Look at how those resistors from the outputs are tied into networks that feed back into the input. I spent an hour finding a perfect, concise example of what you were talking about, and you barely looked at it.

Stop kidding yourself that the feedback in Perceptrons and N-nets used in "small corrections for training process" is somehow incidental or unimportant, if you couldn't train it, it wouldn't work.

To solve NP problems, systems like these are going to need to maintain a superposition of state through the computing elements. Thermal interactions destroy this, they don't stabilize it.
 
So draw it horizontally. This digitizer in first 'cycle' fixes the oldest bit and there could be no rest of the circuit, in the second-the same with the second... I agree that it's smart, but practically for me it just makes four sequential 'cycles'. But there is no point arguing about nomenclature.

I'm not saying that training artificial NN is not important, but that the situation is much easier than in loop computer(LC) - it uses designed gradients and small steps. LC would use gradients gave by pure physics - hydrodynamics of electrons.

Thermal interactions could be useful while finding global minimum (simulated annealing), but I agree that they could even destroy a stable state in LC ... maybe even to work they would require some special technology like superconductors or photonic ... but these potential possibilities ...
 
It's not sequential. It's simultaneous. You still don't understand how it works.
 
The only feedback are 2.2 resistors (like R5/30) for some compensation. Without them for me it's fully sequential - comparator practically doesn't influence own input.
Like I've said - I don't want to argue about it - anyway it's something completely different.
 
*sigh* You still didn't bother to read the text, did you? It mentions R21-23, just study that one little part of it, I'm sure you will catch on. It's not "completely different", and electronics engineers have been designing things like it for 50 years.
 
R21-23 subtracts older bits if necessary to calculate the youngest one. It's nicely done but for me it's also basic. Loop is when output of a gate influences own input.
 
Last edited:
Oh, now it's "basic", huh? LOL! Do you finally understand that it works in a loop and is simultaneous?
 
I'm guessing not, since you referred to "youngest" and "oldest", and are in denial about the outputs influencing the inputs.
 
Last edited:
9 years have passed ... and I still have no idea if this way of converting hard computational problems into a physical system have a chance to be useful?
WQFXL.jpg

I have recently put it on stack: https://physics.stackexchange.com/questions/365542/continuous-time-loop-computer-for-np-problems
... and had discussion with Peter Shor (responsible for popularity of quantum computing) - the conclusion for now is that this approach is not known in literature, and we don't know if it can work (?)
Any thoughts?
 
Status
Not open for further replies.

Latest threads

New Articles From Microcontroller Tips

Back
Top