## 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 through*all* 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.

### Halt

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”

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

- strilanc
- What Quantum Computers Do Faster, with Caveats
- Naming Things: Fail-Useful
- Detecting Simple Cycles Forming, Faster
- Third Party Bit Commitment
- Angular Velocity is Simple
- Collection Equality is Hard
- Deadlocks in Practice: Don’t Hold Locks While Notifying
- Brute Force Parallelization
- A Year’s Worth of Opinions about Objective-C
- Referencing Substrings Faster, without Leaking Memory
- Not Crying Over Old Code
- Exploring Universal Ternary Gates
- Impractical Experiments #2: Securing Peer to Peer Fog of War against Map Hacks
- Achieving Exponential Slowdown by Enumerating Twice
- Using Immortality to Kill Accidental Callback Cycles
- Cancellation Tokens (and Collapsing Futures) for Objective-C
- Visualizing the Eigenvectors of a Rotation
- Collapsing Futures in Objective-C
- Bug Hunting #1: Garbled Audio from End to End
- Impractical Experiments #1: Representing Numbers as Polynomials
- Implementing Quantum Pseudo-Telepathy
- Turn On Your Damn Warnings
- Big-O Made Trivial
- Unfathomable Bugs #7: The Broken Oven
- Solomonoff’s Mad Scientist
- Yearly Blogging Roundup #1
- What isn’t a Monad
- Searching a Sorted Matrix Faster
- How to Read Nested Ternary Operators
- Making Sublime Text 2 Jump to the Correct Line with Unity on OS X
- My Bug, My Bad #4: Reading Concurrently
- Whole API Testing with Reflection
- Optimizing a Parser Combinator into a memcpy
- Don’t Treat Paths Like Strings
- Breaking a Toy Hash Function
- Counting Iterators Lazily
- Unfathomable Bugs #6: Pretend Precision
- My Bug, My Bad #3: Accidentally Attacking WarCraft 3
- Collapsing Types vs Monads (followup)
- Collapsing Futures: Easy to Use, Hard to Represent
- Eventual Exceptions vs Programming in a Minimal Functional Style
- The Mystery of Flunf
- Explain it like I’m Five: The Socialist Millionaire Problem and Secure Multi-Party Computation
- Computer Science Blows My Mind
- A visit to Execution Labs in Montréal
- Transmuting Dice, Conserving Entropy
- Rule of Thumb: Ask for the Clock
- Rule of Thumb: Use Purposefully Weakened Methods
- Rule of thumb: Preconditions Should be Checked Explicitly
- Intersecting Linked Lists Faster
- Mouse Path Smoothing for Jack Lumber
- My Bug, My Bad #2: Sunk by Float
- Repeat Yourself Differently
- Grover’s Quantum Search Algorithm
- Followup to Non-Nullable Types vs C#
- Optimizing Just in Time with Expression Trees
- When One-Way Latency Doesn’t Matter
- Determining exactly if/when/where a moving line intersected a moving point
- Emulating Actors in C# with Async/Await
- Making an immutable queue with guaranteed constant time operations
- Improving Checked Exceptions
- Perishable Collections: The Benefits of Removal-by-Lifetime
- Decoupling shared control
- Decoupling inlined UI code
- Linq to Collections: Beyond IEnumerable<T>
- Publish your .Net library as a NuGet package
- When null is not enough: an option type for C#
- Unfathomable Bugs #5: Readonly or not
- Minkowski sums: examples
- My Bug, My Bad #1: Fractal Spheres
- Working around the brittle UI Virtualization in Windows 8
- Encapsulating Angles
- Unfathomable Bugs #4: Keys that aren’t
- How would I even use a monad (in C#)?
- Useful/Interesting Methods #1: Observable.WhenEach
- Unfathomable Bugs #3: Stringing you along
- Anonymous Implementation Classes – A Design Pattern for C#
- Tasks for ActionScript 3 – Improving on Event-Driven Programming
- Minkowski sums and differences
- Non-Nullable Types vs C#: Fixing the Billion Dollar Mistake
- Unfathomable Bugs #2: Slashing Out
- Script templates and base classes
- Unity font extraction
- Abusing “Phantom Types” to Encode List Lengths Into Their Type
- Constructive Criticism of the Reactive Extensions API
- Quaternions part 3
- Quaternions part 2
- Quaternions part 1
- Unfathomable Bugs #1: You can have things! You can have things IN things! You can have …
- Coroutines – More than you want to know
- Asset Bundle Helper
- The Visual Studio goes away
- .Net’s time traveling StopWatch
- Introducing Catalyst

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?

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.

“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.