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