STEAM stands for Science, Technology, Engineering, Arts, and Mathematics. This post describes a possible plan for a crowd of many people to participate in. Roles for players consist of:
- A Recorder.
- State Actors.
- Holders of letters in a line.
I once read Terry Eagleton suggesting that part of the definition of art is that it be "somewhat pointless."2.0 Equipment
Equipment to be provided consists of:
- A six-sided die.
- Two balls. They could be soccer balls, beach balls, volley balls, or so on. One ball is called the Head, and the other ball is called the State Pointer.
- Six sets of equipment, labelled 1 through 6. A set of equipment consists of:
- A set of cards, where each card is a "letter" from an alphabet. Letters can be, for example, "Blank", "(", ")", ";", "End", "0", and "1". Many letters must have many cards with that letter.
- A set of state placards. Each state placard contains:
- An arbitrary label. These labels are arbitrary, but not repeated. They could be in high elvish, for all it matters, as long as participants can pronounce each label.
- Either the word "Halt" or a set of rules. The placards for the halting states may also contain a short phrase. Each rule in a set of rules is designated by a letter from the alphabet.
- Guidelines for setting up. These guidelines include:
- Optional guidelines for the geographical distribution of states.
- A specification of which State Actor initially holds the State Pointer.
- Guidelines for forming an initial line of letters from the alphabet. These guidelines must include a specification of which holder of a letter initially also holds the Head.
The Recorder throws the die and chooses the corresponding set of equipment. One might create only one set of equipment, and this step would be omitted.
The Recorder distributes the state placards. A audience member comes up for each placard. He collects it, and becomes a State Actor. The State Actors all gather, with some distance between them, in a designated region. (One might break down the region into sub-regions, for subsets of the states, if one wants.)
The Recorder gives the State Pointer to the State Actor holding the placard for the initial state.
The Recorder reads out the guidelines for the initial line of letters. Audience members come up and form a line, accordingly. As an example, the guidelines might say:
The first player sits in the line and holds the "End" letter. The second player stands behind the first player. He holds a "Blank" and the Head. A number of players sit in the line behind the second player. They should each hold "0" or "1", as they choose. A person should sit after these players, and she holds a ";". Another number of players sit in in a row behind her. They also should each hold a "0" or "1".
The Recorder writes down the sequence of letters in the initial set up. This step is optional.
Play can now commence. Play consists of a sequence of clock cycles.3.2 A Clock Cycle
The player holding the Head commences a clock cycle. This player calls out the letter he is holding.
The state actor holding the State Pointer now plays. He looks at his rules and finds the rule corresponding to the letter that has been called out. Each rule has two parts. The first part is either a letter from the alphabet or the word "Forward" or the word "Backward". The second part is the name of a state. That state could be the label on the state placard that this State Actor is holding. Or it could be another state.
If the State Actor calls out a letter, an audience member comes up. He selects that letter from leftover letters in the initial set of equipment. He replaces the player holding the Head in the line. And that player hands the new player the Head.
If the State Actor calls out Forward, the player holding the Head hands it to the player holding a letter in front of him and sits down. The player now holding the Head stands up. There would be no such player if the player holding the Head at the start of the cycle is standing at the front of the line. In this case, an audience member picks up a "Blank" from the leftover set of equipment. That player accepts the Head and stands at the front of the line.
If the State Actor calls out Backward, the player holding the Head hands it to the player holding a letter behind him and sits down. As you might expect, that player now holding the Head stands up. This step might also result in a new player coming up from the audience and joining the line. And this new player would join the line at the back.
The State Actor holding the State Pointer now calls out the state listed on the second part of the rule he is executing. If that state is not the state listed on his state placard, he hands the State Pointer to the appropriate State Actor.
The Recorder writes down the new state that the State Pointer has now transitioned to. (This step is optional.)3.3 Ending the Game
The game ends either when the players become convinced it could go on forever, or it ends when a State Actor holding a placard for a halting state receives the State Pointer. If the game ends in a halting state, the State Actor reads the corresponding phrase from the state placard. That phrase might be something like:
You have been a Turing machine computing the sum of two non-negative integers, written in binary.
Or it could be:
You had at least one unmatched parentheses in your initial line.
If you want, the Recorder could have more audience members come up to recreate the initial line. You can then review, if you like, the computation. For example, you might check that the sum of the two numbers separated by a comma in the initial line up is equal to the number now represented by the final line up on the stage.4.0 Much To Do
Obviously, much would need to be done to flesh this out. In particular, equipment sets need to be constructed. Some choices to think about:
- Would one want to include an equipment set in which the simulated Turing machine does not terminate for some initial line of letters? Or would one want to, at least for the first performance, only have rules that are guaranteed termination for all (valid?) inputs?
- Might one want to emulate automata for languages lower down on the Chomsky hierarchy? For example, one might create a stack to be pushed and popped before the start of the line. Here I envision that a subset of the states specify subroutines. And the State Actors defining these subroutines might be grouped separately from the other actors.
- Would one want to share alphabets among more than one equipment set? Maybe all six sets should have the same alphabet.
- How would one describe the initial line up for a Turing machine that is to decide or semi-decide whether a given string is in a given language? The specification of a grammar for generating a string can be quite confusing to beginners.
- I am thinking that one would not want to create rules for a universal Turing machine. Even some of the suggestions above might be too long to play.
An interesting variation would be to simulate a non-deterministic Turing machine. For some clock cycles, the line would be duplicated. And one would introduce another Head and State Pointer.5.0 Instruction and Theatrics
This activity could serve pedagogical purposes. Suppose the players are different cohorts of students. Could the older students be directed to write the rules for some other computation at the next meeting? Could a set of recursive functions be built up over many meetings? Maybe one would end up with a group engaging in real-time debugging in a joint activity.
One could set up an accompanying talk or lecture. Many topics could be broached: The Church-Turing thesis and universality, uncomputable functions and the halting problem, computational complexity and the question of whether P equals NP, linguistics and the Chomsky hierarchy, etc. Or one might talk about the British secret service and reading the Nazi's mail. I guess there is both a Broadway play and a movie to go along with this activity.
One could introduce some sophistication in showmanship, depending on where this concept is instantiated. I like the idea of the alphabet players wearing different colored shirts, with each color corresponding to a character. Zero could be red, and one could be green. Blanks would be a neutral color, such as white. The State Actors could be in a dim area, with a spotlight serving as the State Pointer. The State Actors or the letter holders could be members of an orchestra, with some tune being played for every state transition or invoked rule. At termination, the entire derivation written down by the Recorder could be run-through. I imagine it would be difficult to design a set of rules that results in an interesting tune. At any rate, I guess the interests of an observing mathematician, the participants, and a theatergoer would be in tension.
I hope if somebody was to try this project, they would give me appropriate acknowledgement.Reference
- Lou Fisher (1975). "Nobody Named Gallix", The Magazine of Fantasy and Science Fiction (Jan.): pp. 98-109.
- Andrew Hodges (1983). Alan Turing: The Enigma, Princeton University Press.
- HarryR. Lewis and Christos H. Papadimitriou (1998). Elements of the Theory of Computation, 2nd edition. Prentice Hall.