Saturday, December 31, 2016

Welcome

I study economics as a hobby. My interests lie in Post Keynesianism, (Old) Institutionalism, and related paradigms. These seem to me to be approaches for understanding actually existing economies.

The emphasis on this blog, however, is mainly critical of neoclassical and mainstream economics. I have been alternating numerical counter-examples with less mathematical posts. In any case, I have been documenting demonstrations of errors in mainstream economics. My chief inspiration here is the Cambridge-Italian economist Piero Sraffa.

In general, this blog is abstract, and I think I steer clear of commenting on practical politics of the day.

I've also started posting recipes for my own purposes. When I just follow a recipe in a cookbook, I'll only post a reminder that I like the recipe.

Comments Policy: I'm quite lax on enforcing any comments policy. I prefer those who post as anonymous (that is, without logging in) to sign their posts at least with a pseudonym. This will make conversations easier to conduct.

Monday, May 16, 2016

A Turing Machine for a Binary Counter

Table 1: Tape in Successive Start States
Input/Output TapeDecimal
tb00
tb11
tb102
tb113
tb1004
tb1015

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
SymbolNumber Of
Occurrences
Comments
t1Start-of-tape Symbol
bPotentially InfiniteBlank
0Potentially InfiniteBinary Digit Zero
1Potentially InfiniteBinary 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
StateSelected Conditions
On EntryOn Exit
StartThe 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.
GoToEndThe head is under the first digit of the binary number on the tape.Same as the entry condition for FindZero.
FindZeroThe head is under the last digit of the binary number on the tapeIf 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).
CreateLeadingZeroAll 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
CreateTrailingOneAll 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.
StepForwardIf 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.
IncrementIf 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.
ResetHeadThe 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.
PauseCounterThe 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(log2 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
StartGoToEnd
ttErrorttError
bForwardsGoToEndbBackwardsFindZero
00Error0ForwardsGoToEnd
11Error1ForwardsGoToEnd
Table A-2: FindZero and CreateLeadingZero
FindZeroCreateLeadingZero
ttErrorttError
bForwardsCreateLeadingZerobbError
01StepForward00Error
1BackwardsFindZero10CreateTrailingOne
Table A-3: CreateTrailingOne and StepForward
CreateTrailingOneStepForward
ttErrorttError
b1FindZerobbError
0ForwardsCreateTrailingOne00Error
1ForwardsCreateTrailingOne1ForwardsIncrement
Table A-4: Increment and ResetHead
IncrementResetHead
ttErrorttError
bBackwardsResetHeadbbPauseCounter
0ForwardsIncrement0BackwardsResetHead
10Increment1BackwardsResetHead
Table A-5: PauseCounter
PauseCounter
ttError
bbStart
00Error
11Error

Saturday, May 14, 2016

Choice Of Technique And Search Models Of Labor Markets

I do not have an analysis or example to go with this post title. I suggest this would be an interesting research topic. What are implications of the analysis of the choice of technique, if any, for search models of labor markets?

Consider the neoclassical theory of supply and demand in labor markets under perfect competition. We know (Opocher and Steedman 2015, Vienneau 2005) that that theory is fatally undermined by an analysis of cost-minimizing firms.

I have recently read an overview, by Steve Fleetwood (2016), of models of search and matching in labor markets. And he illustrates these models with graphs of two crossing monotone curves that, at a glance, look much like labor supply and demand curves. But these curves are drawn in a different space and have a different rationale and derivation than labor supply and demand curves. A wage curve is graphed with the job creation curve. The abscissa is the tightness of the labor market, as measured by the ratio of vacancies to unemployment. The ordinate is the wage, as in the mistaken introductory story. The wage curve is also graphed against the Beveridge curve in a different space, namely, with the present discounted value of expected profit from a vacant job against unemployment.

In a long run analysis, a higher wage is associated with a lower rate of profits. This wage-rate of profits curves has implications for present discounted values. I do not see why an analysis inspired by Sraffa could not undermine search models. But one would have to go further than this to confirm this intuition. And one would need to read some of the original literature.

I do not claim that search models might not have some use in a reconstituted economics.

Reference

Wednesday, May 11, 2016

A Turing Machine For Calculating The Fibonacci Sequence

Table 1: Representation of the Fibonacci Sequence
Input/Output TapeTerms in Series
0b1;1;1, 1
0b1;1;11;1, 1, 2
0b1;1;11;1111, 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
SymbolNumber Of
Occurrences
Comments
01Start of tape marker
bPotentially InfiniteBlank
;Potentially InfiniteSymbol for number termination
1Potentially InfiniteA tally
x1For internal use
y1For internal use
z1For 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
StateDescription
StartMoves the head forward one character.
ReadFirstCharReplaces first ; or 1 (after position of head when the subroutine was called) with x or y, respectively.
WriteFirstSemiWrites a ; at the end of the tape. Transitions to GoToTapeEnd.
WriteFirstOneWrites a 1 at the end of the tape. Transitions to GoToTapeEnd.
GoToTapeEndMoves 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.
MarkTapeEndReplaces original terminating ; with z.
NexCharReplaces the x or y on the tape with ; or 1, respectively.
StepForwardMoves the head forward one character.
ReadCharReplaces the next ; or 1 with x or y, respectively.
WriteSemiWrites a ; at the end of the tape. Transitions to NextChar.
WriteOneWrites a 1 at the end of the tape. Transitions to NextChar.
WriteLastSemiWrites a ; at the end of the tape. Transitions to SetHead.
SetHeadMoves head to the z on the tape.
PauseCopyFor 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
StateDescription
StartAddMoves the head forward one character.
FindSemiForDeleReplaces the ; mid-number with 1.
FindSumEndErases terminating ;.
EndSumWrites terminating ; at the tape position one character backwards.
FindSumStartReplaces z with ;.
StepBackwardMoves the head backwards one character.
ResetHeadSet head to previous ;, before the ; just written.
PauseAddFor 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
SubroutineNumber Of
States
State Names
CopyPair15Error, Start, ReadFirstChar,
WriteFirstSemi, WriteFirstOne,
GoToTapeEnd, MarkTapeEnd,
NextChar, StepForward,
ReadChar, WriteSemi,
WriteLastSemi, SetHead,
WriteOne, PauseCopy
Add7StartAdd, FindSemiForDele,
FindSumEnd, EndSum,
FindSumStart, StepBackward,
PauseAdd
Total22

Appendix A: State Transition Tables

A.1: The CopyPair Subroutine
Table A-1: Start and ReadFirstChar
StartReadFirstChar
00Error00Error
bForwardsReadFirstCharbbError
;ForwardsReadFirstChar;xWriteFirstSemi
11Error1yWriteFirstOne
xxErrorxxError
yyErroryyError
zzErrorzzError
Table A-2: WriteFirstSemi and WriteFirstOne
WriteFirstSemiWriteFirstOne
00Error00Error
b;GoToTapeEndb1GoToTapeEnd
;ForwardsWriteFirstSemi;ForwardsWriteFirstOne
1ForwardsWriteFirstSemi1ForwardsWriteFirstOne
xForwardsWriteFirstSemixForwardsWriteFirstOne
yForwardsWriteFirstSemiyForwardsWriteFirstOne
zzErrorzzError
Table A-3: GoToTapeEnd and MarkTapeEnd
GoToTapeEndMarkTapeEnd
000Error
bbbError
;BackwardsMarkTapeEnd;zNextChar
1BackwardsMarkTapeEnd11Error
xxxError
yyyError
zzzError
Table A-4: NextChar and StepForward
NextCharStepForward
00Error0
bbErrorb
;BackwardsNextChar;ForwardsReadChar
1BackwardsNextChar1ForwardsReadChar
x;StepForwardx
y1StepForwardy
zBackwardsNextCharz
Table A-5: ReadChar and WriteSemi
ReadCharWriteSemi
00Error00Error
b1Errorb;NextChar
;xWriteSemi;FowardsWriteSemi
1yWriteOne1ForwardsWriteSemi
xxErrorxForwardsWriteSemi
yyErroryForwardsWriteSemi
zzWriteLastSemizForwardsWriteSemi
Table A-6: WriteLastSemi and SetHead
WriteLastSemiSetHead
00Error00Error
b;SetHeadbbError
;ForwardsWriteLastSemi;BackwardsSetHead
1ForwardsWriteLastSemi1BackwardsSetHead
xForwardsWriteLastSemixxError
yForwardsWriteLastSemiyyError
zForwardsWriteLastSemizzPauseCopy
Table A-7: WriteOne and PauseCopy
WriteOnePauseCopy
00Error0
b1NextCharb
;ForwardsWriteOne;
1ForwardsWriteOne1
xForwardsWriteOnex
yForwardsWriteOney
zForwardsWriteOnezzStartAdd
A.2: The Add Subroutine
Table A-8: StartAdd and FindSemiForDele
StartAddFindSemiForDele
00
bb
;;1FindSumEnd
11ForwardsFindSemiForDele
xx
yy
zForwardsFindSemiForDelez
Table A-9: FindSumEnd and EndSum
FindSumEndEndSum
00
bBackwardsEndSumbBackwardsEndSum
;bEndSum;bEndSum
1ForwardsFindSumEnd1;FindSumStart
xx
yy
zz
Table A-10: FindSumStart and StepBackward
FindSumStartStepBackward
00
bb
;BackwardsFindSumStart;BackwardsResetHead
1BackwardsFindSumStart1
xx
yy
z;StepBackwardz
Table A-11: ResetHead and PauseAdd
ResetHeadPauseAdd
00
bb
;;PauseAdd;;Start
1BackwardsResetHead1
xx
yy
zz
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
00Error
b1Error
;xWriteSemi
1yWriteOne
xxError
yyError
zzPauseCopy

Saturday, May 07, 2016

Noam Chomsky And Norman Mailer Share A Jail Cell For A Night

No joke. This happened as a result of an October 1967 march on the Pentagon to protest the Vietnam war. I find I had misremembered this passage. I recalled Mailer as being much less modest, as not acknowledging that technical linguistics used mathematical methods that might be beyond him at that stage of his life, no matter how much time he put into it. (I haven't actually read all of the technical works by Chomsky in the references below.) I have always liked Mailer's reporting and essays better than his novels, an opinion that I probably share with many and that he did not appreciate.

"Definitive word came through. The lawyers were gone, the Commissioners were gone: nobody out until morning. So Mailer picked his bunk. It was next to Noam Chomsky, a slim-featured man with an ascetic expression, and an air of gentle but absolute moral integrity. Friends at Wellfleet had wanted him to meet Chomsky at a summer before - he had been told that Chomsky, although barely thirty, was considered a genius at MIT for his new contributions to linguistics - but Mailer had arrived at the party too late. Now, as he bunked down next to Chomsky, Mailer looked for some way to open a discussion on linguistics - he had an amateur's interest in the subject, no, rather he had a mad inventor's interest, with several wild theories in his pocket which he had never been able to exercise since he could not understand what he read in linguistics books. So he cleared his throat now once or twice, turned over in bed, looked for a preparatory question, and recognized that he and Chomsky might share a cell for months, and be the best and most civilized of cellmates, before the mood would be proper to strike the first note of inquiry into what was obviously the tightly packed conceptual coils of Chomsky's intellections. Instead they chatted mildly of the day, of the arrests (Chomsky had also been arrested with Dellinger), and of when they would get out. Chomsky - by all odds a dedicated teacher - seemed uneasy at the thought of missing class on Monday.

On that long unwinding passage from the contractions of the day into the deliberations of the dream, Mailer passed through a revery over much traveled and by now level ground where he thought once more of the war in Vietnam, the charges against it, the defenses for it, and his own final condemnation which had landed him here on this filthy blanket and lumpy bed, this smoke-filled barracks air, where he listened half-asleep to the echoes of Teague's loud confident Leninist voice, he, Mailer, ex-revolutionary, now last of the small entrepreneurs, Left Conservative, that lonely flag - there was no one in America who had a position even remotely like his own, who else could indeed could offer such a solution as he possessed to such a war, such a damnable war. Let us leave him as he passes into sleep. The argument in his brain can be submitted to the reader in the following pages with somewhat more order than Mailer possessed on his long voyage out into the unfamiliar dimensions of prison rest..." -- Norman Mailer (1968).

References
  • Noam Chomsky (1959). On certain formal properties of grammars, Information and Control, V. 2: pp. 137-167.
  • Noam Chomsky (1965). Aspects of the Theory of Syntax, MIT Press.
  • Noam Chomsky (1969). American Power and the New Mandarins, Pantheon Books.
  • Noam Chomsky and M. P. Schützenberger (1963). The algebraic theory of context-free languages, in Computer Programming and Formal Systems, North Holland.
  • Norman Mailer (1968) The Armies of the Night: History as a Novel, the Novel as History, New American Library.

Saturday, April 30, 2016

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.

Wednesday, April 13, 2016

Math Is Power

1.0 Introduction

A common type of post in this blog is the presentation of concrete numerical examples in economics. Sometimes I present examples to illustrate some principle. But usually I try to find examples that are counter-intuitive or perverse, at least from the perspective of economics as mainstream economists often misteach it.

Voting games provide an arena where one can find surprising results in political science. I am thinking specifically of power indices. In this post, I try to explain two of the most widely used power indices by means of an example.

2.0 Me and My Aunt: A Voting Game

For purposes of exposition, I consider a specific game, called Me and My Aunt. There are four players in this version of the game, represented by elements of the set:

P = The set of players = {0, 1, 2, 3}

Out of respect, the first player gets two votes, while all other players get a vote each (Table 1). A coalition, S, is a set of players. That is, a coalition is a subset of P. A coalition passes a resolution if it has a majority of votes. Since there are four players, one of who has two votes, the total number of votes is five. So a majority, in this game of weighted voting, is three votes.

Table 1: Players and Their Votes
PlayersVotes
0 (Aunt)2
1 (Me)1
21
31

One needs to specify the payoff to each coalition to complete the definition, in characteristic function form, of this game. The characteristic function, v(S) maps the set of all subsets of P to the set {0, 1}. If the players in S have three or more votes,v(S) is 1. Otherwise, it is 0. That is, a winning coalition gains a payoff of one to share among its members.

3.0 The Penrose-Banzhaf Power Index

Power for a player, in this mathematical approach, is the ability to be the decisive member of a coalition. If, for a large number of coalitions, you being in or out of a coalition determines whether or not that coalition can pass a resolution, you have a lot of power. Correspondingly, if the members of most coalitions do not care whether you join, because your presence has no influence on whether or not they can put their agenda into effect, you have little power.

The Penrose-Banzhaf power index is one (of many) attempts to quantify this idea. Table 2 lists all 16 coalitions for the voting game under consideration. (The number of coalitions is the sum of a row in Pascal's triangle.) The second column in Table 2 specifies the value for the characteristic function for that coalition. Equivalently, the third column notes which eight coalitions are winning coalitions, and which eight are losing. The last two columns are useful for tallying up counts needed for the Penrose-Banzhaf index.

Table 2: Calculations for Penrose-Banzhaf Power Index
CoalitionCharacteristic
Function
Winning
or Losing
Player
Aunt (0)Me (1)
{}v( {} ) = 0Losing00
{0}v( {0} ) = 0Losing00
{1}v( {1} ) = 0Losing00
{2}v( {2} ) = 0Losing00
{3}v( {3} ) = 0Losing00
{0, 1}v( {0, 1} ) = 1Winning11
{0, 2}v( {0, 2} ) = 1Winning10
{0, 3}v( {0, 3} ) = 1Winning10
{1, 2}v( {1, 2} ) = 0Losing00
{1, 3}v( {1, 3} ) = 0Losing00
{2, 3}v( {2, 3} ) = 0Losing00
{0, 1, 2}v( {0, 1, 2} ) = 1Winning10
{0, 1, 3}v( {0, 1, 3} ) = 1Winning10
{0, 2, 3}v( {0, 2, 3} ) = 1Winning10
{1, 2, 3}v( {1, 2, 3} ) = 1Winning01
{0, 1, 2, 3}v( {0, 1, 2, 3} ) = 1Winning00

The Penrose-Banzhaf index, ψ(i) is calculated for each player i. It is defined, for a given player, to be the ratio of the number of winning coalitions in which that player is decisive to the total number of coalitions, winning or losing. A player is decisive for a coalition if:

  • The coalition is a winning coalition.
  • The removal of the player from the coalition converts it to a losing coalition.

From the table above, one can see that player 0 is decisive for six coalitions, while player 1 is decisive for only two coalitions. Hence, the Penrose-Banzhaf index for "my aunt" is:

ψ(0) = 6/16 = 3/8

By symmetry, the index values for players 2 and 3 are the same as the value for player 1:

ψ(1) = ψ(2) = ψ(3) = 2/16 = 1/8

More than one player can be decisive for a winning coalition. No need exists for the Penrose-Banzhaf index to sum up to one. How much one's vote is weighted does not bear a simple relationship to how much power one has. Also note that the definition of this power index is not confined to simple majority games. Power indices can be calculated for voting games in which a super-majority is required to pass a measure. For example, in the United States Senate, 60 senators are needed to end a filibuster.

4.0 The Shapley-Shubik Power Index

The Shapley-Shubik power index is an application of the calculation of the Shapley value to voting games. The Shapley value applies to cooperative games, in general. For its use as a measure of power in voting games, it matters in which order players enter a coalition. Accordingly, Table 3 lists all 24 permutations of all four players in the voting game being analyzed.

Table 3: Calculations for the Shapley-Shubik Power Index
PermutationPlayer
Aunt (0)Me (1)
(0, 1, 2, 3)v( {0} ) - v( {} ) = 0v( {0, 1} ) - v( {0} ) = 1
(0, 1, 3, 2)v( {0} ) - v( {} ) = 0v( {0, 1} ) - v( {0} ) = 1
(0, 2, 1, 3)v( {0} ) - v( {} ) = 0v( {0, 1, 2} )
- v( {0, 2} ) = 0
(0, 2, 3, 1)v( {0} ) - v( {} ) = 0v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(0, 3, 1, 2)v( {0} ) - v( {} ) = 0v( {0, 1, 3} )
- v( {0, 3} ) = 0
(0, 3, 2, 1)v( {0} ) - v( {} ) = 0v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(1, 0, 2, 3)v( {0, 1} )
- v( {1} ) = 1
v( {1} ) - v( {} ) = 0
(1, 0, 3, 2)v( {0, 1} )
- v( {1} ) = 1
v( {1} ) - v( {} ) = 0
(1, 2, 0, 3)v( {0, 1, 2} )
- v( {1, 2} ) = 1
v( {1} ) - v( {} ) = 0
(1, 2, 3, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1} ) - v( {} ) = 0
(1, 3, 0, 2)v( {0, 1, 3} )
- v( {1, 3} ) = 1
v( {1} ) - v( {} ) = 0
(1, 3, 2, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1} ) - v( {} ) = 0
(2, 0, 1, 3)v( {0, 2} )
- v( {2} ) = 1
v( {0, 1, 2} )
- v( {0, 2} ) = 0
(2, 0, 3, 1)v( {0, 2} )
- v( {2} ) = 1
v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(2, 1, 0, 3)v( {0, 1, 2} )
- v( {1, 2} ) = 1
v( {1, 2} ) - v( {2} ) = 0
(2, 1, 3, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1, 2} ) - v( {2} ) = 0
(2, 3, 0, 1)v( {0, 2, 3} )
- v( {2, 3} ) = 1
v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(2, 3, 1, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1, 2, 3} )
- v( {2, 3} ) = 1
(3, 0, 1, 2)v( {0, 3} )
- v( {3} ) = 1
v( {0, 1, 3} )
- v( {0, 3} ) = 0
(3, 0, 2, 1)v( {0, 3} )
- v( {3} ) = 1
v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(3, 1, 0, 2)v( {0, 1, 3} )
- v( {1, 3} ) = 1
v( {1, 3} ) - v( {3} ) = 0
(3, 1, 2, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1, 3} ) - v( {3} ) = 0
(3, 2, 0, 1)v( {0, 2, 3} )
- v( {2, 3} ) = 1
v( {0, 1, 2, 3} )
- v( {0, 2, 3} ) = 0
(3, 2, 1, 0)v( {0, 1, 2, 3} )
- v( {1, 2, 3} ) = 0
v( {1, 2, 3} )
- v( {2, 3} ) = 1

Table 3 shows some initially confusing calculations in the last two columns, where each of these columns is defined for a given player. Suppose a player and a permutation are defined. For that permutation, let the set Sπ, i contain those players in the permutation π to the left of the given player i. The difference, in the last two columns, is the following, for i equal to 0 and to 1, respectively:

v(Sπ, i ∪ {i}) - v(Sπ, i)

The Shapley-Shubik power index, for a player, is the ratio of a sum to the number of permutations of players. And that sum is calculated for each player, as the sum over all permutations, of the above difference in the value of the value of the characteristic function.

If I understand correctly, given a permutation, the above difference can only take on values of 0 or 1. And it will only be 1 for one player, where that player determines whether the formation of the coalition in the order given will be a winning coalition. As a consequence, the Shapley-Shubik power index is guaranteed to sum over players to unity. In this case, power is a fixed amount, with each player being measured as having a defined proportion of that power.

5.0 Both Power Indices

The above has stepped through the calculation of two power indices, for all players, in a given game. Table 4 lists their values, as well as a normalization of the Penrose-Banzhauf power index such that the sum of the power, over all players, is unity. (I gather that the Penrose-Banzhauf index and the normalized index do not have the same properties.) As one might expect from the definition of the game, "my aunt" has more power than "me" in this game.

Table 4: The Penrose-Banzhaf and Shapley-Shubik Power Indices
PlayerPenrose-Banzhaf Power IndexShapley-Shubik
Power Index
IndexNormalized
06/16 = 3/86/12 = 1/212/24 = 1/2
12/16 = 1/82/12 = 1/64/24 = 1/6
22/16 = 1/82/12 = 1/64/24 = 1/6
32/16 = 1/82/12 = 1/64/24 = 1/6

