### 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'.

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' 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

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 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.
morgan303mnemosynosisdamien_wiseAn 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

somuch 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. :)

mnemosynosisp_catmnemosynosismeleahvaldelanemnemosynosisannasiegfriedhipbradl42Electronic ResourcesIf 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.

mnemosynosisRe: Electronic ResourcesI'll pass your work onto my students.

Cheers,

Kate

pbradl42Re: Electronic ResourcesBut 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.

sly_girlStuff 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.

ifiexistiexistGreat way to teach this beautiful concept.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!

mnemosynosisRe: Great way to teach this beautiful concept.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

ifiexistiexistRe: Great way to teach this beautiful concept.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 :)

pjswb2005hermes 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