Articles in the Computer Science category

The universal algorithm and the Busy Beaver problem

There is an algorithm that can, at least in theory, and in likelihood, at most in theory, solve any problem, calculate the meaning of life, or simulate the universe even …

Hamiltonian Cycle hardness and gadgets

One of my preferred types of NP hardness proofs involves gadgets. Some publications prefer the more general terminology components, but I’ll use the former. Gadget-based proofs, with the proper …

Pseudo-polynomial computational complexity

Exploring the definition and implications of pseudo-polynomial asymptotic time complexity.

The ever common Knapsack problem

We encounter the Knapsack problem all the time. Given a set of items, each of a specific size and value, is it possible to fill a limited size knapsack with …

Fun with self-referential paradoxes and the halting problem

I want to explore a set of paradoxes that arise from self-referential problem formulations. I will then proceed to present the paradox in a more formal setting of computability theory …

About Lisp and programming languages

How Lisp re-sparked academic excitement in a programming language.

Kultur und Informatik 2018

I attended the 16th annual Culture and Computer Science conference in Berlin, organized in Schloss Köpenick, a beautiful art museum setting along a river. The smaller conference focuses on the …

Space vs Time

On space complexity with respect to time, and their trade-offs.

Subset Sum problem NP-hardness proof

I never expected to dedicate a casual blog entry to a hardness proof, especially one fairly academic as this. However, the nature of it evokes certain elegance beyond what I …

On Computational Complexity

I want to highlight the branch of Theoretical Computer Science concerned with classifying algorithmic complexity. Similar to the previous post on computability, this serves as a more philosophical complement to …

About Computability and Turing Machines

On the beauty, simplicity and utility of a Turing Machine.