Computer science

A branch of mathematics that attempts to prove stuff about computers.

Unfortunately, all software engineers already know the answer to the useful theorems though (except perhaps notably for cryptography), e.g. all programmers obviously know that iehter P != NP or that this is unprovable or some other "for all practical purposes practice P != NP", even though they don't have proof.

And 99% of their time, software engineers are not dealing with mathematically formulatable problems anyways, which is sad.

The only useful "computer science" subset every programmer ever needs to know is:

Funnily, due to the formalization of mathematics, mathematics can be seen as a branch of computer science, just like computer science can be seen as a branch of Mathematics!

The dominating model of a computer.

The model is extremely simple, but has been proven to be able to solve all the problems that any reasonable computer model can solve, thus its adoption as the "default model".

The smallest known Turing machine that cannot be proven to halt or not as of 2019 is 7,918-states: www.scottaaronson.com/blog/?p=2725. Shtetl-Optimized by Scott Aaronson is just the best website.

A bunch of non-reasonable-looking computers have also been proven to be Turing complete for fun, e.g. Magic: The Gathering.

A Turing machine that simulates another Turing machine/input pair that has been encoded as a string.

In other words: an emulator!

The concept is fundamental to state several key results in computer science, notably the halting problem.

A computer model that is as powerful as the most powerful computer model we have: Turing machine!

There is a Turing machine that halts for every member of the language with the answer yes, but does not necessarily halt for non-members.

Non-examples: cs.stackexchange.com/questions/52503/non-recursively-enumerable-languages

Subset of recursively enumerable language as explained at: difference between recursive language and recursively enumerable language.

Set of all decision problems solvable by a Turing machine, i.e. that decide if a string belongs to a recursive language.

Is a decision problem of determining if something belongs to a non-recursive language.

Or in other words: there is no Turing machine that always halts for every input with the yes/no output.

Every undecidable problem must obviously have an infinite number of "possibilities of stuff you can try": if there is only a finite number, then you can brute-force it.

Some undecidable problems are of recursively enumerable language, e.g. the halting problem.

Lists of undecidable problems.

Coolest ones besides the obvious boring halting problem:

One of the most simple to state undecidable problems.

The reason that it is undecidable is that you can repeat each matrix any number of times, so there isn't a finite number of possibilities to check.

A:

There are only boring exampes of taking an uncomputable language and converting it into a number?

Same as recursive language but in the context of the integers.

This is the classic result of formal language theory, but there is too much slack between context free and context sensitive, which is PSPACE (larger than NP!).

By Noam Chomsky.

TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!

The list: complexityzoo.uwaterloo.ca/Complexity_Zoo

Computational problem where the solution is either yes or no.

When there are more than two possible answers, it is called a function problem.

Decision problems come up often in computer science because many important problems are often stated in terms of "decide if a given string belongs to given formal language".

The canonical undecidable problem.

A problem that has more than two possible yes/no outputs.

It is therefore a generalization of a decision problem.

$BB(n)$ is the largest number of 1's written by a halting $n$-state Turing machine.

Some variant definitions define it as the number of time steps taken by the machine instead. Wikipedia talks about their relationship, but no patience right now.

Overviews:

This problem is theoretically interesting because many important mathematical conjectures have been proved to be equivalent to whether a given Turing machine halts or not, this is notably the case for:

Therefore, if we were able to compute $BB(n)$, we would be able to prove those conjectures automatically, by letting the machine run up to $BB(n)$, and if it hadn't halted by then, we would know that it would never halt.

Of course, in practice, $BB$ is generally uncomputable, so we will never know it. And furthermore, even if it were, it would take a lot longer than the age of the universe to compute any of it, so it would be useless.

However, philosophically speaking at least, the number of states of the equivalent Turing machine gives us a philosophical idea of the complexity of the problem.

Complexity: NP-intermediate as of 2020:

The basis of RSA: RSA. But not proved NP-complete, which leads to:

This is natural question because both integer factorization and discrete logarithm are the basis for the most popular public-key cryptography systems as of 2020 (RSA and Diffie-Hellman key exchange respectively), and both are NP-intermediate. Why not use something more provenly hard?

Logarithm of a discrete groups.

NP-intermediate as of 2020 for similar reasons as integer factorization.

A solution to a computational problem!

Draft by Ciro Santilli with cross language input/output test cases: github.com/cirosantilli/algorithm-cheat

By others:

More commonly known as a map or dictionary.

This is a family of notations related to the big O notation. A good mnemonic summary of all notations would be:

Module bound above, possibly multiplied by a constant: is defined as:

E.g.:

Stronger version of the big O notation, basically means that ratio goes to zero. In big O notation, the ratio does not need to go to zero.

So in informal terms, big O notation means $\le$, and little-o notation means $<$.

E.g.:

Strictly speaking, only defined for decision problems: cs.stackexchange.com/questions/9664/is-it-necessary-for-np-problems-to-be-decision-problems/128702#128702

A problem that is both NP and NP-hard.

Interesting because of the Cook-Levin theorem: if only a single NP-complete problem were in P, then all NP-complete problems would also be P!

We all know the answer for this: either false or independent.

A problem such that all NP problems can be reduced in polynomial time to it.

This is the most interesting class of problems for BQP as we haven't proven that they are neither:

Big list: cstheory.stackexchange.com/questions/79/problems-between-p-and-npc/460#460

P for quantum computing!

Heck, we know nothing about this class yet related to non quantum classes!

The exact same problem appears over and over, e.g.:

Ciro Santilli also identified knowledge version of this problem: the missing link between basic and advanced.

The function being maximized in a optimization problem.

It is cool how even for such a "simple looking" problem, we were still unable to prove optimality as of 2020.

Applications: