The other controversy that you'll see in a computer science context is that the Turing Machine specified by Turing has an <i>infinite</i> tape (or at least an unbounded tape; there are no conditions under which it can produce an out-of-memory error).<p>That means that there is no largest number (or other mathematical object) that it can represent, which is different from a physically-realized general-purpose programmable computer. On a physically-realized computer, once you fix some representation for numbers, there will always be a largest one that the computer can actually represent in its memory.<p>People have even maintained that, from the pure theory of computation point of view, the desktop computer (without threads and interrupts) is most like a finite-state machine rather than a Turing machine. It's just that each different possible memory (plus CPU register) state is a "state", so a computer with 8 GB of RAM will have something above 2^68719476736 states.<p>However, it can easily simulate a Turing machine given the assumption that the tape doesn't run out for a particular computation, including for computations that in human terms are very large and complex ones. :-)<p>Edit: One could also include the computer's hard drive as addressable memory, in which case it has even more states when viewed as a finite state machine.<p>A basic problem from an automata theory point of view is that eventually there are some inputs which need to fit entirely in memory in order to be processed correctly, and yet simply <i>can't</i> fit in memory. At that point, the computer will necessarily have to stop being as powerful as the idealized Turing machine in terms of distinguishing those inputs!
Turing was familiar with the Jacquard loom for weaving patterns on punch cards and Babbage's, and was then tasked with brute-forcing a classical cipher.<p>Quantum wave theory existed but wasn't considered necessary for classical brute-forcing. For example, Shor's algorithm for integer factorization was published in 1994.<p>Turing's paper does not specify concurrency, local or distributed. (Though is non-distributed multi-core local concurrency just also a Turing Machine?)<p>Is anything sufficient?<p>From "Church–Turing–Deutsch principle" <a href="https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%93Deutsch_principle" rel="nofollow noreferrer">https://en.m.wikipedia.org/wiki/Church%E2%80%93Turing%E2%80%...</a> :<p>> <i>The principle was stated by Deutsch in 1985 with respect to finitary machines and processes. He observed that</i> classical physics, which makes use of the concept of real numbers, cannot be simulated by a Turing machine, which can only represent computable reals. <i>Deutsch proposed that quantum computers may actually obey the CTD principle, assuming that the laws of quantum physics can completely describe every physical process.</i><p>Do modern QC allow a continuum of computable reals either? Not really yet, no; not with qubits, qudits or qutrits is there a complete real (0,1) interval. There are <i>mean</i> Expectation Values even on actual QC instead of quantum circuit simulators where it's either 0 or 1 for that run of the sim.<p>TASK: Represent e.g. π+1e-10 on a classical and then a modern quantum computer.<p>How many quantizations of theta π can there be?<p>And then with Bloch sphere rotations we have every possible unitary quantum operator?<p>And still there can be side channels in formally-verified classical and classical+quantum computers.