In many voting games, the normalized Penrose-Banzhauf and Shapley-Shubik power indices are not identical for all players. In fact, suppose the rules for the above variation of Me and my Aunt voting game are varied. Suppose now that four votes - a supermajority - are needed to carry a motion. The normalized Penrose-Banzhaf index for player 0 becomes 1/3, while each of the other players have a normalized Penrose-Banzhaf index of 2/9. Interestingly enough, the Shapley-Shubik indices for the players do not change, if I have calculated correctly. But the values assigned to rows in Table 3 do sometimes vary. Anyways, that one tweak of the rules results in different power indices, depending on which method one adopts. A more interesting example would be one in which the rankings vary among power indices.

Other power indices, albeit less common, do exist. Which one is most widely applicable? I would think that mainstream economists, given game theory and marginalism, would tend to prefer the Shapley-Shubik power index. Felsenthal and Machover (2004) seem to be widely recognized experts on measures of voting power, and they have come to prefer the Penrose-Banzhaf index over the Shapley-Shubik index.

6.0 Where To Go From Here

I have described above a couple of power indices in voting games. As I understand it, many have tried to write down reasonable axioms that characterize power indices. One challenge is to specify a set of axioms such that your preferred power index is the only one that satisfies them. But, as I understand it, some sets of reasonable axioms are open insofar as more than one power index would satisfy them. I seem to recall a theorem that one could create a power index for a reasonable set of axioms such that whichever player you want in a voting game is the most powerful. Apparently, a connection can be drawn between a power index and a voting procedure. And Donald Saari boasts that he could create an apparently fair voting procedure that would result in whatever candidate you like being elected.

