Ciro Santilli $$ Sponsor Ciro $$ 中国独裁统治 China Dictatorship 新疆改造中心、六四事件、法轮功、郝海东、709大抓捕、2015巴拿马文件 邓家贵、低端人口、西藏骚乱
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: 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.
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.
Coolest ones besides the obvious boring halting problem:
One of the most simple to state undecidable problems.
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!).
TODO had seen a good table on Wikipedia with an expanded hierarchy, but lost it!
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.
is the largest number of 1's written by a halting -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.
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 , we would be able to prove those conjectures automatically, by letting the machine run up to , and if it hadn't halted by then, we would know that it would never halt.
Of course, in practice, 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?
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:
More commonly known as a map or dictionary.
Like breadth-first search, this also has the property of visiting parents before any children.
This is the easiest one to do iteratively:
  • pop and visit
  • push right to stack
  • push left to stack
Only makes sense for binary tree because if there are more nodes it is not clear what the top node should go in the middle of.
This is unlike pre-order depth-first search and post-order depth-first search which generalize obviously to general trees.
This is a bit harder than interative pre-order: now we have to check if there is a left or right element or not:
  • (START) push current
  • if there is left:
    • move left
  • else:
    • (ELSE) pop
    • visit
    • if there is right
      • move right
      • GOTO START
    • else:
      • GOTO ELSE
The control flow can be slightly simplified if we allow NULLs:
Post-order depth-first search (LRN)
split toc "Depth-first search" words: 19
Has the property of visiting all children before the parent.
Interative post-order
split toc "Post-order depth-first search" words: 9
This is the hardest one to do iteratively.
Interative post-order with two stacks
split toc "Interative post-order"
Interative post-order with one stack
split toc "Interative post-order"
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:
  • . For , is enough. Otherwise, any will do, the bottom line will always catch up to the top one eventually.
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 , and little-o notation means .
  • K does not tend to zero
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:
  • P: would be boring on quantum computer
  • NP-complete: would likely be impossible on a quantum computer
Heck, we know nothing about this class yet related to non quantum classes!
  • conjectured not to intersect with NP-complete, because if it were, all NP-complete problems could be solved efficiently on quantum computers, and none has been found so far as of 2020.
  • conjectured to be larger than P, but we don't have a single algorithm provenly there:
    • it is believed that the NP complete ones can't be solved
    • if they were neither NP-complete nor P, it would imply P != NP
  • we just don't know if it is even contained inside NP!
The exact same problem appears over and over, e.g.:
  • transportaion: the last mile of the trip when everyone leaves the train and goes to their different respective offices is the most expensive
  • telecommunications: the last mile of wire linking local hubs to actual homes is the most expensive
  • electrical grid: same as telecommunications
Ciro Santilli also identified knowledge version of this problem: the missing link between basic and advanced.
The function being maximized in a optimization problem.