Community

Better dead than bored. #opensource #boardgames #music

Activity

project activity

My Covid-19 quarantine plan for the last 12 months was to write code every day. With a few exceptions, I pulled that off. The big pre-Covid plan was to write every day, but in traditional hacker fashion I first built some tools (Ktistec and kin).

The big project was Ktistec, of course, but early on I spent a lot of time on MXNet.cr, mostly on native MXNet bindings, but also on a Gluon compatible library. I also put a lot of time into Ishi, a project that sprang from my desire to visualize MXNet output inside of my iTerm console.

Now, to do some writing...

#ktistec #mxnet #ishi

I recently stumbled across Scott Aaronson's lecture notes for PHYS771 Quantum Computing Since Democritus. (I haven't yet read the book.)

Scott Aaronson is a computational complexity researcher/thinker first and foremost, and I love his particular style/peculiar style. En route to quantum computing, he talks a lot about computational complexity, reflects on free will, and manages to loop in time travel, as he does. But the notes (and presumably the book) are not a primer on quantum computing (which was what I was looking for).

The questions Scott’s trying to answer are, generally, what kind of problems can you solve with quantum computing, and, specifically, will we be able to solve NP complete problems in polynomial time with quantum computing. These are very important questions, because Shor’s algorithm (a quantum algorithm) can factor integer primes in polynomial time, which threatens to reduce the effectiveness of a lot of the cryptography on which we all depend. So there are real world consequences.

Factoring integer primes is in NP but it's not known/believed to be NP complete, but if a polynomial time algorithm is discovered for a known NP complete problem, like the traveling salesperson problem, an entire class of difficult problems becomes very much easier to solve, because a solution for one NP complete problem is a solution for any NP complete problem.

How much easier? For reasonably large problems it's the difference between solvable and solvable but not in the lifetime of the universe, because the only known algorithm amounts to trying every possible solution.

#complexity #quantum-computing #review

i came across supertasks while reading “bangs crunches whimpers and shrieks” by john earman.

a supertask is an infinite sequence of tasks that occur within a finite amount of time. how do you fit an infinite number of tasks into a finite interval? assume a one second interval. perform the first  task at time 0.5 seconds, the next at time 0.75 seconds, the next at time 0.875 seconds, and so on—always dividing the remaining time in half. mathematically, you’ll end up with an infinite number of tasks in a one second interval.

zeno's paradox articulates a supertask—the task being to cover half the previous distance at each step. luckily, evidence refutes zeno's assertion that motion is an illusion.

other supertasks are not so easily analyzed. the thomson's lamp puzzle toggles a lamp on or off at each step and asks if the lamp is on or off at the end of the interval. it must be one or the other, right?

imo, a supertask feels a bit like finishing a software project. call it the generalization of the 80/20 rule.

#supertask #software