# Classical Models of Computation

## The Turing Machine

The Turing machine is a theoretical computer, originally proposed by Allan Turing. It can compute anything that is possible on a classical system.

It includes a *finite state machine,* a machine which has a finite number of possible states, and whose current state relies on the previous state. So if I put in the number 4 now, and the number 4 again next, the results may be different because the current answer depends on the previous result and well as my input.

It's also a *tape* machine. It has an infinite rope of tape that it can read from or write on, but the important thing about the tape is that it can only input *one instruction at a time*. Because the machine includes a finite state machine, the state changes *every time* a new instruction is read in [*(Kaye, P - p. 3)*](/learning-quantum/quantum-circuits/quantum-circuit-summary/quantum-circuit-references.md#the-turing-machine).

## The Circuit Model

The Turing machine is the most abstract idea of a computer. We never talk about storage, or time, or wires - only instructions and state. We'll move a bit closer to real life in our discussion of the circuit model of computation.

In the circuit model we have a given number of wires, along which travels a current. As we talked about earlier [*high voltage corresponds to 1 and low voltage corresponds to 0*](/learning-quantum/qubits/classical-bits.md#yes-no). Along the path of this wire is some kind of *logic gate* which affects some change of state on the system [*(Kaye, P - p. 3)*](/learning-quantum/quantum-circuits/quantum-circuit-summary/quantum-circuit-references.md#a-circuit-diagram)*:*

![A circuit diagram](/files/-M2vNK-kUtHPcIsEkm4N)

You see here on the left a series of inputs, labelled $$i\_1 - i\_4$$. On the right we have a series of outputs labelled $$o\_1 - o\_4$$. In the middle we have a few gates, labelled $$G\_1 - G\_4$$. Some of the gates take in multiple outputs, and produce multiple outputs.

### Using Gates

A logic gate is an [*operator*](/learning-quantum/linear-algebra/transformations.md#operators) that[ *transforms*](/learning-quantum/linear-algebra/transformations.md#transformation-matrices) the input into some output. These may preform [*fundamental boolean operations*](/learning-quantum/qubits/classical-bits.md#boolean-operations) or more complex instructions.

For example, the [*transformation matrix*](/learning-quantum/linear-algebra/transformations.md#transformation-matrices) for a NOT gate looks like this:

$$
\text{NOT}=\begin{bmatrix}0&1\1&0\end{bmatrix}
$$

Let's do an example. We'll start by defining the matrices for our classical bits:

$$
0=\begin{bmatrix}1\0\end{bmatrix}, \hspace{6pt} 1=\begin{bmatrix}0\1\end{bmatrix}
$$

Looks familiar I'm sure. We'll multiply the 0 vector by the NOT transformation matrix:

$$
\begin{bmatrix}0&1\1&0\end{bmatrix}\begin{bmatrix}1\0\end{bmatrix}=\begin{bmatrix}0\1\end{bmatrix}
$$

You can see that the result is the 1 matrix.

Classical gates are flexible. We can take multiple bits as input, and we can produce multiple bits as output. We can combine them and use them to construct larger and more complex operations.

{% hint style="info" %}
[More information on classical logic gates](https://www.khanacademy.org/computing/ap-computer-science-principles/computers-101/logic-gates-and-circuits/a/logic-gates)
{% endhint %}

### Universal Gates

We can also define *universal gates* - gates which can be used to define all other gate operations. For example the NAND gate (NOT/AND) is an example of a universal gate.

{% hint style="info" %}
[More about universal gates](https://www.electronics-tutorials.ws/logic/universal-gates.html)
{% endhint %}

## Classical Systems and Information

During this entire tutorial, we've focused heavily on *information*.

How is information represented? How is information processed? How is information preserved? How is information changed?

We can see that in both these models of computation, information can be destroyed. The original state of the wire may not be retrievable after certain gate operations. We've gained something, but we've also lost something.

Quantum mechanics doesn't allow for this possibility. All information must be preserved. This means all of our quantum operations must be *reversible*.


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://lewisla.gitbook.io/learning-quantum/quantum-circuits/classical-models-of-computation.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.