1. 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.
    Dismiss Notice

Continious time loop computer

Discussion in 'Electronic Projects Design/Ideas/Reviews' started by Jarek Duda, Dec 22, 2008.

  1. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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...
     
  2. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    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.
     
  3. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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: Dec 25, 2008
  4. dave

    Dave New Member

    Joined:
    Jan 12, 1997
    Messages:
    -
    Likes:
    0


     
  5. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin

    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: Dec 26, 2008
  6. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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.
     
  7. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    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:
    PAiA Corporation: 4 Bit Digitizer Flash Converter
    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.
     
  8. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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.
     
  9. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    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.
     
  10. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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 ...
     
  11. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    It's not sequential. It's simultaneous. You still don't understand how it works.
     
  12. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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.
     
  13. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    *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.
     
  14. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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: Dec 28, 2008
  15. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    Oh, now it's "basic", huh? LOL! Do you finally understand that it works in a loop and is simultaneous?
     
  16. duffy

    duffy New Member

    Joined:
    Dec 22, 2008
    Messages:
    2,618
    Likes:
    73
    Location:
    nortern 'sconsin
    I'm guessing not, since you referred to "youngest" and "oldest", and are in denial about the outputs influencing the inputs.
     
    Last edited: Dec 28, 2008
  17. Jarek Duda

    Jarek Duda New Member

    Joined:
    Dec 22, 2008
    Messages:
    8
    Likes:
    0
    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?
    [​IMG]
    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?
     

Share This Page