An online book by Andy Matuschak and Michael Nielsen.

Presented in a new mnemonic medium which makes it almost effortless to remember what you read.

I think this will be relevant for Mathematical Logic. Also Quantum Physics.

Started reading [[2021-03-06]]

Notes

Through his career, Hilbert was interested in the ultimate limits of mathematical knowledge: what can humans know about mathematics, in principle, and what (if any) parts of mathematics are forever unknowable by humans? Roughly speaking, Hilbert’s 1928 problem asked whether there exists a general algorithm a mathematician can follow which would let them figure out whether any given mathematical statement is provable. Hilbert’s hoped-for algorithm would be a little like the paper-and-pencil algorithm for multiplying two numbers. Except instead of starting with two numbers, you’d start with a mathematical conjecture, and after going through the steps of the algorithm you’d know whether that conjecture was provable. The algorithm might be too time-consuming to use in practice, but if such an algorithm existed, then there would be a sense in which mathematics was knowable, at least in principle.

Attacking Hilbert’s problem forced Turing to make precise exactly what was meant by an algorithm. To do this, Turing described what we now call a Turing machine: a single, universal programmable computing device that Turing argued could perform any algorithm whatsoever.

Turing’s machine became the gold standard: an algorithm was what we could perform on a Turing machine.

Turing machine

Is there a (single) universal computing device which can efficiently simulate any other physical system?

Paraphrased from David Deutsch

In this sense, computers aren’t just human inventions. They are a fundamental feature of the universe, the answer to a simple and profound question about how the universe works.

Underlying every such image is millions of pixels, described by tens of millions of bits. When I move the game controller, I am effectively conducting an orchestra, tens of millions strong, organized through many layers of intermediary ideas, in such a way as to create enjoyment and occasionally sheer delight.

it turns out that all quantum gates can be thought of as matrices, with the matrix entries specifying the exact details of the gate.

Quantum gates are equivalent to matrices, noted isomorphism

The $X$ Gate (NOT)

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

$X$ is its own inverse

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