Computing with Tiles

moyix

Everyone “knows” what a computer is, and has some sense of what it means to carry out a computation. Making this notion precise was left to Alonzo Church and Alan Turing, who in 1936 and 1937 independently developed a rigorous logical definition of what it meant for something to be “computable”. Although their constructions were very different (Turing’s a simple machine, Church’s a calculus of functions), they capture precisely the same notion, and anything expressible in one can be expressed in the other.

Today, I’d like to give an intuitive sense of just how universal the idea of computation is, and separate it from the physical machines you’re using to read this post. To do this, I’m going to explore a way of computing that may seem strange or impossible or, at the very least, impractical at first: I’ll show that you can compute anything a Turing machine…

View original post 2,242 more words

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s