![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bg7f.png\")
<\/p>\n\n\n\nFor a long time historically, computation was a matter of actually solving,<\/p>\n\n\n\n
or \ufb01nding algorithms to solve, various mathematical problems using mechan-<\/p>\n\n\n\n
ical or other algorithms. It was only in the early twentieth century that the<\/p>\n\n\n\n
process of computation was modelled in mathematical terms, largely in the<\/p>\n\n\n\n
works of Alan Turing, Alonso Church, Kurt G\u00a8odel, and Emil Post. Their e\ufb00orts<\/p>\n\n\n\n
were directed at extracting the basic properties of a computational process,<\/p>\n\n\n\n
independent of the platform on which it was executed.<\/p>\n\n\n\n
The \ufb01rst question regarding computation that a theoretician asks is<\/p>\n\n\n\n
whether or not the given problem is computable. What exactly does this mean?<\/p>\n\n\n\n
If the problem is somehow reduced to the calculation of a function, then is this<\/p>\n\n\n\n
function computable? In order to meaningfully answer this question without<\/p>\n\n\n\n
having to examine all possible algorithms designed to compute the function,<\/p>\n\n\n\n
the famous mathematician Alan Turing came up with a theoretical model<\/p>\n\n\n\n
computer known as the Turing Machine, which is a simpli\ufb01cation of your<\/p>\n\n\n\n
desktop computer to the bare bones.<\/p>\n\n\n\n
101<\/p>\n\n\n\n
<\/p>\n\n\n\n
102 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
6.1.1 Turing machine<\/p>\n\n\n\n
Turing\u2019s abstract computing machine captures the concept of an algorithm<\/p>\n\n\n\n
to evaluate a function. It can be thought of as a mechanical analogue of an<\/p>\n\n\n\n
algorithm broken down to its bare bones. Now an algorithm basically takes<\/p>\n\n\n\n
an input in some symbolic form, performs basic manipulations in steps that<\/p>\n\n\n\n
may even be recursive and \ufb01nally \ufb01nishes up with an output. In the paradigm<\/p>\n\n\n\n
of a computing machine, the machine has a means of accepting and reading<\/p>\n\n\n\n
an input, a set of instructions on what basic steps to perform, which may<\/p>\n\n\n\n
depend on the output at a previous step. The machine must therefore be able<\/p>\n\n\n\n
to move back and forth over previous steps and write out the answer at<\/p>\n\n\n\n
each step, and halt when the process is over. This mechanism of comparing<\/p>\n\n\n\n
outputs to conditions in the program can be achieved easily by attributing an<\/p>\n\n\n\n
internal state to the machine.<\/p>\n\n\n\n
FIGURE 6.1: A schematic of a Turing machine.<\/p>\n\n\n\n
Turing modelled this process in an abstract machine (TM), schematically<\/p>\n\n\n\n
shown in Figure 6.1, consisting of the following.<\/p>\n\n\n\n
1. A tape which is a string of cells that can contain one of a \ufb01nite set of<\/p>\n\n\n\n
symbols, \u0393 = {S<\/p>\n\n\n\n
i<\/p>\n\n\n\n
}, which could, for example, be binary 0 and 1, a blank<\/p>\n\n\n\n
(<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0) and a special symbol B, for the left edge of the tape.<\/p>\n\n\n\n
2. A read\/write head that can take input from or write output to a cell<\/p>\n\n\n\n
at a time when fed into the machine.<\/p>\n\n\n\n
3. A register that stores the internal state of the machine, which could<\/p>\n\n\n\n
be one of a \ufb01nite set of states {q<\/p>\n\n\n\n
i<\/p>\n\n\n\n
}. There are two special states, S, the<\/p>\n\n\n\n
starting state and H, the halting state.<\/p>\n\n\n\n
4. A table of instructions (like a program) that make the head execute<\/p>\n\n\n\n
a Left move, a Right move, and a Print, depending on the symbol<\/p>\n\n\n\n
currently read by the head. This is like a function f(q, x) = hq<\/p>\n\n\n\n
0<\/p>\n\n\n\n
, x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
, mi<\/p>\n\n\n\n
![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bg80.png\")
<\/p>\n\n\n\n
Computation Models and Computational Complexity 103<\/p>\n\n\n\n
where q is the current state of the machine, x is the current symbol read,<\/p>\n\n\n\n
q<\/p>\n\n\n\n
0<\/p>\n\n\n\n
is the new state after execution of the step, x<\/p>\n\n\n\n
0<\/p>\n\n\n\n
is the symbol written<\/p>\n\n\n\n
on to the tape, and m is a move L, R, or 0.<\/p>\n\n\n\n
Example 6.1.1. To see how a TM might work, consider one with binary<\/p>\n\n\n\n
symbols, \u0393 = {0, 1,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0, B} and internal states Q = {S, q<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, q<\/p>\n\n\n\n
2<\/p>\n\n\n\n
, q<\/p>\n\n\n\n
3<\/p>\n\n\n\n
, H}. Let the<\/p>\n\n\n\n
table (program) be as follows:<\/p>\n\n\n\n
H<\/p>\n\n\n\n
H<\/p>\n\n\n\n
H<\/p>\n\n\n\n
H<\/p>\n\n\n\n
H<\/p>\n\n\n\n
x<\/p>\n\n\n\n
q<\/p>\n\n\n\n
i<\/p>\n\n\n\n
B 0 1<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0<\/p>\n\n\n\n
S hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, B, Ri<\/p>\n\n\n\n
q<\/p>\n\n\n\n
1<\/p>\n\n\n\n
hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, 0, Ri hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, 1, Ri, hq<\/p>\n\n\n\n
2<\/p>\n\n\n\n
,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0, Li<\/p>\n\n\n\n
q<\/p>\n\n\n\n
2<\/p>\n\n\n\n
hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0, Li, hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0, Li<\/p>\n\n\n\n
q<\/p>\n\n\n\n
3<\/p>\n\n\n\n
hH, B, 0i hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
, 0, Li, hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
, 1, Li hH,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0, Li<\/p>\n\n\n\n
Can you see what this machine achieves? Take for example an input string<\/p>\n\n\n\n
110 on the tape followed by blanks. The tape would look like<\/p>\n\n\n\n
B 1 1 0<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0 . . .<\/p>\n\n\n\n
The sequence of states followed by the machine are:<\/p>\n\n\n\n
hS, Bi \u2192 hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, Bi<\/p>\n\n\n\n
R<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, 1i<\/p>\n\n\n\n
R<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, 1i<\/p>\n\n\n\n
R<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
1<\/p>\n\n\n\n
, 0i<\/p>\n\n\n\n
R<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
2<\/p>\n\n\n\n
,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0i<\/p>\n\n\n\n
R<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
,<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0i<\/p>\n\n\n\n
L<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
, 1i<\/p>\n\n\n\n
L<\/p>\n\n\n\n
\u2212\u2192 hq<\/p>\n\n\n\n
3<\/p>\n\n\n\n
Bi \u2192 hH, Bi.<\/p>\n\n\n\n
The tape now looks like<\/p>\n\n\n\n
B 1 1<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\ue001<\/p>\n\n\n\n
0 . . .<\/p>\n\n\n\n
You can see that this machine erases the last symbol on the tape. Try it<\/p>\n\n\n\n
out on a di\ufb00erent input.<\/p>\n\n\n\n
Exercise 6.1. Try to construct the table of instructions for a TM that adds 1 to<\/p>\n\n\n\n
the entry on the tape.<\/p>\n\n\n\n
Every TM is speci\ufb01ed by its own set of symbols \u0393, set of internal states<\/p>\n\n\n\n
Q, and program. So there exists a speci\ufb01c Turing machine for every speci\ufb01c<\/p>\n\n\n\n
algorithm. However, the machine may be made programmable according to<\/p>\n\n\n\n
di\ufb00erent algorithms, if the program is also fed in as part of the input. Thus a<\/p>\n\n\n\n
programmable Turing machine can simulate any other Turing machine: this<\/p>\n\n\n\n
is the universal Turing machine (UTM).<\/p>\n\n\n\n
In his work, strengthened by the work of Alonso Church, who was simulta-<\/p>\n\n\n\n
neously working on Hilbert\u2019s famous computability problem, Turing was able<\/p>\n\n\n\n
to prove the thesis that any algorithm could be simulated by a UTM. Church\u2019s<\/p>\n\n\n\n
work strengthened this to the Church\u2013Turing thesis:<\/p>\n\n\n\n
104 Introduction to Quantum Physics and Information Processing<\/p>\n\n\n\n
Theorem 6.1. Any function that can be computed by an algorithm can be<\/p>\n\n\n\n
e\ufb03ciently simulated by the Universal Turing Machine.<\/p>\n\n\n\n
Turing was then able to formulate the problem of computability in terms<\/p>\n\n\n\n
of whether or not such a universal machine would halt, i.e., \ufb01nd a solution. So<\/p>\n\n\n\n
problems on which this machine halted would then be called computable.<\/p>\n\n\n\n
Interestingly enough, the famous halting problem, viz. whether or not a<\/p>\n\n\n\n
particular algorithm on a Turing machine will halt, is itself uncomputable!<\/p>\n\n\n\n
The question then begged to be asked as to whether a given problem that<\/p>\n\n\n\n
is not computable by a UTM can be made so by a di\ufb00erent paradigm of com-<\/p>\n\n\n\n
putation. This led to extensions of the Turing machine concept to probabilistic<\/p>\n\n\n\n
Turing machines where the algorithms made use of fuzzy logic.<\/p>\n\n\n\n
6.1.2 Probabilistic Turing Machine<\/p>\n\n\n\n
One of the major challenges to the Church\u2013Turing thesis came from al-<\/p>\n\n\n\n
gorithms that were probabilistic, that is, could solve problems e\ufb03ciently but<\/p>\n\n\n\n
with a certain (bounded) probability of failure. These problems, for instance<\/p>\n\n\n\n
the Solovay\u2013Strassen primality test (1977) cannot be e\ufb03ciently solved on the<\/p>\n\n\n\n
deterministic Turing machine described above.<\/p>\n\n\n\n
Computer scientists therefore extended the validity of the Church\u2013Turing<\/p>\n\n\n\n
thesis to probabilistic algorithms by designing a probabilistic Universal Turing<\/p>\n\n\n\n
Machine.<\/p>\n\n\n\n
A probabilistic or randomized Turing machine is one in which randomness<\/p>\n\n\n\n
is built into each step which chooses possible options according to a probability<\/p>\n\n\n\n
distribution. Such a machine therefore would need to have an additional tape:<\/p>\n\n\n\n
the random tape, containing a string of random numbers to decide the options<\/p>\n\n\n\n
at each step. Without going into details, we will state that a probabilistic<\/p>\n\n\n\n
universal Turing machine (PTM) can replace the earlier deterministic one<\/p>\n\n\n\n
to save the Church\u2013Turing Thesis in its stronger form.<\/p>\n\n\n\n
There is a plethora of randomized complexity classes that can be de\ufb01ned<\/p>\n\n\n\n
for randomized algorithms that we will not go into, but this extends the class<\/p>\n\n\n\n
of e\ufb03ciently solvable problems.<\/p>\n\n\n\n
6.1.3 Quantum Turing Machine<\/p>\n\n\n\n
The challenge to this model of computation came with trying to simulate<\/p>\n\n\n\n
quantum mechanical systems on a PTM; this was still unsolvable. The natural<\/p>\n\n\n\n
question to ask was whether or not it was possible to generalize to a quantum<\/p>\n\n\n\n
Turing machine (QTM) that would further expand the class of solvable<\/p>\n\n\n\n
problems. This was done by David Deutsch in 1985 though thought of earlier<\/p>\n\n\n\n
by Benio\ufb00 and Bennett.<\/p>\n\n\n\n
The most important idea behind this machine, which is also probabilistic,<\/p>\n\n\n\n
is that it is reversible, in the same way as quantum time evolution is reversible.<\/p>\n\n\n\n
The idea behind discussing Turing models is to see if the class of problems<\/p>\n\n\n\n
![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bg82.png\")
<\/p>\n\n\n\n
Computation Models and Computational Complexity 105<\/p>\n\n\n\n
that are hard to solve can be made smaller. As it turned out, while QTMs<\/p>\n\n\n\n
cannot reduce the class of unsolvable problems, they do reduce that of hard<\/p>\n\n\n\n
problems.<\/p>\n\n\n\n
The Turing model is the most mathematically abstract model for compu-<\/p>\n\n\n\n
tation, and is widely used to establish computability and upper bounds on<\/p>\n\n\n\n
the e\ufb03ciency of a given algorithm. There are several other models involving<\/p>\n\n\n\n
for example, decision trees, cellular automata, or logical calculus. The most<\/p>\n\n\n\n
practical approach is called the circuit model where elementary logic opera-<\/p>\n\n\n\n
tions are used as building blocks to evaluate the function. It was shown that<\/p>\n\n\n\n
the circuit model was equivalent to the Turing model, so that there is no loss<\/p>\n\n\n\n
in generality in concentrating on this, as we will in most of this book<\/p>\n","protected":false},"excerpt":{"rendered":"
For a long time historically, computation was a matter of actually solving, or \ufb01nding algorithms to solve, various mathematical problems using mechan- ical or other algorithms. It was only in the early twentieth century that the process of computation was modelled in mathematical terms, largely in the works of Alan Turing, Alonso Church, Kurt G\u00a8odel, […]<\/p>\n","protected":false},"author":1,"featured_media":4040,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[495],"tags":[],"class_list":["post-4048","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computation-models-and-computational-complexity"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/download-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4048","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4048"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4048\/revisions"}],"predecessor-version":[{"id":4049,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4048\/revisions\/4049"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4040"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4048"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4048"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4048"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}