You are viewing mnemosynosis

me2009

Teaching Turing Machines

It can be hard to convey the beauty, simplicity and profundity of Turing Machines to introductory cognitive science students who frequently have no background (or interest) in mathematics, logic or philosophy. Today I demonstrated a Turing Machine using students to act out the various parts.

The demonstration function was 2 + 1 = 3

I lined up nine students in front of the class to be the 'tape' and one student in front to be the 'machine head'.



The Tape

Each student on the 'tape' represented either a 1 or a 0 and stood in the following pattern

...000110000...

- '1s' stood facing the class and each represented the number '1'
- '0s' stood with their backs to the class and represented the space between numbers.

The Machine Head

The 'machine head' student started in state A. State A was visually represented by the 'superman pose' (hands on hips, looking triumphant).

When the machine head switched to state B, she put her hands by her sides.

In order to 'write' on the tape, she used her hands to mechanically turn the pertinent 'tape' student around 180 degrees so that he or she now represented a 0 or 1 respectively.

After a few minutes demonstrating the machine head's repertoire of possible actions, I positioned the machine head to the far right and gave the class the following rules to solve 2 + 1 = 3

The Instructions*

1. If the machine is in state A, and reads a 0, then it stays in state A, writes a 0, and moves one square to the right.

2. If the machine is in state A, and reads a 1, then it changes to state B, writes a 1, and moves one square to the right.

3. If the machine is in state B, and reads a 0, then it changes to state A, writes a 1 and stops.

4. If the machine is in state B, and reads a 1, then it stays in state B, writes a 1, and moves one square to the right.

The Output*



Students calculated 2 + 1 = 3 using instructions 1 through 4. Each output on the 'tape' is represented by steps (i) through (vii) represented in the diagram above. The final output was:

...001110000...

Which meant three students faced the class and the machine head stood in superman pose at a halt.

Students seemed to have fun and I hope they got a better understanding of Turing Machines by acting them out physically than simply reading about them in a book.

* Instructions and output from Crane, T. (2003) Computers and Thought. The Mechanical Mind, Ch.3, 94-95.

Comments

You rock so much for this.:D
Thank you. :D It was so much fun. I wish I did more computation with them. Writing Minsky's 1967 Universal Turing machine would be a great youtube video. I could attach the label 'we are computer' on it or some such.
Oh wow, very cool!
An interactive demonstration such as this wins hands-down over reading about it on paper. The theory/description of Turing Machines are so kinetic that it makes so much more sense to have it presented physically. And, taking part in the demo gets everyone involved, which adds interest aids memory-retention.
It' a lot to take-in at once unless (even if?) you have a background in maths/computing -- there's binary representation of numbers, binary addition, the concept of machine instructions, an instruction pipeline, etc.
And that's before you get to the profound beauty of the algorithms underpinning the Turing Machine and can advance to stuff like Turing Completeness, see the effect Turing himself had on the history of computing, logic/maths, electronics, patents, the war, ciphers, and so on.
I think this is one of those lectures/lessons they'll remember, and I hope it encourages some of your students to dig deeper. :)
Thank you. :)
That is an extremely cool approach.
Interpretive dance wins again! :)
I have shown you this, right? Skip the professor at the start and go to the students on the oval. This is where it all ends, you know. Soon you'll build computers that will take the MCG to stage..


THAT is what teaching should be. Way to go!
Thank you! :)

hi

You have a very interestin aproach.I guess your students understood very well what you have tried to teach them.I guess there should be more people who have new ways of teaching.Cloud Computing Security

Electronic Resources

This is an excellent idea.

If you're interested, I have a collection of flash-based Turing machines that I wrote a few years ago when I was working on a FIPSE grant at Wash U, including a universal machine. They are collected at http://inquiry.mcdaniel.edu/turing/. Feel free to use them, just attribute credit.

That page contains links to the prose explanation that wraps these for both the Inquiry Project (WashU / UCSD) and the Mind Project (ISU). It's in need of updating.

Re: Electronic Resources

Thanks Peter. It's nice to have you on my blog. I'm quite humbled by your flash-based Turing machines. They would have taken a *lot* longer than my hand-scribbled schematics for class!!

I'll pass your work onto my students.

Cheers,
Kate

Re: Electronic Resources

Hey - that's what US Department of Education grants are for!
But seriously, I think that your technique of actually getting the students moving probably taps into their episodic memory in a way that no amount of playing with pixels can.
I did something similar when teaching basic net concepts to a group of people. I had them form a network of computers; lines of people branching out at some points. I then sent "packets" through the network: pieces of paper with simple maths puzzles on them. They had an address on them (someone's name) and a return address. People passed them down the lines as would a network of computers. It only took a few minutes and people had lots of fun.

Stuff like this is always fantastic: it wakes people up and engages them at the beginning of a session and gives a visual and dynamic model that people can relate to.

Great way to teach this beautiful concept.

Great way of teaching!!

I was extremely excited reading this and was compelled to give the below observations(I hope you dont mind).

1. I presume when you say in ur instructions

"and moves one square to the right"

you are indicating the tape (the nine lined up students) moves to the right. So did all the students kind of move to the right? That would have been really cool.

2. Why did you need nine students? I think you should have used only 8 students. As per Crane's book the seperator is "000" and you have the number 2 which is "11" flanked both sides with "000". That makes it eight students. Though an additional '0' doesnt matter there would have been a consistency in punctuation if 3 0s were used both sides.

3. The operation you demonstrated was addition of "1" to any number or in other words "the next number" operation. So given any number represented by consecutive ones (2 is "11" or 3 is "111") in the tape flanked by "000", with these instructions you could increment it by 1. Was that communicated? This means you could using the same dance routine incremented 3 or 4 and did you do that?

4. This dance routine could be extended for unary addition - http://www.mhuffman.com/notes/turing/unaryadd.htm. In this case our "machine head quarterback" has five states - hand up, left, right, down, front -- may be.. :)

Once again my comments might have been superfluous or even wrong - I hope you didnt mind. I gave these comments as I thought this was so awesome a way to explain turing machine!

Re: Great way to teach this beautiful concept.

Hi there,

Thanks for your comments. I'm glad you liked my idea!

1. The machine head did the moving for the sake of visual clarity.

2. I had an extra-enthusiastic student who wanted to take part and I knew it wouldn't matter. :)

3. I explained the magic of the successor function and how it grounded mathematical functions generally. We didn't have time to do extra additions.

4. Nice! :)

Thanks so much for your input. Turing machines make me shiver with delight.


Cheers,
Kate

Re: Great way to teach this beautiful concept.

Thanks for you detailed reply. You have everything accounted for :) Very Nice!

Turing Machines are always a delight!! The first time I read about it I didnt sleep for three days in search of a better machine than this to decide languages which cannot be decided by the turing machine - obviously I failed. The thing is that the concept of turing machine is so decpetively simple it is natural for people to harbour such unfounded confidence. You seriously want to doubt Church-Turing thesis. May be our brain is a hypercomputer and hence the urge! An identity crisis you see :)
This is a really good read for me, Must admit that you are one of the best bloggers I ever saw.Thanks for posting this informative article.
hermes handbags Coach handbags hermes birkin handbags hermes purses discount hermes handbags hermes kelly handbags hermes lindy handbags hermes wallets hermes birkin bags burberry handbags hermes handbag coach handbags
me2009

July 2014

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  

Tags

Powered by LiveJournal.com