The crux of the difference between analog and digital computing is the number of bits of precision available, right? Now, I know that in the Turing machine, numbers can be stored with any degree of precision since the storage medium is an infinite tape.

But in the real world, physical quantities such as energy or position are not incremented in discrete chunks, as they are in their binary. Instead, their exact values can vary continuously as they do in analog circuits.

On that basis then, are there things which, fundamentally, an analog computer can do that digital computing cannot do?

  • 1
    $\begingroup$ I believe you can solve NP-hard problems in polynomial time if you allow infinite precision arithmetic which is one version of analog computing. $\endgroup$
    – Lembik
    Jan 22 '15 at 20:52
  • 1
    $\begingroup$ fairly similar to analog computers & Church-Turing thesis, good refs over there, maybe check em out & then clarify how your question is different $\endgroup$
    – vzn
    Jan 23 '15 at 2:26
  • $\begingroup$ @Lembik Really interesting. Can you back that up with a source? $\endgroup$
    – kdbanman
    Jan 24 '15 at 23:15
  • $\begingroup$ @kdbanman Here's an example: arxiv.org/pdf/1208.0526.pdf This is an analog algorithm that solves SAT in polynomial continuous time, but requires exponentially large voltage fluctuations. $\endgroup$
    – Pseudonym
    Nov 8 '20 at 6:14

Digital computers are also analog if you get down all the abstraction levels until you reach electrical circuits. The only difference is that we choose to "cut" as with some sort of grid in what levels of detectable analog shifts in signal we create another new abstraction level that we call a bit or a byte.

Anything an analog computer computes, like for example the output signal of an analog filter or the amount of millimeters that a mass in a spring and damper system moves, will also eventually reach a maximum resolution. This is because of for example noise in detectors, error in measuring equipment, and maybe quantum phenomena though I'm not so sure as how that would work. If you define a bit as that very small quantum of information you'll get a digital abstraction for the output of your analog computer.

In other words, if you use a formal abstraction of a digital computer where you can achieve enough resolution for your computations, you'll be able to compute the same than an equivalent real-world analog computer for that problem will compute.

The same problem occurs when digitizing time. For example if you look into analog and digital filter equivalencies, there is always an error that is introduced when digitizing an analog filter. That error tends to 0 as the time step used for the discretizing of the continuous system gets smaller.


In one sense the answer is yes, there are things that analog computers can do that digital computers can't. Hava Siegelmann, for instance, has investigated several classes of abstract analogue machines (in much the same way as TMs are abstract digital machines), known as recurrent neural networks (RNNs) and has shown that certain of those machines can, for example, decide any language of bitstrings. This, of course, cannot be said about Turing Machines, so these RNNs are strictly more powerful than TMs. For more information, follow the link and look at her publications.


I know that a turing computer cannot compute everything simply because it uses a countably infinite number of bits. Analog values have an uncountable (or higher infinity-ness) infinity of precision. I would check out both VSauce and ViHart out on YouTube, as they have excellent videos on the subject of infinities.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.