Computer Science Blows My Mind
source link: http://twistedoakstudios.com/blog/Post3631_computer-science-blows-my-mind
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Computer Science Blows My Mind
Computer science is an interesting discipline. Often, I find myself inadequately trying to communicate why I find it so fascinating. I think I get the closest when describing computer science things that ‘blow my mind’.
This post is… basically just a list of computer science things I think are cool.
Physical
I remember a time when I was very confused about how computers worked. I knew I could type in a program, and the computer would run it, but how that happened was a big mystery. I could write a program to interpret programs, but… how do I run the interpreter? It can’t be interpreters all the way down!
When I learned how to make an adder out of logic gates, and realized I could pull the same sort of trick all the way up… I imagine that’s how Archimedes felt as he ran through the streets naked after realizing he could measure volume via water displacement.
It sounds a bit silly to say it, but did you know computers run on physics?! Amazing!
Coloring Complexity
Suppose you’re given a map. Your job is to determine if, with a particular number of colors, you can color in all the areas without giving any bordering areas the same color. You don’t have to actually provide such a coloring, just determine if there is one.
How difficult do you think it is to solve this problem? It actually depends on the number of colors.
With 0 or 1 colors, the problem is trivial. Only graphs without nodes are 0-colorable, and only graphs without edges are 1-colorable.
With 2 colors, the problem is easy. You can solve it in linear time. As soon as you pick the color of one area, you’re forced to a single possibility for adjacent areas. Just keep filling in areas as you’re forced to, until you either finish or find a contradiction.
With 3 colors, the problem is very hard. In fact it’s NP-Complete, meaning an algorithm that solves any instance in polynomial time could be repurposed to say… be the first to find inputs that collide when hashed with SHA-1.
With 4 colors, the difficulty changes again. Complicated details aside, you can use the following algorithm to solve the problem:
bool IsFourColorable(PlanarGraph g) {
return true;
}Needless to say, planar 4-colorability is a bit easier than planar 3-colorability.
Over-constrained problems are easy, but so are under-constrained problems. Changing tiny details of problems can massively change how easy they are to solve.
Proofs without Proofs
Suppose you meet an alien with access to absurd amounts of computational power. The alien is cooperative, but you’re not sure if it’s trustworthy. Can the alien help you solve hard computational problems, even though you don’t trust it and it can probably track everything you do? Can Arthur extract useful work out of a tricky Merlin?
Welcome to the wonderful world of interactive proofs.
Want to convince me that you have solved a problem or know some information (e.g. a password), without giving me the solution or the information? You can do it with an interactive zero knowledge proof. For example, most cryptographic voting systems involve voting machines zero-knowledge-proving that they are functioning correctly at every step.
Want to search throughall the different possibilities that could be reached in exponential time, to see if one meets a criteria? All you need is two isolated provers instead of one. No, seriously, MIP (problems solvable in polynomial time with multiple unbounded interactive provers) is equivalent to NEXPTIME (problems that can be solved in exponential time, with access to a ‘branch both ways’ instruction). This is not quite as practical as zero knowledge proofs, but NEXPTIME is so gigantic that I don’t care.
In computer science, the idea of a mathematical proof is one special case amongst many strategies to convince verifiers that something is true.
Secure Multiparty Computation
A common intuition in real time strategy games is that map hacks are unavoidable. The game needs to know where enemy units are in order to determine if they can be seen, and a map hack is just a matter of displaying instead of hiding the information… right? Wrong.
Secure multiparty computation (SMPC) allows mutually distrusting computers to interact in a way that simulates a trusted server. In the case of an RTS game, the simulated server would compute the answers to questions like “What units can see each other?” and then tell the players what they can see. This can be done without any of the players’ computers learning where hidden enemy units are.
Unfortunately, SMPC is quite expensive and requires back-and-forth interaction. It’s not practical to run it over hundreds of unit positions a hundred times a second. It’s more applicable to turn based games like civilizations or poker than to real time strategy games.
Still, the fact that having a real trusted third parties is unnecessary (it’s more like… an optimization) is very cool.
You’ve probably head of the halting problem. Basically, it’s a more concrete version of Gödel’s incompleteness theorem: instead of proving xor disproving every statement, you want to find a program that determines if given programs halt.
It is the case that no program solves the halting problem. This is quite possibly the most actively counter-intuitive thing I know.
For example, you can write a (partial) halting solver that works by enumerating all mathematical proofs until a proof that the program in question halts is found or a proof that the program in question doesn’t halt is found. The only way such a solver can fail is if there are “unfathomable” programs that run forever, with no possible proof even in principle that they run forever. (Alternatively: you used an inconsistent proof system.)
Unfathomable programs exist.
The idea of unfathomable programs breaks my brain. Again and again, I end up with the same confused questions: if there’s no proof the machine doesn’t halt, in what sense does the fact that it doesn’t halt even exist? How does it make any sense to require an infinitely large proof about any aspect of a machine with a finite-sized specification?
Even worse, unfathomable programs are impossible to find. Confirming you had a no-proof-but-runs-forever program would involve proving it ran forever and then proving you didn’t just prove that last thing.
Basically, the halting problem can be used to produce the feeling of confusion-about-reality-itself on demand. It’s just that mind blowing to me.
Summary
Computer science interesting. Craig like.
Discuss on Reddit
7 Responses to “Computer Science Blows My Mind”
Mark says:
If someone claimed to have a black box that solved the Halting Problem, is there an interactive proof they could offer to convince someone of that?
CraigGidney says:
I don’t see any way to do it. We could test the box against programs with known halting/not-halting, we could test if the box solves NP-Complete problems reduced to halting queries, and we could do some measure of testing by just running programs for a really long time and comparing… but none of those allow us to become arbitrarily certain that the box works in the cases that we can’t figure out ourselves.
Jona Christopher Sahnwaldt says:
“Unfathomable programs exist” – no, that hasn’t been proven. What has been proven is this: For every (partial) halting solver S there is a program P such that S cannot decide if P halts or not. Formally:
For all S: Exists P: S can’t decide P. (1)
If I understand you correctly, “unfathomable programs exist” means this: There is a program P such that for every (partial) halting solver S, S cannot decide if P halts or not. Formally:
Exists P: For all S: S can’t decide P. (2)
(2) would imply (1), but (1) doesn’t imply (2), although even many books on Turing, Gödel etc. make this mistake. It can actually be shown that (2) is false.
Maybe this can alleviate some of your confusion-about-reality-itself. 😉
I meant unfathomable relative to ZFC or the human brain or [insert any other computable method of reasoning here].
Of course any given program either halts or doesn’t and a simple “return true” or “return false” technically solves it. In fact, there are solvers of length N+c that solve all programs up to length N: just have the solver use those extra c bits to simulate the program while computing the Nth busy beaver number. If the program has at most N bits and hasn’t halted after Nth-busy-beaver steps, it’s never going to.
But, unless we have access to hypercomputation of some kind, there are possible programs we simply will never be able to definitively analyze.
I’m not sure I understand you correctly. Do you mean that there are programs we can’t analyze because of our limited resources? That’s true, but not unexpected or confusing…
Of course, relative to each well-defined method M (e.g. ZFC), there is an unfathomable program P(M). But I don’t know of any proof that there exists a program P that is unfathomable by all methods. (I don’t think “the human brain” is well-defined, so Turing’s proof doesn’t really apply to it.)
How does the solver of length N+c compute the N-th busy beaver number? I don’t think that’s possible without an oracle.
No, I think there are program that we will never be able to fathom even if we had unlimited computational resources.
The solver doesn’t compute the Nth busy beaver number, it’s hardcoded to contain the program of length N that runs the longest. So it stops working for programs after length N, but nicely solves all the ones up to N (though not particularly quickly) despite only being slightly longer.
I think it’s a misinterpretation of Turing’s proof to say that there are absolutely unfathomable programs. I’m pretty sure it hasn’t been proven that such programs exist. I think they don’t exist, but AFAIK that hasn’t been proven either, so I guess we’ll have to agree to disagree.
To find that solver, you need an oracle for the busy beaver problem, which is equivalent to (has the same Turing degree as) an oracle for the halting problem.
Twisted Oak Studios offers consulting and development on high-tech interactive projects. Check out our portfolio, or Give us a shout if you have anything you think some really rad engineers should help you with.
Archive
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK