How To Find Fluke Switch Points

Figure 1: Convergence of Newton Method

This post steps through an algorithm for finding a fluke switch point. I used a different example when I tried to explain this before. Today, I use an example building on my draft ROPE Article.

Consider Figure 3 in this post, repeated below as Figure 2. Let s₁ = s₂ = 1. I want to find s₃, the markup in the corn industry, such that the wage curves for Gamma, Delta, Eta, and Theta intersect at a single switch point. One wants to find a function one of whose zeros is the desired markup.

Figure 2: Variation of Switch Points with the Markup in the Corn Industry

This economy produces a single consumption good, called corn. Corn is also a capital good, that is, a produced commodity used in the production of other commodities. In fact, iron, steel, and corn are capital goods in this example. So three industries exist. One produces iron, another produces steel, and the last produces corn. Two processes exist in each industry for producing the output of that industry. Each process exhibits Constant Returns to Scale (CRS) and is characterized by coefficients of production. Coefficients of production (Table 1) specify the physical quantities of inputs required to produce a unit output in the specified industry. All processes require a year to complete, and the inputs of iron, steel, and corn are all consumed over the year in providing their services so as to yield output at the end of the year.

Table 1: The Technology

Input	Iron Industry		Steel Industry		Corn Industry
	a	b	c	d	e	f
Labor	1/3	1/10	5/2	7/20	1	3/2
Iron	1/6	2/5	1/200	1/100	1	0
Steel	1/200	1/400	1/4	3/10	0	1/4
Corn	1/300	1/300	1/300	0	0	0

A technique consists of a process in each industry. Table 2 specifies the eight techniques that can be formed from the processes specified by the technology. If you work through this example, you will find that to produce a net output of one bushel corn, inputs of iron, steel, and corn all need to be produced to reproduce the capital goods used up in producing that bushel.

Table 2: Techniques

Technique	Processes
Alpha	a, c, e
Beta	a, c, f
Gamma	a, d, e
Delta	a, d, f
Epsilon	b, c, e
Zeta	b, c, f
Eta	b, d, e
Theta	b, d, f

Given the markups s₁, s₂, and s₃, the wage and prices under Gamma are rational functions of the scale factor for the rate of profits:

w_γ(r) = (f₃ r³ + f₂ r² + f₁ r + f₀)/(g₂ r² + g₁ r + g₀)

p_γ,1(r) = (u₂ r² + u₁ r + u₀)/(g₂ r² + g₁ r + g₀)

p_γ,2(r) = (v₂ r² + v₁ r + v₀)/(g₂ r² + g₁ r + g₀)

Since corn is the numeraire, its price is unity. The coefficients of the polynomials are functions of the coefficients of production for the first, second, and first processes in the iron, steel, and corn industries, respectively, and of the markups.

The Delta technique differs from Gamma in the process for producing corn. The extra profits obtained in operating the second corn-producing process at Gamma prices are:

h₁(r)/(g₂ r² + g₁ r + g₀) = 1

- [(a_f,1,3 p_γ,1(r) + a_f,2,3 p_γ,2(r) + a_f,3,3)(1 + s₃r)

+ a_f,0,3 w_γ(r)]

A switch point between Gamma and Delta is found as an appropriate zero of h₁(r), which is a cubic polynomial. Denote r₁(s₃) as the zero sought for the fluke case.

The extra profits obtained in operating the second iron-producing process at Gamma prices are:

h₂(r)/(g₂ r² + g₁ r + g₀) = p_γ,1(r)

- [(a_b,1,1 p_γ,1(r) + a_b,2,1 p_γ,2(r) + a_b,3,1)(1 + s₁r)

+ a_b,0,1 w_γ(r)]

An appropriate zero of h₂(r) is a switch point between Gamma and Eta. Denote r₂(s₃) as the zero sought for the fluke case.

Consider the following function:

h(s₃) = r₂(s₃) - r₁(s₃)

A zero of h(s₃) is such that the wage curves for Gamma, Delta, Eta, and Theta intersect at a single switch point. At a switch point for Gamma, Delta, and Eta, neither extra profits nor extra costs will be obtained in operating either iron-producing and corn-producing processes. Since the same steel-producing process is operated in all four techniques, Theta is also cost-minimizing at this switch point.

One can find such a zero by applying Newton’s method to two initial guesses, as illustrated in Figure 1 at the top of the post. Some experimentation allows one to determine two initial guesses, s⁰₃ and s¹₃, for the markup in the corn industry and for which roots of the cubics are wanted. The slope of a linear approximation to the function whose zero is sought is:

m_{i + 2} = [h(sⁱ₃) - h(s^{i + 1}₃)]/(sⁱ₃ - s^{i + 1}₃), i = 0, 1, 2, ...

The intercept with the ordinate is:

b_{i + 2} = h(s^{i + 1}₃ - m_{i + 2} s^{i + 1}₃, i = 0, 1, 2, ...

The next iteration is:

s^{i + 2}₃ = - b_{i + 2}/m_{i + 2}, i = 0, 1, 2, ...

In my experience, Newton's method converges fairly rapidly in this application of finding fluke switch points.

A Iterative Procedure Converging To Prices Of Production

Figure 1: Prices of Corn and Ale in an Iterative Process

1.0 Introduction

Anwar Shaikh proposed, sometime in the 1970s, I guess, an interpretation of Marx's transformation problem. Marx's solution in volume 3 of Capital is the first step of an iterative process. I thought I might work through this idea with an example from an old exposition of mine. I am not sure how faithful I am to Shaikh's approach. I notice that as I explain it, the equality of total values and of total prices is maintained for gross output. In this conception, Marx's solution to the transformation problem is not incorrect or incoherent, but merely incomplete.

My favorite solution to the transformation problem is based on von Charasoff's original capital, also known as Sraffa's standard commodity. Both Shaikh and Sraffa's solution raise a question about what is special about labor. As I understand it, Shaikh's iterative procedure does not need to start at labor values. One needs to look outside what is formalized in the mathematics.

2.0 Technology and Labor Values

Consider a simple capitalist economy that produces only two goods, corn and ale. Assume the amounts of corn and ale produced each year are given, as well as the production processes used in each industry. Corn and ale are each produced by processes that require a year to complete. These processes require a certain number of workers to be hired at the beginning of the year, as well as the purchase of certain quantities of corn and ale to be used as inputs in production. Operating these processes then produces certain quantities of outputs of corn and ale for use at the end of the year. Table 1 shows the amount of inputs per unit output for both industries. The data allow for surplus production, that is for more corn and ale to be produced than are used as inputs. I might as well assume Constant Returns to Scale (CRS).

Table 1: The Technique of Production

Input	Corn Industry	Ale Industry
Labor	1 Person-Year	1 Person-Year
Corn	1/8 Bushel	3/8 Bushel
Ale	1/16 Bottle	1/16 Bottle
Output	1 Bushel	1 Bottle

I now want to consider a couple of levels at which these processes can be operated. Suppose the first process is scale to produce a gross output of 15/16 bushels, and the second process is used to produce 1/16 bottles. Then the quantity flows shown in Table 2 result. With these gross outputs, one person-year is employed throughout the economy. The ale used up in production is exactly replaced by the output of ale industry. 9/64 bushels of the corn produced replace the corn used up in production. So these quantity flows are for a stationary state in which one person-year of labor are used to produce a net output of 51/64 bushels of corn. So a bushel of corn embodies 64/51 ≈ 1.255 person-years per bushel. If the wage consists entirely of corn, the maximum wage is 51/64 bushels per person-years.

Table 2: Processes Scaled to Produce a Net Output of Corn

Input	Corn Industry	Ale Industry
Labor	15/16 Person-Year	1/16 Person-Year
Corn	15/128 Bushel	3/128 Bushel
Ale	15/256 Bottle	1/256 Bottle
Output	15/16 Bushel	1/16 Bottle

On the other hand, suppose that 3/10 bushels of corn are produced in the corn industry, and 7/10 bottles are produced in the ale industry. The quantity flows shown in Table 3 result. Here, too, one person-year is employed throughout the economy. The corn produced is wholly used to replace the corn used as inputs throughout the economy. The net output of the ale industry, after replacing the ale used as capital goods, is 51/80 bottles. That is, a bottle of ale embodies 80/51 ≈ 1.569 person-years per bottle. The maximum wage is 51/80 bottles per person-years.

Table 3: Processes Scaled to Produce a Net Output of Corn

Input	Corn Industry	Ale Industry
Labor	3/10 Person-Year	7/10 Person-Year
Corn	3/80 Bushel	21/80 Bushel
Ale	3/160 Bottle	7/160 Bottle
Output	3/10 Bushel	7/10 Bottle

Labor values are 64/51 ≈ 1.255 person-years per bushel and 80/51 ≈ 1.569 person-years per bottle.

3.0 An Iterative Procedure

To specify the iterations of prices, a general notation is useful. Accordingly, define the following variables.

• a₀: A two-element row vector of direct labor coefficients.
• A: A 2x2 Leontief matrix.
• q: A two-element column vector of gross outputs.
• y: A two-element column vector of net outputs.
• w: A two-element column vector of the commodity wage.
• p: A two-element row vector of prices. Indexed in the iterative process.
• C_n: Constant capital, evaluated at prices in the iterative process.
• V_n: Variable capital, evaluated at prices in the iterative process.
• S_n: Surplus product, evaluated at prices in the iterative process.

The rate of profits is defined in terms of the ratio of surplus value to the value of the capital advanced. Both the numerator and the denominator are aggregated across all industries. Accordingly, I find it convenient to specify the level and composition of the economy as such that employment is one person-year, and the net output of the economy is in the proportions of the wage basket. These assumptions are more restrictive, I think, than is needed. Anyways, for this exposition of the first case, suppose quantity flows are as in Table 2. And let the commodity wage be at a level where half the net output is paid out as the wage. In this case, only corn is a consumption good.

Initially, prices are assumed to be labor values. The price of constant capital, at a given iteration, is:

C_n = p_n A q

The value of advanced wage goods, at a given iteration, is:

V_n = p_n w a₀ q

The value of surplus value is the value of net output not paid out to the workers:

S_n + V_n = p_n y

I take wages as advanced, along with constant capital. Accordingly, the overall rate of profits at a given iteration, is:

r_n = S_n/(C_n + V_n)

Prices are iterated as follows:

p_{n + 1} = p_n (A + w a₀)(1 + r_n)

Notice that all the terms on the right-hand side are defined at a given iteration. Table 4 shows the results for the first few iterations in the case of the numeric example, with the assumptions for the first case.

Table 4: One Set of Iterative Prices

Count	p1 (approx.)	p2 (approx.)	S/(C + V) (approx.)
0	64/51	80/51	0.645570
1	1.242244	1.758501	0.634923
2	1.242776	1.750519	0.635368
...	...	...	...
	1.242755	1.750839	0.635350

As I understand, this iteration occurs in logical time. It is not a process in historical time. This process converges to prices of production, which satisfy the following equation:

p (A + w a₀)(1 + r) = p

Marx sets out the first iteration above. One can modify the assumptions. I do not think much is gained by restricting attention to schemes of simple and expanded production, as at the end of Volume 2 of Capital.

Figure 2: Rate of Profits in an Iterative Process

In Figures 1 and 2, the lines labeled 'Corn Wage' are for the quantity flows in Table 2. The lines labeled 'Ale Wage' are for the quantity flows in Table 3. I suppose a better numeric example would not converge as quickly.

4.0 Conclusion

This post is one more illustration that academics have had ways of making sense of the transformation problem. One could argue about which way is more insightful. Do these discussions help make sense of capitalist economies and of the confusions in mainstream economics?

References

• Deepankar Basu. 2020. Can commodities be substance of value? UMass Economics Working Papers. 290.
• Fred Moseley. 2020. A critique of Shaikh's two interpretations of Marx's 'transformation problem'. Cambridge Journal of Economics.
• Anwar Shaikh. 1977. Marx's theory of value and the 'transformation problem'. The Subtle Anatomy of Capitalism (ed. by Jesse Schwartz).

Direct And Indirect Methods, Axioms And Algorithms For The Choice Of The Technique

1.0 Introduction

Kurz and Salvadori (1995) explain prices of production with two methods of analysis: the direct method and the indirect method. The indirect method, for the circular capital case, involves the creation of the wage frontier, the most well-known diagram to come out of Sraffa (1960). The direct method characterizes a system of prices of production by axioms, while the indirect method suggests algorithms for finding cost-minimizing techniques.

2.0 The Direct Method

In both methods, the given technology is characterized as a set of processes. A process is specified as the quantities of inputs and the quantities of outputs for a given level of operation. In the case of reproducible natural resources, that is, land, the quantity available of each quality of land should be specified. I do not think that non-reproducible natural resources fit comfortably in this model; some work has been done on the corn-guano model exploring this.

I find it useful to assume constant returns to scale. I understand why Sraffa does not need this assumption in the first two sections of his book. He does not consider the choice of technique there or how a state can be reached in which the same rate of profits is obtained for each operated process. He considers which process is operated and the level of operation of each process as given. Sraffa explicitly says that his assumption, that no question of the returns to scale arises, does not apply to the last section, analyzing the choice of technique. I find it difficult to understand how the theory of joint production can be set out without considering the choice of technique.

Informally, the following six axioms characterize quantities and prices for a capitalist economy undergoing smooth reproduction:

1. The levels of operation of the processes comprising the technology are such that, after replacing commodities used up in production and those needed for accumulation at the given rate of growth, requirements for use can be satisfied by net output.
2. The levels of operation of the processes comprising the technology are such that one unit of labor is employed throughout the economy.
3. No pure economic profits can be made by operating any process. That is, for each process, the revenues obtained from operating it do not exceed its costs, including charges for the rate of profits, rent, and wages.
4. The price of the numeraire is unity.
5. The rule of free goods: The price of a good in excess supply (that is, with a level of production strictly exceeding its requirements for use) is zero.
6. The rule of non-operated processes: If the costs of operating a process, including charges for the rate of profits, strictly exceeds the revenues obtained from that process, it is not operated.

Kurz and Salvadori set out these axioms for specific models, along with non-negativity conditions. In models of rent, one discards the second axiom; scale matters. The most general model, I guess, is that of full joint production. What can be deduced from the axioms varies among these models.

3.0 The Indirect Method

One can set out the indirect method by applying combinatorics, in which one looks at all possible techniques that can be constructed from the processes comprising the technology. Discard those techniques that cannot satisfy requirements for use. In the circulating capital case, each technique yields a system of equations with one degree of freedom. These equations can be solved. So each technique has a wage curve, in which the wage is lower, the higher the rate of profits. All these curves can be graphed on the same graph, and the outer wage frontier shows which technique is cost-minimizing at any given wage or rate of profits.

How can a combinatorial explosion be avoided in this analysis? By applying certain algorithms which do not require one to consider every technique. Christian Bidard champions the Lemke algorithm for the case of fixed capital. As in the case of the simplex method for linear programs, one does not need to consider every feasible technique in finding the cost-minimizing technique for a given wage or rate of profits.

4.0 Questions

Different, but related questions, arise for the two methods. For the direct method, one asks, what conditions must technology satisfy such that a solution of quantities and prices exist? When is this solution unique? For the case of circulating capital, one looks at the Hawkins-Simon condition, the Perron-Frobenius theorem, and the misleadingly-named non-substitution theorem. In the case of general joint production, the special case in which the rate of profits is equal to the rate of growth is of interest. I suppose research questions might still revolve about how many of the nice properties of circulating capital carry over to models that are intermediate between this case and full joint production. For example, has any work been done on combining a fixed capital model with a model of extensive rent? Biao Huang recently found that revisiting the fixed capital model was worthy of research. Relaxing the assumption of free disposal is important for investigating environmental concerns.

For the indirect method, I ask on what platforms are these algorithms executing? When I apply numerical methods for finding fluke switch points, I am definitely not making any claims about how markets work. I think my application of linear programming and duality theory in my 2005 Manchester School article is another case of an external analyst examining an economic model. But sometimes, as in my 2017 ROPE article, an algorithm is described that can be executed by an abstract market. At least this seems to be Bidard's view. And these algorithms might even be able to be executed in parallel by, say, accountants working for different firms in different industries. What I would like to see, however, is how market structures, how bids and asks are resolved, for example, enters into these algorithms. Be that as it may, one can ask which algorithms converge. How fast? Is the point to which they converge unique and independent of the initial condition?

References

• Christian Bidard. 2004. Prices, Reproduction, Scarcity. Cambridge University Press.
• Heinz D. Kurz and Neri Salvadori (1995) Theory of Production: A Long-Period Analysis. Cambridge University Press.
• Keiran Sharpe. 1999. Note and comment: on Sraffa's price system. Cambridge Journal of Economics 23(1): 93-101.
• Piero Sraffa. 1960. The Production of Commodities by Means of Commodities: Prelude to a Critique of Economic Theory. Cambridge University Press.
• K. Vela Velupillai. 2021. Definitions, assumptions, propositions and proofs in Sraffa's PCMC. In A Reflection on Sraffa's Revolution in Economic Theory (ed. by Ajit Sinha). Palgrave
• Ludwig Wittgenstein. Remarks on the Foundations of Mathematics, revised edition.
• J. E. Woods. 1990. The Production of Commodities: An Introduction to Sraffa. Macmillan.

How To Find Fluke Switch Points

Figure 1: Convergence to a Pattern of Switch Points over the Axis for the Rate of Profits

1.0 Introduction

This post illustrates how to find fluke switch points. As usual, I proceed by example, in this case, as taken from my paper in Structural Change and Economic Dynamics.

2.0 Technoplogy

In this example of a capitalist economy, two commodities, iron and corn, are produced. One process is known for producing iron. In the iron industry, workers use inputs of iron and corn to produce an output of iron. The output of the iron industry is one ton with the inputs shown in Table 1. Two processes are known for producing corn. Each corn-producing process shown in Table 1 produces an output of one bushel corn from inputs of labor power, iron, and corn. Assume constant returns to scale.

Table 1: The Coefficients of Production

Input	Industry
	Iron	Corn
	I	II Alpha	II Beta
Labor	a0,1 = 1	a0,2α = (5191/5770) e1/10 - σt	a0,2β = 305/494
Iron	a1,1 = 9/20	a1,2α = (1/40) e1/10 - σt	a1,2β = 3/1976
Corn	a2,1 = 2	a2,2α = (1/10) e1/10 - σt	a2,2β = 229/494

3.0 Switch Points

I take corn as the numeraire. Wages are paid out of the surplus at the end of the harvest. I take the rate of profits as given. In this post, I do not explain how to find the price of iron and the wage for, say, the Alpha technique, given the technology at a given value of (σ t).

At a switch point, no excess profits or costs arise in evaluating the Beta process in the corn industry at Alpha prices. That is, switch points are the roots of the following equation.

1 - {[p₁^α(σt) a_1,2^β + a_2,2^β](1 + r) + w^α(σt) a_0,2^β} = 0

The above is a quadratic equation for this example. Let f_k(σ t) denote the kth root of the above equation.

r_k = f_k(σ t)

These are the switch points for a specific value of the parameters σ t. I fix σ at 1/10. Figure 2 graphs the switch points, as well as the maxmimum wage, against time. You can see technical progress brings about reswitching and takes it away.

Figure 2: Fluke Switch Points Partition Time

4.0 Numerical Methods

Various fluke cases arise in the example. They can be found by numerical methods. Table 2 defines, for four types of fluke cases, a new function whose root is the parameter values that correspond to the type of fluke case. For illustration, consider the fluke switch point that arises on the axis for the rate of profits with σ t ≈ 0.6663189. That is, g(σ t) is the difference between the maximum rate of profits for the Beta technique and the rate of profits for a selected switch point for the Alpha and Beta techniques.

Table 2: Functions and Their Zeros

Function	Fluke Case
gk(σ t) = fk(σ t) + 1	Pattern of switch points for the reverse substitution of labor.
gk(σ t) = fk(σ t)	Pattern of Switch points over the wage axis.
gk(σ t) = rmax, β - fk(σ t)	Pattern of switch points over the axis for the rate of profits.
gk(σ t) is the discriminant of the quadratic equation above	Reswitching pattern of switch points.

One needs two initial parameter values to start either algorithm specified here. Figure 3 graphs extra profits in operating the corn process in the Beta technique, as evaluated at Alpha prices. Extra profits are shown for two different parameter values. On the left panel, a switch point exists for a rate of profits smaller than the maximum rate of profits. The parameter values are evidently too small for a pattern of switch points over the axis for the rate of profits. On the right panel, the parameter values are too large. These are acceptable initial values.

Figure 3: Initial Values for a Pattern Over the Axis for the Rate of Profits

One can find the desired parameter value by either a bisection method or Newton’s method. Figure 4 provides a flowchart for the bisection method. The parameter values are updated to the midpoint of the current iterations. One of the current iterations is updated while keeping invariant the condition that the current iterations bound the zero of the function whose zero is sought. When the distance between the current iterations is small enough, either iteration is considered an acceptable approximation of the parameter values at which the fluke case arises.

Figure 4: Bisection Method

Figure 5 specifies Newton's method. An iteration for Newton’s method is based on approximating the function whose zero is sought by a straight line going through the two points determined by the previous two iterations. You can see that the slope and intercept for this line are found in the block in the lower left of the figure. And that the next iteration of the parameter values are found by an update calculated with this slope and intercept.

Figure 5: Newton Method

Newton's method is not guaranteed to converge, albeit I have had no issues in this context of finding fluke cases in the analysis of the choice of technique. When it does converge, its convergence is much faster than the bisection method (Figure 1).

A Market Algorithm

Figure 1: Specification of a Market Algorithm

1.0 Introduction

This article is heavily based on Bidard (2004).

An approach to the analysis of the choice of technique, in keeping with construction of the outer envelope of wage curves, is to consider replacing processes, more or less, one at a time. This post presents this approach as following an algorithm.

Assume that a set of techniques exist where all techniques are at least viable, indecomposable, and produce the same set of commodities. From the set of techniques, one can form a set of processes. In each process, workers produce a single commodity at the end of the year from certain inputs. The inputs, by assumption, are totally consumed in the course of the year. I also assume that the numeraire is specified.

Consider the algorithm specified by the flowchart in Figure 1. For this to be an algorithm, Steps 1 and 3 must be fully specified. One might as well assume that a known pseudo random number generator is used with a specified initial seed. Whether or not a candidate process yields extra profits is found in Step 5 with the prices of production calculated in Step 2. A process yields extra profits if and only if:

p a_.,j (1 + r) + w a_0,j > p_j

where a_0,j is the direct labor coefficient, and a_.,j is a column vector for the new process. I am imagining that a_.,j is the j column of the Leontief input-output matrix for a new technique. This new technique is formed by replacing a process in the technique previously selected in Step 2. Since, by assumption, no joint production exists, the process to be replaced is easily found. It is the process in the current technique that produces the same commodity as the candidate process. I have taken the wage as given in this specification of the algorithm. One could just as well take rates of profits as given.

This algorithm converges to a cost-minimizing technique. Consider the sequence of Steps enumerated as ‘2, 3, 4, (5, 7, 9)*, 5, 6, 2’. This expression denotes a single path around the loop on the bottom left of Figure 1, including zero or more paths around the loop on the right. As long as the loop on the right is repeated less times than the number of techniques, this path can be repeated. The question arises whether or not this algorithm contains an infinite loop. In a simple case, a process would be introduced into a technique because it is cost-minimizing for prices corresponding to the first technique, and that first technique would be cost-minimizing at the prices corresponding to the new technique. It can be shown that the existence of an infinite loop is impossible, under the assumption that no joint production exists. The algorithm always terminates.

(The use of metalinguistic symbols of parentheses and an asterisk to denote a repeated sequence of symbols is a convention in defining regular expressions. A sequence of symbols in a language, where the grammar of that language is specified by a regular expression, is accepted by a finite state machine, a type of automata. This is the lowest level of the Chomsky hierarchy. Chomsky (1965) uses transformational grammars to characterize human languages, which he argues are at the highest level of the hierarchy.)

Furthermore, except at switch points, the cost-minimizing technique found by the algorithm is unique. Which technique is initially selected at Step 1 or how processes are ordered at Step 3 does not matter, except for performance. The same cost-minimizing technique is ultimately found. The algorithm terminates with the selection of any one of the techniques that are cost minimizing at a switch point, depending on these details.

The algorithm is specified sequentially in Figure 1. Steps 3, 4, 5, 7, and 9 can be distributed. Inasmuch as this algorithm is executed in a capitalist economy, these steps are, in fact, distributed across firms. One might also modify the algorithm to apply when the set of processes and techniques are not known at that start of algorithm. Innovation and technical progress can be accommodated with an appropriate modification of Step 4 and Step 9. Step 7 should be eliminated, and the algorithm would be defined without a termination step, like daemons in operating systems. When the algorithm is modified for distributed processing, more than one process might be introduced into a technique simultaneously, including in the same industry. For which technique, then, are prices calculated in Step 2? This relates to the question of when labor expended in new processes is ‘socially necessary’, as Marx put it.

References

• Bidard, Christian. 2004. Prices, Reproduction, Scarcity. Cambridge: Cambridge University Press.
• Chomsky, Noam. 1965. Aspects of the Theory of Syntax. Cambridge: M.I.T. Press.

Reversing Figure And Ground In Life-Like Celluar Automata

Figure 1: Random Patterns in Life and Flip Life

1.0 Introduction

I have occasionally posted about automata. A discussion with a colleague about Stephen Wolfram's A New Kind of Science reminded me that I had started this post some time last year.

This post has nothing to do with economics, albeit it does illustrate emergent behavior. And I have figures that are an eye test. I am subjectively original. But I assume somebody else has done this - that I am not objectively original.

This post is an exercise in combinatorics. There are 131,328 life-like Celluar Automata (CA), up to symmetry.

2.0 Conway's Game of Life

John Conway will probably ever be most famous for the Game of Life (GoL). I wish I understood monstrous moonshine.

The GoL is "played", if you can call it that, on an infinite plane divided into equally sized squares. The plane looks something like a chess board, extended forever. See the left side of Figure 1, above. Every square, at any moment in time, is in one of two states: alive or dead. Time is discrete. The rules of the game specify the state of each square at any moment in time, given the configuration at the previous instant.

The state of a square does not depend solely on its previous state. It also depends on the states of its neighbors. Two types of neighborhoods have been defined for a CA with a grid of square cells. The Von Neumann neighbors of a cell are the four cells above it, below it, and to the left and right. The Moore neighborhood (Figure 2) consists of the Von Neumann neighbors and the four cells diagonally adjacent to a given cell.

Figure 2: Moore Neighborhood of a Dead Cell

The GoL is defined for Moore neighborhoods. State transition rules can be defined in terms of two cases:

• Dead cells: By default, a dead cell stays dead. If a cell was dead at the previous moment, it becomes (re)born at the next instant if the number of live cells in its Moore neighborhood at the previous moment was x₁ or x₂ or ... or x_n.
• Alive Cells: By default, a live cell becomes dead. If a cell was alive at the previous moment, it remains alive if the number of live cells in its Moore neighborhood at the previous moment was y₁ or y₂ or ... or y_m.

The state transition rules for the GoL can be specified by the notation Bx/Sy. Let x be the concatenation of the numbers x₁, x₂, ..., x_n. Let y be the concatenation of y₁, y₂, ..., y_m. The GoL is B3/S23. In other words, if exactly three of the neighbors of a dead cell are alive, it becomes alive for the next time step. If exactly two or or three of the neighbors of a live cell are alive, it remains alive at the next time step. Otherwise a dead cell remains dead, and a live cell becomes dead.

The GoL is an example of recreational mathematics. Starting with random patterns, one can predict, roughly, the distributions of certain patterns when the CA settles down, in some sense. On the other hand, the specific patterns that emerge can only be found by iterating through the GoL, step by step. And one can engineer certain patterns.

3.0 Life-Like Celluar Automata

For the purposes of this post, a life-like CA is a CA defined with:

• A two dimensional grid with square cells and discrete time
• Two states for each cell
• State transition rules specified for Moore neighborhoods
• State transition rules that can be specified by the Bx/Sy notation.

How many life-like CA are there? This is the question that this post attempts to answer.

The Moore neighborhood of cell contains eight cells. Thus, for each of the digits 0, 1, 2, 3, 4, 5, 6, 7, and 8, they can appear in Bx. For each digit, one has two choices. Either it appears in the birth rule or it does not. Thus, there are 2⁹ birth rules.

The same logic applies to survival rules. There are 2⁹ survival rules.

Each birth rule can be combined with any survival rule. So there are:

2⁹ 2⁹ = 2¹⁸

life-like CA. But this number is too large. I am double counting, in some sense.

4.0 Reversing Figure and Ground

Figure 1 shows, side by side, grids from the GoL and from a CA called Flip Life. Flip Life is specified as B0123478/S01234678. Figure 3 shows a window from a computer program. In the window on the left, the rules for the GoL are specified. The window on the right is used to specify Flip Life.

Figure 3: Rules for Life and Flip Life

Flip Life basically renames the states in the GoL. Cells that are called dead in the GoL are said to be alive in Flip Life. And cells that are alive in the GoL are dead in Flip Life. In counting the number of life-like CA, one should not count Flip Life separately from the GoL. In some sense, they are the same CA.

More generally, suppose Bx/Sy specifies a life-like CA, and let Bu/Sv be the life-like CA in which figure and ground are reversed.

• For each digit x_i in x, 8 - x_i is not in v, and vice versa.
• For each digit y_j in y, 8 - y_j is not in u, and vice versa.

So for any life-like CA, one can find another symmetrical CA in which dead cells become alive and vice versa.

5.0 Self Symmetrical CAs

One cannot just divide 2¹⁸ by two to find the number of life-like CA, up to symmetry. Some rules define CA that are the same CA, when one reverses figure and ground. As an example, Figure 4 presents a screen snapshot for the CA called Day and Night, specified by the rule B1/S7.

Figure 4: Day and Night: An Example of a Self-Symmetrical Cellular Automaton

Given rules for births, one can figure out what the rules must be for survival for the CA to be self-symmetrical. Thus, there are as many self-symmetrical life-like CAs as there are rules for births.

6.0 Combinatorics

I bring all of the above together in this section. Table 1 shows a tabulation of the number of life-like CAs, up to symmetry.

Table 1: Counting Life-Like Celluar Automata

	Number
Birth Rules	29
Survival Rules	29
Life-Like Rules	29 29 = 262,144
Self-Symmetric Rules	29
Non-Self-Symmetric Rules	29(29 - 1)
Without Symmetric Rules	28(29 - 1)
With Self-Symmetric Rules Added Back	28(29 + 1) = 131,328

7.0 Conclusion

How many of these 131,328 life-like CA are interesting? Answering this question requires some definition of what makes a CA interesting. It also requires some means of determining if some CA is in the set so defined. Some CAs are clearly not interesting. For example, consider a CA in which all cells eventually die off, leaving an empty grid. Or consider a CA in which, starting with a random grid, the grid remains random for all time, with no defined patterns ever forming. Somewhat more interesting would be a CA in which patterns grow like a crystal, repeating and duplicating. But perhaps an interesting definition of an interesting CA would be one that can simulate a Turing machine and thus may compute any computable function. The GoT happens to be Turing complete.

Acknowledgements: I started with version 1.5 of Edwin Martin's implementation, in Java, of John Conway's Game of Life. I have modified this implementation in several ways.

References

• David Eppstein (2010). Growth and Decay in Life-Like Celluar Automata

A Turing Machine for a Binary Counter

Table 1: Tape in Successive Start States

Input/Output Tape	Decimal
tb0	0
tb1	1
tb10	2
tb11	3
tb100	4
tb101	5

1.0 Introduction

This post describes another program for a Turing Machine. This Turing machine implements a binary counter (Table 1). I do not think I am being original here. (Maybe this was in the textbook on computability and automata that I have been reading.)

2.0 Alphabet

Table 2: The Alphabet For The Input Tape

Symbol	Number Of Occurrences	Comments
t	1	Start-of-tape Symbol
b	Potentially Infinite	Blank
0	Potentially Infinite	Binary Digit Zero
1	Potentially Infinite	Binary Digit One

3.0 Specification of Valid Input Tapes

At start, the (input) tape should contain, in this order:

• t, the start-of-tape symbol.
• b, a blank.
• A sequence of binary digits, with a length of at least one.

The above specification allows for any number of unnecessary leading zeros in the binary number on the tape. The head shall be at the blank following the start-of-tape symbol.

4.0 Specification of State

The machine starts in the Start state. Error is the only halting state. Table 3 describes some conditions, for a non-erroneous input tape, that states are designed to satisfy, on entry and exit. For the states GoToEnd, FindZero, CreateTrailingOne, Increment, and ResetHead, the Turing machine may experience many transitions that leaves the machine in that state after the state has been entered. When the state PauseCounter has been entered, the next increment of a binary number appears on the tape.

Table 3: States

State	Selected Conditions
	On Entry	On Exit
Start	The head is immediately to the left of the binary number on the tape. (The binary number on the tape at this point is referred to as "the original binary number" below.)	Same as the entry condition for GoToEnd.
GoToEnd	The head is under the first digit of the binary number on the tape.	Same as the entry condition for FindZero.
FindZero	The head is under the last digit of the binary number on the tape	If all digits in the original binary number are 1 and that number has not been updated with a leading zero, the head is under the first digit of the binary number on the tape. If the original binary number contained at least one digit 0, the head is under the location of the last instance of 0 in the original binary number, and that digit has been changed to a 1. Otherwise, the head is under the first digit in the binary number now on the tape, and that digit is now a 1 (having once been a leading zero).
CreateLeadingZero	All the digits in the original binary number are 1. The head is under the first digit of the binary number on the tape.	Same as the entry condition for CreateTrailingOne
CreateTrailingOne	All the digits in the original binary number are 1. The first digit in the original binary number has been replaced by 0. The head is under that first digit.	The original binary number has been shifted one digit to the left, and a leading zero has been prepended to it. The head is under the last digit of the binary number now on the tape.
StepForward	If all digits in the original binary number are 1, that number has been shifted one digit to the left, that number has been updated with a leading 0 which is now a 1, and the head is under that digit. Otherwise, the last instance of 0 in the original number has been updated to a 1, and the head is now under that digit tape.	Same as the entry condition for Increment.
Increment	If all digits in the original binary number are 1, that number has been shifted one digit to the left, that number has been updated with a leading 0 which is now a 1, and the head is under the next location on the tape. Otherwise, the last instance of 0 in the original number has been updated to a 1, and the head is now under the next location on the tape.	Same as the entry condition for ResetHead. All the 1's to the right of the 0 updated to a 1 have themselves been updated to a 0.
ResetHead	The head is under the last digit of the binary number on the tape, and that number is the successor of the original binary number.	Same as the entry condition for PauseCounter.
PauseCounter	The head is immediately to the left of the binary number on the tape, and that number is the successor of the original binary number.

I think one could express the conditions in the above lengthy table as logical predicates. And one could develop a formal proof that the state transition rules in the appendix ensure that these conditions are met on entry and exit of the non-halting tape, at least for non-erroneous input tapes. I do not quite see how invariants would be used here. (When trying to think rigorously about source code, I attempt to identify invariants for loops.)

5.0 Length of Tape and the Number of States

Suppose the state PauseCounter was a halting state. Then this Turing machine would be a linear bounded automaton. In the Chomsky hierarchy, automata that accept context-sensitive languages need not be more general than linear bound automata.

The program for this Turing machine consists of 10 states. The number of characters on the tape grows at the rate O(log₂ n), where n is the number of cycles through the start state. I gather the above instructions could be easily modified to not use any start-of-tape symbol. Anyways, 20 people seems more than sufficient for the group activity I have defined, for this particular Turing machine.

Appendix A: State Transition Tables

This appendix provides detail specification of state transition rules for each of the non-halting states. I provide these rules by tables, with each table showing a pair of states.

Table A-1: Start and GoToEnd

Start				GoToEnd
t	t	Error		t	t	Error
b	Forwards	GoToEnd		b	Backwards	FindZero
0	0	Error		0	Forwards	GoToEnd
1	1	Error		1	Forwards	GoToEnd

Table A-2: FindZero and CreateLeadingZero

FindZero				CreateLeadingZero
t	t	Error		t	t	Error
b	Forwards	CreateLeadingZero		b	b	Error
0	1	StepForward		0	0	Error
1	Backwards	FindZero		1	0	CreateTrailingOne

Table A-3: CreateTrailingOne and StepForward

CreateTrailingOne				StepForward
t	t	Error		t	t	Error
b	1	FindZero		b	b	Error
0	Forwards	CreateTrailingOne		0	0	Error
1	Forwards	CreateTrailingOne		1	Forwards	Increment

Table A-4: Increment and ResetHead

Increment				ResetHead
t	t	Error		t	t	Error
b	Backwards	ResetHead		b	b	PauseCounter
0	Forwards	Increment		0	Backwards	ResetHead
1	0	Increment		1	Backwards	ResetHead

Table A-5: PauseCounter

PauseCounter
t	t	Error
b	b	Start
0	0	Error
1	1	Error

A Turing Machine For Calculating The Fibonacci Sequence

Table 1: Representation of the Fibonacci Sequence

Input/Output Tape	Terms in Series
0b1;1;	1, 1
0b1;1;11;	1, 1, 2
0b1;1;11;111	1, 1, 2, 3
0b1;1;11;111;11111;	1, 1, 2, 3, 5
0b1;1;11;111;11111;11111111;	1, 1, 2, 3, 5, 8

1.0 Introduction

I thought I would describe the program for a specific Turing machine. This Turing machine computes the Fibonacci sequence in tally arithmetic, as illustrated in Table 1 above. The left-hand column shows the tape for the Turing machine for successive transitions into the Start state. (The location of the head is indicated by the bolded character.) The right-hand column shows a more familiar representation of a Fibonacci sequence. This Turing machine never halts for valid inputs. It can calculate other infinite sequences, such as specific Lucas sequences, for other valid inputs.

A Turing machine is specified by the alphabet of characters that can appear on the tape, possible valid sequences of characters for the start of the tape, the location of the head at the beginning of a computation, the states and the state transition rules, and the location of the state pointer at beginning of a computation.

2.0 Alphabet

Table 2: The Alphabet For The Input Tape

Symbol	Number Of Occurrences	Comments
0	1	Start of tape marker
b	Potentially Infinite	Blank
;	Potentially Infinite	Symbol for number termination
1	Potentially Infinite	A tally
x	1	For internal use
y	1	For internal use
z	1	For internal use

3.0 Specification of Valid Input Tapes

At start, the (input) tape should contain, in this order:

• 0, the start of tape marker.
• b, a blank.
• Zero or more 1s.
• ;, a semicolon.
• One or more of the following:
• Zero or more 1s.
• ;, a semicolon.

The head shall be at a blank or semicolon such that exactly two semicolons exist in the tape to the right of the head. Table 3 provides examples (with the head being at the bolded character).

Table 3: Examples of Valid Initial Input

0b;;

0b1;;

0b1;1;

0b11;1;

0b1;1;11;111;11111;11111111;

4.0 Definition of State

The states are grouped into two subroutines, CopyPair and Add. Error is the only halting state, to be entered when an invalid input tape is detected. The Turing machine begins the computation with the state pointer pointing to the Start state, in the CopyPair subroutine. Eventually, the Turing machine enters the PauseCopy state. The machine then transitions to the StartAdd state, in the Add subroutine. Another number in the sequence has been successfully appended to the tape when the Turing machine enters the PauseAdd state.

The Turing machine then transitions into the Start state. The CopyPair and Add subroutines are repeated in pairs forever.

4.1 CopyPair

The input tape for the CopyPair subroutine is any valid input tape, as described above. The state pointer starts in the Start tape. Error is the only halting state. The subroutine exits with a transition from the PauseCopy state to the StartAdd state. When the PauseCopy state is entered, the tape shall be in the following configuration:

• The terminal semicolon in the tape, when the Start state was entered, shall be replaced with a z.
• The head shall be at that z.
• The tape to the right of the z shall contain a copy of the character string to the right of the head when the Start state was entered.

This subroutine can be implemented by the states described in Table 4. The detailed implementation of each state is provided in the appendix. Throughout these states, there are transitions to the Error state triggered by encountering on the tape a character that cannot be there in a valid computation.

Table 4: States in the CopyPair Subroutine

State	Description
Start	Moves the head forward one character.
ReadFirstChar	Replaces first ; or 1 (after position of head when the subroutine was called) with x or y, respectively.
WriteFirstSemi	Writes a ; at the end of the tape. Transitions to GoToTapeEnd.
WriteFirstOne	Writes a 1 at the end of the tape. Transitions to GoToTapeEnd.
GoToTapeEnd	Moves the head backward one character to locate the head at the character that was at the end of the tape when the subroutine was called.
MarkTapeEnd	Replaces original terminating ; with z.
NexChar	Replaces the x or y on the tape with ; or 1, respectively.
StepForward	Moves the head forward one character.
ReadChar	Replaces the next ; or 1 with x or y, respectively.
WriteSemi	Writes a ; at the end of the tape. Transitions to NextChar.
WriteOne	Writes a 1 at the end of the tape. Transitions to NextChar.
WriteLastSemi	Writes a ; at the end of the tape. Transitions to SetHead.
SetHead	Moves head to the z on the tape.
PauseCopy	For noting that last two numbers on the tape, when the subroutine was called, have been copied to the end of the tape.

4.2 Add

When the PauseAdd state is entered, the tape shall be in the following configuration:

• The semicolon between the z and the last semicolon, when the StartAdd state is entered, shall be replaced by a 1, if there is at least one 1 between this character and the terminating semicolon.
• The semicolon at the end of the tape, when the StartAdd state is entered, shall be erased (replaced by a blank).
• The character before the erased semicolon shall be replaced by a semicolon.
• The z shall be replaced by a semicolon.
• The head shall be at a semicolon such that two semicolons exist to the right of the head.

Table 5: States in the Add Subroutine

State	Description
StartAdd	Moves the head forward one character.
FindSemiForDele	Replaces the ; mid-number with 1.
FindSumEnd	Erases terminating ;.
EndSum	Writes terminating ; at the tape position one character backwards.
FindSumStart	Replaces z with ;.
StepBackward	Moves the head backwards one character.
ResetHead	Set head to previous ;, before the ; just written.
PauseAdd	For noting next number in Fibonacci series.

5.0 Length of Tape and the Number of States

After three run-throughs of this Turing machine, five numbers in the Fibonacci sequence will be calculated. And the tape will contain 19 characters. As shown in Table 6, the number of states is 22. For the group activity I have defined for simulating a Turing machine, 42 people are needed. (One more person is needed, in computing the next number in the sequence, to be erased from the tape than ends up as characters on the tape.) I suppose one could get by with 36 people, if one is willing to some represent two states, one in each subroutine.

Table 6: State Count

Subroutine	Number Of States	State Names
CopyPair	15	Error, Start, ReadFirstChar, WriteFirstSemi, WriteFirstOne, GoToTapeEnd, MarkTapeEnd, NextChar, StepForward, ReadChar, WriteSemi, WriteLastSemi, SetHead, WriteOne, PauseCopy
Add	7	StartAdd, FindSemiForDele, FindSumEnd, EndSum, FindSumStart, StepBackward, PauseAdd
Total	22

Appendix A: State Transition Tables

A.1: The CopyPair Subroutine

Table A-1: Start and ReadFirstChar

Start				ReadFirstChar
0	0	Error		0	0	Error
b	Forwards	ReadFirstChar		b	b	Error
;	Forwards	ReadFirstChar		;	x	WriteFirstSemi
1	1	Error		1	y	WriteFirstOne
x	x	Error		x	x	Error
y	y	Error		y	y	Error
z	z	Error		z	z	Error

Table A-2: WriteFirstSemi and WriteFirstOne

WriteFirstSemi				WriteFirstOne
0	0	Error		0	0	Error
b	;	GoToTapeEnd		b	1	GoToTapeEnd
;	Forwards	WriteFirstSemi		;	Forwards	WriteFirstOne
1	Forwards	WriteFirstSemi		1	Forwards	WriteFirstOne
x	Forwards	WriteFirstSemi		x	Forwards	WriteFirstOne
y	Forwards	WriteFirstSemi		y	Forwards	WriteFirstOne
z	z	Error		z	z	Error

Table A-3: GoToTapeEnd and MarkTapeEnd

GoToTapeEnd				MarkTapeEnd
0				0	0	Error
b				b	b	Error
;	Backwards	MarkTapeEnd		;	z	NextChar
1	Backwards	MarkTapeEnd		1	1	Error
x				x	x	Error
y				y	y	Error
z				z	z	Error

Table A-4: NextChar and StepForward

NextChar				StepForward
0	0	Error		0
b	b	Error		b
;	Backwards	NextChar		;	Forwards	ReadChar
1	Backwards	NextChar		1	Forwards	ReadChar
x	;	StepForward		x
y	1	StepForward		y
z	Backwards	NextChar		z

Table A-5: ReadChar and WriteSemi

ReadChar				WriteSemi
0	0	Error		0	0	Error
b	1	Error		b	;	NextChar
;	x	WriteSemi		;	Fowards	WriteSemi
1	y	WriteOne		1	Forwards	WriteSemi
x	x	Error		x	Forwards	WriteSemi
y	y	Error		y	Forwards	WriteSemi
z	z	WriteLastSemi		z	Forwards	WriteSemi

Table A-6: WriteLastSemi and SetHead

WriteLastSemi				SetHead
0	0	Error		0	0	Error
b	;	SetHead		b	b	Error
;	Forwards	WriteLastSemi		;	Backwards	SetHead
1	Forwards	WriteLastSemi		1	Backwards	SetHead
x	Forwards	WriteLastSemi		x	x	Error
y	Forwards	WriteLastSemi		y	y	Error
z	Forwards	WriteLastSemi		z	z	PauseCopy

Table A-7: WriteOne and PauseCopy

WriteOne				PauseCopy
0	0	Error		0
b	1	NextChar		b
;	Forwards	WriteOne		;
1	Forwards	WriteOne		1
x	Forwards	WriteOne		x
y	Forwards	WriteOne		y
z	Forwards	WriteOne		z	z	StartAdd

A.2: The Add Subroutine

Table A-8: StartAdd and FindSemiForDele

StartAdd				FindSemiForDele
0				0
b				b
;				;	1	FindSumEnd
1				1	Forwards	FindSemiForDele
x				x
y				y
z	Forwards	FindSemiForDele		z

Table A-9: FindSumEnd and EndSum

FindSumEnd				EndSum
0				0
b	Backwards	EndSum		b	Backwards	EndSum
;	b	EndSum		;	b	EndSum
1	Forwards	FindSumEnd		1	;	FindSumStart
x				x
y				y
z				z

Table A-10: FindSumStart and StepBackward

FindSumStart				StepBackward
0				0
b				b
;	Backwards	FindSumStart		;	Backwards	ResetHead
1	Backwards	FindSumStart		1
x				x
y				y
z	;	StepBackward		z

Table A-11: ResetHead and PauseAdd

ResetHead				PauseAdd
0				0
b				b
;	;	PauseAdd		;	;	Start
1	Backwards	ResetHead		1
x				x
y				y
z				z

A.3: Modifications?

The above is my first working version. I have not proven that cases can never arise where I have not specified rules in the tables for the states for the Add subroutine. Nor do I know that all rules can be triggered by some, possibly invalid, input tape. I know that I have not defined the minimum number of states for the system. For example, the ReadChar state could be defined as in Table A-12, along with the elimination of the WriteLastSemi and SetHead states. This would result in the CopyPair subroutine specification not being met and a tighter coupling between the two subroutines. On the other hand, the subroutines are already coupled through the appearance of z on the tape during the transition from one subroutine to the other.

Table A-12: Modified ReadChar

ReadChar
0	0	Error
b	1	Error
;	x	WriteSemi
1	y	WriteOne
x	x	Error
y	y	Error
z	z	PauseCopy

A STEAM Experience For A Flash Mob

1.0 Introduction

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.

3.0 Playing the Game

3.1 Preliminaries

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.