The Unreasonable Effectiveness of Mathematics in the Natural Sciences is an article by the famous mathematician Eugene Wigner. (Wigner 1990)

Reflection

What I found most peculiarly interesting is the focus on many mathematical/physics texts on the idea of the “beauty” of the expressions; and, it seems, the clear pleasure that Wigner gets from analyzing the systems with the aforementioned “beauty.”

Setting aside whether or not this beauty is “deserved”/appropriate, I love that my attraction to physics is somewhat similar to what Wigner describes. Under the appropriate conditions, with constraints, it is possible to build a solution to physics problems simply through the evolution of mathematics.

Theory of Computing is a science which attempts to identify “what the most efficient way to solve a given computational task?”

“efficient”

…with respect to what resources?

• time
• space/memory
• randomness
• communication / interaction
• quantum-ness (https://theory.stanford.edu/~abouland/)

“most”

study of impossibilities: lower bounds

For instance, we want a result like “SAT cannot be solved in Polynomial Time” (then in which case P != NP)

history of the theory of computing

computability theory

computability theorists consider themselves to deal with the problem of: “what computational tasks can be solved at all?” We know that because of the halting problem, not everything is solvable. (Turing 1936)

Formal models of computation to have the language and tools:

• what is computation?
• what can and cannot be computed?
• what can and cannot be efficiently computed?

Sidebar: proof

Goal

• basic principles of the theory of computation
• formalize and prove properties of computation
• apply basic principles of computational thinking such as reductions
• exposure to different areas of theory

Questions for Omer

Questions for Omer

Content

Finite Automata

this is a very simple model of computation (a constant amount of memory), meaning we can:

Assuming the Church-Turing thesis holds, there are problems that no computing device can solve.

We can prove this using a counting argument: there are no surjective function from the set of all Turing Machines to the set of all languages over \(\qty {0,1}\).

That is: every mapping from \(TM\) to languages fails to cover some language.

proof

Suppose for contradiction all languages are recognizable, then for all \(L\), there is as truing machine \(M\) recognizing \(L\). Meaning, there’s some surjection \(R: TM \to L\).