I gather that many examples of voting games have been presented in which apparently paradoxical or perverse results arise. And these do not seem to be merely theoretical results. Can I find some such examples? Perhaps, I should look here at some of Daron Acemoglu's work.

I am aware of three types of examples to look for. One is that of a dummy. A dummy is a player that, under the weights and the rule for how many votes are needed for passage, can never be decisive in a coalition. Whether this player drops out or joins a coalition can never change whether or not a resolution is passed, even though the player has a positive weight. A second odd possibility arises as the consequence of adding a new member to the electorate:

"...power of a weighted voting body may increase, rather than decrease, when new members are added to the original body." -- Steven J. Brams and Paul J. Affuso (1976).

A third odd possibility apparently can arise on a council when one district annexes another. Suppose, the district annexing the other consequently increases the weight of its vote accordingly. One might think a greater weight leads to more power. But, in certain cases, the normalized Penrose-Banzhaf index can decrease.

The above calculations for the Penrose-Banzhaf and Shapley-Shubik power indices treat all coalitions or permutations, respectively, as equally likely to arise. Empirically, this does not seem to be true. And this has an impact on how one might measure power. For example, since voting is unweighted on the Supreme Court of the United States, all justices might be thought to be equally powerful. But, because of the formation of well-defined blocks, Anthony Kennedy was often described as being particularly powerful in deciding court decisions, at least when Antonin Scalia was still alive. So empirically, one might include some assessment of the affinities of the players for one another and, thus, some influence on the probabilities of each coalition forming. This will have consequences on the calculation of power indices. But why stop there? In the United States these days, politicians only seem to represent the most wealthy.

Update: This page, from the University of Warwick, has links to utilities for calculating various power indices.

References
  • Steven J. Brams and Paul J. Affuso (1976). Power and Size: A New Paradox, Theory and Decision. V. 7, Iss. 1 (Feb.): pp. 29-56.
  • Dan S. Felsenthal and Moshé Machover (2004). Voting Power Measurement: A Story of Misreinvention, London Scool of Economics and Political Science
  • Andrew Gelman, Jonathan N. Katz, and Joseph Bafumi (2004). Standard Voting Power Indexes Do Not Work: An Empirical Analysis, B. J. Pol. S.. V. 34: pp. 657-674.
  • Guillermo Owen (1971) Political Games, Naval Research Logistics Quarterly. V. 18, Iss. 3 (Sep.): pp. 345-355.
  • Donald G. Saari and Katri K. Sieberg (1999). Some Surprising Properties of Power Indices.