Skip to main content
added 281 characters in body
Source Link
Nat
  • 1.5k
  • 1
  • 13
  • 27
        [variable]
+-------[resistor]---------+
|                          |
|                       [current]
|                       [ meter ]
|                          |
+-----[  variable  ]-------+
      [power supply]

where:$$ \require{enclose} \def\place#1#2#3{\smash{\rlap{\hskip{#1pt}\raise{#2pt}{#3}}}} % \bbox[10pt]{\enclose{box}{\phantom{\Rule{250pt}{75pt}{0pt}}}} % \place{-275}{70}{\enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{resistor} \\ \text{set resistance:}~R \end{array} }}} % \place{-270}{0}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{power source} \\ \text{set voltage:}~V \end{array} }}} % \place{-55}{30}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{current meter} \\ \text{measured current:}~I \end{array} }}} $$

  • $R$ is the resistance of the variable resistor;

  • $V$ is the voltage difference of the variable power source;

  • $I$ is the current measured by the current meter.

Since we can select both $V$ and $R$ and we know Ohm's law,$$ I=\frac{V}{R}, $$we can, in principle $I=\frac{V}{R}$, we can use this circuit to divide numbers for us:

  1. Select some division problem you want to perform, $\frac{a}{b}=?$.

  2. Set the voltage source to $V=a~\mathrm{V}$.

  3. Set the resistor to $R=b~\mathrm{\Omega}$.

  4. Measure $I=?~\mathrm{A}$ to get the result!

The thing's that Ohm's law, $V=IR$, is given in terms of uses real-number values, $\left\{V,I,R\right\}{\in}\mathbb{R}$. If we believe it to be literally truethat these values actually have infinite precision, then we can select two values ofperform multiplication or division with infinite precision and multiply them together in finite time; this is a feat that a Turing machine can't perform (unless we allow for zerowith finite-time operations).

        [variable]
+-------[resistor]---------+
|                          |
|                       [current]
|                       [ meter ]
|                          |
+-----[  variable  ]-------+
      [power supply]

where:

  • $R$ is the resistance of the variable resistor;

  • $V$ is the voltage difference of the variable power source;

  • $I$ is the current measured by the current meter.

Since we can select both $V$ and $R$ and we know Ohm's law,$$ I=\frac{V}{R}, $$we can, in principle, use this circuit to divide numbers for us:

  1. Select some division problem you want to perform, $\frac{a}{b}=?$.

  2. Set the voltage source to $V=a~\mathrm{V}$.

  3. Set the resistor to $R=b~\mathrm{\Omega}$.

  4. Measure $I=?~\mathrm{A}$ to get the result!

The thing's that Ohm's law, $V=IR$, is given in terms of real values. If we believe it to be literally true, then we can select two values of infinite precision and multiply them together in finite time; this is a feat that a Turing machine can't perform (unless we allow for zero-time operations).

$$ \require{enclose} \def\place#1#2#3{\smash{\rlap{\hskip{#1pt}\raise{#2pt}{#3}}}} % \bbox[10pt]{\enclose{box}{\phantom{\Rule{250pt}{75pt}{0pt}}}} % \place{-275}{70}{\enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{resistor} \\ \text{set resistance:}~R \end{array} }}} % \place{-270}{0}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{power source} \\ \text{set voltage:}~V \end{array} }}} % \place{-55}{30}{ \enclose{box}{\bbox[5pt,lightblue]{ \begin{array}{c} \text{current meter} \\ \text{measured current:}~I \end{array} }}} $$

Since we can select both $V$ and $R$ and we know Ohm's law, $I=\frac{V}{R}$, we can use this circuit to divide numbers for us:

  1. Select some division problem to perform, $\frac{a}{b}=?$.

  2. Set the voltage source to $V=a~\mathrm{V}$.

  3. Set the resistor to $R=b~\mathrm{\Omega}$.

  4. Measure $I=?~\mathrm{A}$ to get the result!

The thing's that Ohm's law uses real-number values, $\left\{V,I,R\right\}{\in}\mathbb{R}$. If we believe that these values actually have infinite precision, then we can perform multiplication or division with infinite precision in finite time; this is a feat that a Turing machine can't perform with finite-time operations.

Source Link
Nat
  • 1.5k
  • 1
  • 13
  • 27

Unfortunately for analog computation it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not solvable on a Turing machine.

"Noise" appears to be used in the general sense of non-idealities in a signal:

In signal processing, noise is a general term for unwanted (and, in general, unknown) modifications that a signal may suffer during capture, storage, transmission, processing, or conversion.[1]

Sometimes the word is also used to mean signals that are random (unpredictable) and carry no useful information; even if they are not interfering with other signals or may have been introduced intentionally, as in comfort noise.

-"Noise (signal processing)", Wikipedia

For an example of what they're talking about, let's consider a simple circuit:

        [variable]
+-------[resistor]---------+
|                          |
|                       [current]
|                       [ meter ]
|                          |
+-----[  variable  ]-------+
      [power supply]

where:

  • $R$ is the resistance of the variable resistor;

  • $V$ is the voltage difference of the variable power source;

  • $I$ is the current measured by the current meter.

Since we can select both $V$ and $R$ and we know Ohm's law,$$ I=\frac{V}{R}, $$we can, in principle, use this circuit to divide numbers for us:

  1. Select some division problem you want to perform, $\frac{a}{b}=?$.

  2. Set the voltage source to $V=a~\mathrm{V}$.

  3. Set the resistor to $R=b~\mathrm{\Omega}$.

  4. Measure $I=?~\mathrm{A}$ to get the result!

This is a simple analog computer that can divide numbers without need for us to perform the math in some other manner, e.g. digital logic.

But what's really cool about this? If we're naive, we might believe that it can do real computation:

In computability theory, the theory of real computation deals with hypothetical computing machines using infinite-precision real numbers. They are given this name because they operate on the set of real numbers. Within this theory, it is possible to prove interesting statements such as "The complement of the Mandelbrot set is only partially decidable."

These hypothetical computing machines can be viewed as idealised analog computers which operate on real numbers, whereas digital computers are limited to computable numbers.

-"Real computation", Wikipedia

The thing's that Ohm's law, $V=IR$, is given in terms of real values. If we believe it to be literally true, then we can select two values of infinite precision and multiply them together in finite time; this is a feat that a Turing machine can't perform (unless we allow for zero-time operations).

Anyway, back to the original quote:

Unfortunately for analog computation it turns out that when realistic assumptions about the presence of noise in analog computers are made, their power disappears in all known instances; they cannot efficiently solve problems which are not solvable on a Turing machine.

They're basically saying that, whenever someone's come up with a scheme like this, the non-idealities of the situation (noise in the signals, design, etc.) tend to derail the idealistic expectations.

The quoted excerpt seems to use this as a jumping-off point to discuss how quantum computers aren't as limited by this problem as classical analog computers often seem to have been.