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

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

• Steve Fleetwood (2016). Reflections upon neoclassical labour economics, in What is Neoclassical Economics? Debating the origins, meaning and significance, (ed. by Jamie Morgan), Routledge.
• Arrigo Opocher and Ian Steedman (2015). Full Industry Equilibrium: A Theory of the Industrial Long Run, Cambridge University Press.
• Robert L. Vienneau (2005). On Labour Demand and Equilibria of the Firm, Manchester School, V. 73, Iss. 5: pp. 612-619.

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

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.