Classical Turing Machine Vs. Quantum Turing Machine: The Clash of two Titans

What is the result of the product of 2 and 5? Please keep that result in mind. What then is the output of multiplying 25 by 2, and then dividing the result by 5? Having this result in mind, add it to the result from the former computation. Is the overall result 20? How are you sure you are correct? Where did you store the former results? How did you perform the mathematical operations in your head? In what order? What chemical, neurological or mechanical process occurred in your brain that enabled you to compute, store the results and manipulate the stored result to generate the output? Is there a mechanical method to accomplish this? Can a machine be designed to emulate these computational processes? These and many more questions in this line of thought were being asked during the early 19th century, and was summarized as the “decision problem” (Entscheidungsproblem).

One of the major issues was that for decades words like symbols, algorithm, computable, functions, etc. were being tossed around in questions without themselves been properly defined. This led to lots of ambiguities and contradictions when attempting to solve the “decision problem”. It was David Hilbert who stripped down the essence of these questions into three parts: Was mathematics complete? Was mathematics consistent? And, was mathematics decidable? While Kurt Godel provided the answer for the first two questions, it took five years later for Allan Turing to provide an answer for the decidability question. Don’t be mistaken. At this time there had been invented lots of machines that can perform calculations and computations based on specific inputs to generate solutions as output; the imperative question at the time was, can a machine think and make decisions for itself based on its “state of mind” and the input variable presented to it?

In his search into the foundations of mathematics, Allan Turing introduced the concept of the Turing Machine: the development of the first abstract machine. This was a machine that “provides a models with which one can reason about an algorithm in a mathematically precise way without being tied to any particular formalism”. He tried to design a state of mind, which can take mechanical actions of one-step movement and symbol detection/writing, and performs its operations in an automated manner – a computer. Its “head” could either read/write a symbol on a tape, move left/right and change its internal state or not: all of which is dependent on the current symbol on an infinite tape, and the “state of mind” of the machine. ?Due to the infinite tape, the machine possessed infinite storage space, and given infinite time, could perform any computable calculation. It was an idealistic model of a central processing unit.

After some tweaks and fix of the original Turing machine, the creation of Lambda Calculus by Alonzo Church, and the formalized definition of a general recursive function by Kurt Godel, the operations of a Universal Turing Machine (UTM) was formalized. This was regarded as the Church-Turing thesis: in other words, this a machine which, theoretically, can compute any computable sequence. Just as the use of the term effectively calculable functions needed to be redefined and formalized by an effective method, the use of the effective method needs to be further formalized for the Church-Turing thesis to be provable, and a Universal Turing Machine universally accepted.

Let us be particular about the foundational building blocks, concepts and logic with which the Turing machine was designed; it is only then can we be aware of the potential limitations, if any, of the machine. Note that each operation of the machine is finite, discrete and distinguishable; these are characteristics that are suitable for counting, particularly integers. Therefore, a Turing computable statement or algorithm has to be presented in the first-order logic, whether it is derivable from it or not. Is this a weakness or a strength? Limiting the symbols of computation to 0s and 1s did certainly made using the first-order logic and operational computation much manageable by contemporary computers; but note that the set of symbols isn’t limited to 0s and 1s, as long as they can be clearly defined and distinguishable.

However, at the moment, anything a modern-day computer can compute, a Turing Machine can also compute. Contemporary computer programs, computer processors and random-access machines are built on the theoretical foundations provided by an idealistic Turing Machine. Although, there are tons of other abstract machines after Turing’s, they are all computable by a UTM.

It has been noted that some functions are mathematically definable but not computable. The birth of quantum mechanics has exacerbated the need to redefine and formalize the classical meaning and implications of the effective method. Furthermore, mathematical problems like Shor’s algorithm has once more extended the meaning and implications of algorithm and computation. Some physicist believes that the titan Classical Turing Machine would need to be replaced by a Quantum version whose computational ability would supersede it. Others believe that a UTM could be able to compute all quantum algorithm as long as they can be properly defined into a classical sequential algorithm. Do we really need another titan? A Quantum Turing Machine? If so, what would its “state of mind” and mode of operations be like? Is this even possible? And if so, is it necessary?

TO BE CONTINUED.

This article is for instructional and didactic purpose. If you found it informative and inspiring please like, comment, share and re-post.