Strings over Σ

What a decade since I’ve last posted about a paper I read.

Where do you put your unwanted objects?

I’ve been working on system-level software for Linux for some time now, which is a job that makes you much more likely to encounter the odd corner of an operating system than higher level development.

With the unprecedented en vogue1 right now, I have taken the unprecedented step of trying out Emacs after having been a loyal Vim user for years.

DISCLAIMER: Let me say this first.

Hello, I am Florian and you might remember me from posts such as Turing Completeness.

The other day I was asked to take a look at code I had written years ago that basically allowed the user to build up logical formulas while always keeping them in CNF (conjunctive normal form – that is, a logical formula where the outermost connective is…

The subtle difference between incompleteness (of a theory), completeness (of a proof system) and indecidability (of a logical system) are a common source of confusion.

This paper is about detecting a user’s keypresses using the interference the movements of the fingers cause in WiFi signals.

This is one of my pet peeves: I have heard many people describe Turing-complete as “a language you can do everything with”.

It has been a long time since I last posted one of those, apologies!

I recently got the book What is the Name of this Book?

For some reason that is not completely clear to me either, I decided to go about and implement the sequent calculus technique for theorem proving this weekend.

Even though week-ish is an intentionally vague concept, I should apologize for this week-ish to take particularly long.

The paper in question covers something that I have been meaning to read up for months: the arithmetical hierarchy, which was sadly not covered in the university courses I have attended.

This paper was more discovered than chosen.

I have been meaning to read this paper for quite some time, but for some reason, even though its entire point is proposing an understandable consensus algorithm, Paxos’ (the canonical consensus algorithm previous to this paper) reputation for being imposs…

Looking around for papers to cover in this series, I remember a talk about folding algorithms one Erik Demaine gave at my former university as the annual Vienna Gödel Lecture, where once a year major contributors to the field of computer science (other gu…

So, I feel like cheating a bit again as this paper is only three pages long, but I guess it is an ACM Turing Award lecture paper, so it deserves a spot here, at least for historical significance.

First of all, sorry for the delay!