computation for cognitive scientists

Turing machine

The Wikipedia article on Alan Turing provides useful background information and pointers to other sites. Also well-worth looking at is the Turing Archive.

The Wikipedia article on mathematical induction is worth looking at, especially if you haven't done any proofs by induction for a while. In particular, note that it has a discussion of variants on the basic mathematical induction format.

Here's a nice little Turing machine simulator which uses almost the same notation as we introduced in Lecture 3. You can use it to test your own Turing machines, or you can step through some of the example machines they have.

And here's a Turing machine demo. It's not as flexible as the previous one, but it does show the graphical representation (not just the states and the tape contents) which is nice. Play with it! It won't take long and you'll learn something.

The Wikipedia article on the Busy Beaver Problem is also useful.

And here's a poetic proof that the Halting Problem is undecidable.

The Wikipedia article on mathematical induction is worth looking at, especially if you haven't done any proofs by induction for a while. In particular, note that it has a discussion of variants on the basic mathematical induction format.

Here's a nice little Turing machine simulator which uses almost the same notation as we introduced in Lecture 3. You can use it to test your own Turing machines, or you can step through some of the example machines they have.

And here's a Turing machine demo. It's not as flexible as the previous one, but it does show the graphical representation (not just the states and the tape contents) which is nice. Play with it! It won't take long and you'll learn something.

The Wikipedia article on the Busy Beaver Problem is also useful.

And here's a poetic proof that the Halting Problem is undecidable.

All rights reserved. Patrick Blackburn 2011

✕