Intro

It is an exploration of the inherent properties of algorithms and computation, independent of current technology. This can extend from “what is the best way to multiply two numbers,” to “could we use the effects of quantum entanglement to factor numbers faster.”

Theorems, Lemmas and Claims are “true” statements about concepts we are trying to define. The difference between them is basically their level of importance.

Theorem - Refers to a significant result that we would want to remember and highlight.

Lemma - A technical result that can be helpful in proving theorems but is not particularly important on its own.

Claims - A throwaway statement we may use in order to prove a bigger result, but in an of itself is not very important.

A place-value system for representing numbers or a set of instructions for representing objects as symbols.

A set of instructions for performing operations on data structures/data representations. Examples of algorithms are multiplying and adding numbers.

Specification - What is the task that the algorithm performs? ie. Multiplication.

Implementation - How is the task accomplished, or what sequence of instructions are performed? , The implementation may be the differentiating factor between algorithms. So for example, Karatsuba’s Algorithm and Grade School Multiplication both achieve the same specification of multiplying numbers, but they differ in implementation which makes them separate algorithms.

Analysis - Why does this sequence of instructions achieve the desired task, and, optionally, how performant is this algorithm? This may be described via a proof.

It showcases how algorithms evolve and therefore impact our efficiency and understanding of the world.

Performing an O(n^1.6) efficiency in comparison to grade school multiplication’s O(n^2), essentially what happens is that it takes older algorithm’s deconstructed + abstract form of multiplying two n-digit numbers and reduces it from 4 multiplied terms to 3 terms. This is trivial for small numbers, but becomes significantly better for bigger numbers. To program this algorithm, recursion is necessary.

Basically things that could never happen due to our understanding of the world via laws (ex. the computation laws of nature or the law of conservation of energy.) Due to the supposed impossibility of these things happening or existing, we consider these important as “negative results,” which help us enforce that these laws are correct.

The RSA encryption scheme relies on the conjectured impossibility of efficiently factoring large intergers to ensure security.

A definition is a description of a concept.

An assertion is a “true” statement about a concept we are trying to define. Some examples of assertions are theorems, lemmas and claims.

Proofs are arguments we use to demonstrate that our statements are correct.