0
$\begingroup$

Ignoring quantum mechanics for a moment, is it true that analog computers are more powerful than turing machines? for example an analog computer can add two irrational numbers together, but a turing machine cannot.

but if one were to take quantum mechanics into account, I still think it's reasonable to redefine effective computation based off the power of analog computers since although the real world is technically discretized, it is also the case that you cannot build unbounded machines in the real world.

Improve this question
$\endgroup$
3
  • 3
    $\begingroup$ In what sense can an analog computer "add two irrational numbers together" that a Turing machine can't? $\endgroup$
    – Naïm Favier
    Commented Jun 3 at 20:22
  • $\begingroup$ @NaïmFavier Turing machines can't add irrational numbers together with perfect precision in finite time $\endgroup$
    – JobHunter69
    Commented Jun 4 at 15:00
  • 1
    $\begingroup$ I guess my point is that a model of computation requires specifying input and output encodings. If your analog computer can add real numbers instantly with infinite precision but you can only read finite amounts of the result in finite time, then what's the point? $\endgroup$
    – Naïm Favier
    Commented Jun 4 at 15:16

1 Answer 1

Reset to default
2
$\begingroup$

As far as anyone can tell, no, analog computers are not more powerful than Turing machines. In practice, they run into problems with errors accumulating rapidly.

It's also worth pointing out that specifying how to provide information as an input, and how to read it from the output is not entirely trivial. For instance, if I gave you an irrational number, how would you encode it as a stick of that length, or a bucket of water of that volume? It's basically not possible. If the output is a stick of some length, or a jug of water of some volume, how would you measure its length or volume to sufficient precision to distinguish between rational vs irrational numbers? You can't. You can only measure to finite accuracy, and the time it takes to measure is (at least) proportional to the number of digits of precision needed (and probably much more).

So it is widely believed that there is no free lunch here.

See also the extended Church-Turing hypothesis, which proposes that no realizable computation method is faster (by more than polynomially) than a Turing machine. See especially https://en.wikipedia.org/wiki/Church%E2%80%93Turing_thesis#Variations.

Improve this answer
$\endgroup$
7
  • $\begingroup$ This is a good answer. To put it in perspective, the smallest possible measurement scientists believe can exist, is a planck length. Which is 10 ^ -35 meters. Which is 35 zeroes after the fullstop. Any modern computer could easily calculate something accurately to 35 decimal places. But 2 sticks that are 10 ^ -35 meters long each, can't be added together to get 2 * the plank length. And I don't think something like this is feasible even with analog electronics like resistors. Though I think there might exist cases where an analog computer could be better over a normal digital one. $\endgroup$
    – Minko_Minkov
    Commented Jun 4 at 6:25
  • $\begingroup$ "if I gave you an irrational number, how would you encode it as a stick of that length," well you would give it to me as, for example, the charge on a capacitor. Not sure what you mean $\endgroup$
    – JobHunter69
    Commented Jun 4 at 15:01
  • $\begingroup$ @JobHunter69, if I have an input of $x=\sqrt{23}+\cos(\pi/17)$ (some irrational number) that I want to provide to an analog computer, how do I arrange to charge up a capacitor so it has charge $x$? $\endgroup$
    – D.W. ♦
    Commented Jun 4 at 17:02
  • $\begingroup$ @D.W. The input comes in the form of the capacitor. A counter question is, if I have a capacitor of irrational charge x, how do I arrange a digital computer to input this number? $\endgroup$
    – JobHunter69
    Commented Jun 4 at 18:22
  • $\begingroup$ @JobHunter69, under the ordinary understanding of a computer, if I have some data I want to compute on, there has to be some way to provide that to the computer as input. For a digital computer, the answer is that you cannot provide irrational numbers as input. You suggested that a Turing machine cannot take irrational numbers as input but an analog computer can, and I'm pointing out there are some flaws in that statement. Even if you ignore that, there still remain the issues with reading off the output and with noise accumulation. $\endgroup$
    – D.W. ♦
    Commented Jun 4 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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