Tangential question: how does single cycle multiplication works in arm cortex processors? Do they just run the ALU clock fast enough that the multiplication finishes in one visible core cycle or is there a binary trick?
Any binary operation (subject to the usual "well behaved" caveat) can be split up into any number of steps; this is called pipelining. In fact there's not really a reason why multiplication isn't a single cycle step, other than speed and energy efficiency.
The maximum clock speed of an operation is limited by how fast a change in the input can be propagated into the correct change in output. You can get around this by splitting the operation into multiple mini-steps (pipelining) and clocking it to as fast as the slowest stage will go.
>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).
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.
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.
Yep, I appreciate that there is a time/space tradeoff, see this [1] from ~25 minutes ago. I agree it's not exactly the same thing. I just wanted my original comment to not be misrepresented.
Sorry if I misrepresented you. Allowing unbounded resources makes all problems trivial, whether hardware or software, using the same lookup trick.
Thus there's nothing gained from hardware, so claiming there is a constraint on software that is not in hardware isn't really correct. Both have the same constraints for fixed size machines, and both allow fast solution for unbounded size machines.
There's plenty of such "other machines" that solve NP hard problems in P time, such as closed timelike curves, chaos machines, infinitely precise engineering, etc., but such machines are generally not physically realizable, and most are not even cost effective for small n, so people use complexity to mean how the problem scales on physically realizable, cost effective devices.
If every conversation about complexity had to go through this same digression to clarify that there are indeed other areas of thought about computation that have different conclusions, then no one could cover the original topic.
Currently the Church–Turing–Deutsch principle seems to be the best formulation of such issues, and Deutsch added the physically realizable part to remove from consideration things that are math but not physics, since such machine concepts are not useful to do actual computation.
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).
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.
> 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".
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.
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.
