4 ms·

The paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.

by _0ffh 8y ago

wbhart 8y ago
Is there a known example of something a digital computer can do that a Turing machine cannot?
- your-nanny 8y ago
  overheat.
- Retra 8y ago
  Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
- pmiller2 8y ago
  In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
  - kps 8y ago
    Real computers generally have external storage and/or network interfaces, which makes them unbounded.
    - pmiller2 8y ago
      No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.
- wolfgke 8y ago
  > Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".
ChrisLomont 8y ago
>Actual digital circuits are not bound to that constraint. Yes they are. Hardware can parallelize, but does not remove asymptotic complexity for arbitrarily sized problems. It only changes the hidden constant cost. The paper result is for unbounded size for n. Hardware has fixed size n, and for a fixed size n, any problem is constant time O(1).
- systemBuilder 8y ago
  Andy Yao proved a lower bound on circuit complexity for multiplication of circuit width x depth = Omega(n ^ 2). Trivial carry circuits for adders are O(n).
- _0ffh 8y ago
  Hardware might have fixed size n, but a general approach certainly doesn't! I must have failed badly at making my point clearly, because I've got that same criticism more than once. Take as an example this paper [1], which explicitly states the delay of an n-bit Baugh-Wooley multiplier as O(log n). I appreciate that this might not be what people are discussing here - if so, excuse me mixing things up. I answered to a question that asked about a connection between the Turing machine algorithm and practical circuit design, and I tried as best I could to give a practical circuit design perspective. [1] https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf
  - ChrisLomont 8y ago
    I'm familiar with such results. TAOCP has quite a few I've fiddled with over the years. It has an O(n) multiply, for example. Most (all?) algorithms can be made O(log n) by throwing hardware at it. The hardware is basically a lookup table, and you can inspect each bit of a length n problem in O(log n) time, and output the answer. Papers like this use problem structure to reduce the general exponential circuit growth to (usually) ~linear growth. But all I've seen require unbounded circuit growth, as does this one, which is O(n log n) circuit size. By allowing hardware to grow at unbounded rate, it's not really solving the same problem.

The paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.

by _0ffh 8y ago

The paper applies to integer multiplication on a Turing machine. Actual digital circuits are not bound to that constraint.

wbhart 8y ago

Is there a known example of something a digital computer can do that a Turing machine cannot?

your-nanny 8y ago
overheat.
Retra 8y ago
Turing machines can simulate any other machine, but they can't do what any machine can do. You can simulate a toaster, but only a real machine can actually make toast.
pmiller2 8y ago
In terms of computational power, real computers (ignoring physics) are linear bounded automata, which is a class of automata strictly weaker than Turing machines. Throwing physics into the mix means they’re unreliable computing devices.
- kps 8y ago
  Real computers generally have external storage and/or network interfaces, which makes them unbounded.
  - pmiller2 8y ago
    No, you’re still limited by the computational power of the universe. Since there is a finite amount of energy and a finite number of particles, you’re limited to a finite number of states. The entire universe is no more powerful than a very large, but finite, linear bounded automation.
wolfgke 8y ago
> Is there a known example of something a digital computer can do that a Turing machine cannot? - Physically exist, since Turing machines are a purely abstract mathematical model that can because of the infinite length of its tape never realized physically. - Many computation models that are based on a Turing machine are based on the idea: a) Write the input of the algorithm on the tape b) Let the Turing machine do the computation c) When the Turing machine terminates, read the output from the tape. The problem is: Many things that one want to do on computers do not fit this model: * interact with the outside word * programs that do not terminate: for example an OS kernel is not supposed to stop when some computation stops, but should continue scheduling the processes. Both are simply not part of a computation based on the above idea. I am aware that there of course exist extensions where such things are part of. But here the definition of the Turing machine is IMHO much more "artifical" than its original intent for defining "computability".

ChrisLomont 8y ago

>Actual digital circuits are not bound to that constraint. Yes they are. Hardware can parallelize, but does not remove asymptotic complexity for arbitrarily sized problems. It only changes the hidden constant cost. The paper result is for unbounded size for n. Hardware has fixed size n, and for a fixed size n, any problem is constant time O(1).

systemBuilder 8y ago
Andy Yao proved a lower bound on circuit complexity for multiplication of circuit width x depth = Omega(n ^ 2). Trivial carry circuits for adders are O(n).
_0ffh 8y ago
Hardware might have fixed size n, but a general approach certainly doesn't! I must have failed badly at making my point clearly, because I've got that same criticism more than once. Take as an example this paper [1], which explicitly states the delay of an n-bit Baugh-Wooley multiplier as O(log n). I appreciate that this might not be what people are discussing here - if so, excuse me mixing things up. I answered to a question that asked about a connection between the Turing machine algorithm and practical circuit design, and I tried as best I could to give a practical circuit design perspective. [1] https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf https://www.irjet.net/archives/V3/i2/IRJET-V3I259.pdf
- ChrisLomont 8y ago
  I'm familiar with such results. TAOCP has quite a few I've fiddled with over the years. It has an O(n) multiply, for example. Most (all?) algorithms can be made O(log n) by throwing hardware at it. The hardware is basically a lookup table, and you can inspect each bit of a length n problem in O(log n) time, and output the answer. Papers like this use problem structure to reduce the general exponential circuit growth to (usually) ~linear growth. But all I've seen require unbounded circuit growth, as does this one, which is O(n log n) circuit size. By allowing hardware to grow at unbounded rate, it's not really solving the same problem.