Continuations

In theory there is no difference between theory and practice. In practice there is. - Yogi Berra Yoga works. Meditation works. Conscious breathing works. By “works” I mean that these practices have positive effects for people who observe them. They can help build and retain strength and flexibility of both body and mind. The fact that they work shouldn’t be entirely surprising, given that these practices have been developed over thousands of years through trial and error by millions of people...

So far in the Tech Tuesday series on the theory of computation we have learned about Finite State Machines and their limitations, as well as the more general relationship between automata and languages. As a reminder, an automaton is a model of computation and the reason to have such models is so we can apply formal reasoning to them. Today I will introduce an automaton known as a Turing machine after the amazing Alan Turing who dreamed up this model of computation in the 1930s. The easiest w...

Last Tech Tuesday, we looked at complexity classes which group problems by their intrinsic difficult. There we encountered one of the great unsolved questions of Computer Science. Is P = NP? The class P is easy to define. It is the set of all problems that can be solved by a Turing machine in polynomial time, i.e O(n^k) for some k. So you might think that NP stands for non-polynomial time but you’d be wrong. Instead the class NP has the same definition as P except for a non-deterministic Turi...

In the last two Tech Tuesdays, I introduced the topic of computational complexity. Today as promised I want to dig a bit deeper into the question of best, average and worst case complexity. The canonical example used for this is sorting. For simplicity we will assume that we are sorting a list of numbers. Several different sorting algorithms have been developed over the years that go by fun names such as Insertion Sort, Quicksort and even Bubble Sort (here is a past Tech Tuesday three-part in...

Last year’s Tech Tuesday ended with a first look at computational complexity. We saw how crazily long a brute force attempt to find a 40 character string would take. This was the result of exponential growth in the runtime of our algorithm. Today we will start to dig a bit deeper. Let’s consider a very common problem: checking whether a word is part of a group of words. For instance, if you use the “find on page” feature in your browser you can check if this page contains the word “freezing” ...

Last Tech Tuesday, I presented the idea of a Finite State Machine (FSM) using a Nespresso machine as an example. We saw that what makes an FSM attractive is that we can easily analyze it using formal methods and answer such questions as to whether a particular state is ever reached or how long a computation by the machine will take. I also suggested though that this ability came at a price and today I want to explain that further. To do that let’s start by looking at a common computer problem...

So far in the Tech Tuesday series on the theory of computer science we have covered questions of computability. We have looked at ways of formalizing computation through abstract machines such as the Finite State Machine and the Turing Machine to explore limits on what can be computed at all. We saw with the Halting Problem that the power to compute lots of things is gained at the cost of not being able to say much about the computation (e.g. will it stop?). Now we will turn our attention to ...

Last Tech Tuesday as part of my series on the theory of computation I introduced the Turing Machine. Just to refresh your memory, the Turing Machine is essentially a Finite State Machine connected to an infinite tape for storage. And now, drum roll, here is Alan Turing’s amazing intellectual breakthrough: he showed that it is possible to construct a single Universal Turing Machine that will simulate any other Turing Machine! Let me explain. What a particular Turing Machine does is defined by ...

In the last two Tech Tuesdays, I introduced Finite State Machines (FSM) and showed examples of both their usefulness and their limitation. Just as a reminder, we study computer science theory to get a handle on two fundamental questions: what can be computed at all (computability)? And, how hard is it to compute something that can be computed (complexity)? The upshot on FSM is that they cannot compute a whole lot but what they can they do very efficiently. Let me flush both parts of that asse...

As promised (threatened?) Tech Tuesday is embarking on a look at the theoretical side of computer science. We also call this the theory of computation and it deals with two big questions: first, what are the limits to computation (known as computability) and second, how efficiently can we compute things (known as computational complexity). Now in order to be able to make formal arguments in trying to answer these questions it helps a lot to have models of computation that are simpler and more...