Month: August 2013

Hackers & Painters: Big Ideas from the Computer Age

I’ve just completed a book, Hackers & Painters: Big Ideas from the Computer Age by Paul Graham.

I thought it was very articulate, it feels like he is giving a talk, so it was easy to follow and understand. It’s a relatively non-computer-science friendly, though some parts of the book were rather technical. The chapters didn’t necessarily follow one another, so each chapter felt like reading a separate essay. As a result, the book overall didn’t flow well. Individual chapters reads great, each with its introductions, arguments, and takeaways.

Several things in the book that caught my attention:
Continue reading Hackers & Painters: Big Ideas from the Computer Age

Interesting Consequences of Undecidability

In the book Introduction to Automata Theory — Languages and Computation. The following paragraph is interesting:
av

What this means is that if we were given a source code of a program, we would be unable to decide what the program does. Only lexical or syntactical properties of the program may be decided. This is interesting because it’s really counter-intuitive! You’d think that given the source code and read through it we can systemically figure out what it does. Not true. This means is that another program, B, cannot figure out what program A does.

Interestingly enough, this implies that no anti-virus will ever be totally effective, or any other types code detection software, because it is undecidable what a program does. There will always exist programs which can’t be detected. I knew this when I was young, from the fact that AV programs always update their virus databases, so naturally that meant there was no systemic way to detect mischievous programs. I wondered if the updates would ever stop in the future. Now I know this will never happen because of this consequence of undecidability.