Tag Archives: computation

Introduction to Computational Theory: Areas of Research

Posted on by

A Turing MachineIn my last post I started explaining the theory of computation, starting with its central principle: The Church-Turing Thesis. In this post, I’m going to explain several areas of research in computational theory that, as per the Church-Turing Thesis, are based on the realization that all (full featured) computers are equivalent.

Turing Machines as Simplified Computers

Since Turing Machines are known to be equivalent in expressive power to modern computers, it turns out this means that Turing Machines can serve as a very simplified version of a modern computer — or any conceivable computer!

This makes Turing Machines quite useful for exploration of the Theory of Computation. Mathematicians have been able to come up with ‘programs’ written for Turing machines and then – because Turing Machines are so simple – come up with consistent ways of how to measure how fast the program runs given any number of inputs. Continue reading →

An Introduction to the Theory of Computation: The Church-Turing Thesis

Posted on by

A Turing MachineOne scientific/philosophical point that all three of my favourite authors loved to delve into was Computational Theory and, in particular, something called “The Church-Turing Thesis” and it’s related thesis: The Turing Principle [1]

I remember, back when I was working on my computer science degree, studying about Turing machines and the Church-Turing Thesis in my Intro to Computational Theory class. Back then I thought it was a big waste of time. I just wanted to program computers and I could care less about this long dead Turing-guy (or this Church-guy) nor his stupid theoretical machines.

Now that I understand the philosophical ramifications of the Church-Turing Thesis, I wish I had paid attention in class!  Because the Church-Turing Thesis, if true, has some profound philosophical ramifications and it might also tell us something about the deep — and special — nature of reality.

In a series of posts I will attempt to do a short summary of Computational Theory. This serves as the basis for many other topics to come, so it will be nice to have a series of posts I can easily reference back to. (I’ll also do a summary at the end if I get that far.) I’ll do my best to make it as easy as possible and as interesting as possible. But if this just isn’t your cup of tea, you may need to move on or just skim it for general ideas or wait for the quick summary. [2] Continue reading →